Algebraic Side-Channel Attack on Twofish

Chujiao Ma⁺, John Chandy, and Zhijie Shi

¹University of Connecticut, Connecticut, United States of America
{chujiao.ma, john.chandy, zhijie.shi}@uconn.edu

Abstract

While algebraic side-channel attack (ASCA) has been successful in breaking simple cryptographic algorithms, it has never been done on larger or more complex algorithms such as Twofish. Compared to other algorithms that ASCA has been used on, Twofish is more difficult to attack due to the key-dependent S-boxes as well as the complex key scheduling. In this paper, we propose the first algebraic side-channel attack on Twofish, and examine the importance of side-channel information in getting past the key-dependent S-boxes and the complex key scheduling. The cryptographic algorithm and side-channel information are both expressed as boolean equations and a SAT solver is used to recover the key. While algebraic attack by itself is not sufficient to break the algorithm, with the help of side-channel information such as Hamming weights, we are able to correctly solve for 96 bits of the 128 bits key in under 2 hours with known plaintext/ciphertext.

Keywords: algebraic side-channel attack, Twofish, cryptography, block cipher, SAT solver, conjunctive normal form

+: Corresponding author: Chujiao Ma
Department of Computer Science and Engineering, 371 Fairfield Way, Unit 4155, University of Connecticut, Storrs, CT 06269-4155, U.S.A. Tel: 412-759-1257

Journal of Internet Services and Information Security (JISIS), 7(2): 32-43, May 2017 [pdf]