Interpolation attacks of the block cipher: SNAKE. (English) Zbl 0942.94009

Knudsen, Lars (ed.), Fast software encryption. 6th international workshop, FSE ‘99. Rome, Italy, March 24-26, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1636, 275-289 (1999).
Summary: This paper presents an efficient interpolation attack using a computer algebra system. The interpolation attack proposed by T. Jakobsen and L. R. Knudsen, “The interpolation attack on block ciphers”, Fast Software Encryption, FSE’97, Lect. Notes Comput. Sci. 1267, 28-40 (1997)] was shown to be effective for attacking ciphers that use simple algebraic functions. However, there was a problem that the complexity and the number of pairs of plaintexts and ciphertexts required for the attack can be overestimated. The authors solve this problem by first, finding the actual number of coefficients in the polynomial (or rational expression) used in the attack by using a computer algebra system, and second, by finding the polynomial (or rational expression) with fewest coefficients by choosing the plaintexts.
They apply this interpolation attack to the block cipher SNAKE proposed by C. Lee and Y. Cha [“The block cipher: SNAKE with provable resistance against DC and LC attacks”, in: Proc. 1997 Korea-Japan Joint Workshop on Information Security and Cryptology (JW-ISC’97), 3-17 (1997)]. In the SNAKE family there are two types of Feistel ciphers, SNAKE(1) and SNAKE(2), with different round functions. Both of them use the inverse function in Galois field \(GF(2^m)\) as \(S\)-box. The authors show that when the block size is 64 bits and \(m=8\), all round keys are recovered for SNAKE(1) and SNAKE(2) with up to 11 rounds. Moreover, when the block size is 128 bits and \(m=16\), all round keys are recovered for SNAKE(1) with up to 15 rounds and SNAKE(2) with up to 16 rounds.
For the entire collection see [Zbl 0917.00016].


94A60 Cryptography


SNAKE; Risa/Asir