Differential-algebraic cryptanalysis of reduced-round of Serpent-256

Abstract

Differential cryptanalysis is a general cryptanalytic tool that makes use of differentials over some rounds of a cipher, combined with some key bit guesses of one or two rounds. This paper introduces a new cryptanalysis strategy of block ciphers named differential-algebraic cryptanalysis. The idea of differential-algebraic cryptanalysis is to find a differential with high probability and build the multivariable system equations for the last few rounds. The subkey values of the last few rounds can be obtained by filtering the solutions of system equations instead of guessing all possible subkey values. We use the differential-algebraic cryptanalysis to break 8-round Serpent-256. Our attack can recover the 256-bit key with 2 83 chosen plaintexts, 2 180.4 8-round Serpent-256 encryptions and 2 176.7 bytes memory. Compared with the previous differential cryptanalysis results, both the data complexity and the time complexity are reduced, but the memory requirements are increased. The time complexity and the memory requirements are very close, and a time-memory tradeoff is exploited. © 2010 Science in China Press and Springer-Verlag Berlin Heidelberg.