Volume 7 - Issue 2
Algebraic Side-Channel Attack on Twofish
- Chujiao Ma
University of Connecticut, Storrs, Connecticut 06269, USA
chujiao.ma@uconn.edu
- John Chandy
University of Connecticut, Storrs, Connecticut 06269, USA
john.chandy@uconn.edu
- Zhijie Shi
University of Connecticut, Storrs, Connecticut 06269, USA
zhijie.shi@uconn.edu
Keywords: algebraic side-channel attack, Twofish, cryptography, block cipher, SAT solver, conjunctive normal form
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.