Algebraic Side-Channel Attack on Twofish

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