Further notes for a self-study course in block-cipher cryptanalysis

Cryptologia, Apr 2002 by Phan, Raphael Chung-Wei

ABSTRACT: To every aspiring cryptanalyst, especially those just starting to study cryptanalysis, there is no standard textbook to refer. A year ago, the existing literature on block-cipher cryptanalysis was organized in a self-study course in a way that could help students learn cryptanalysis step by step. [5] Since then, various new cryptanalytic methods have sprung up and have been added to the cryptanalytic literature. This paper attempts to acquaint the student with the new cryptanalytic methods and serve as further notes to the course in block-cipher cryptanalysis.

KEYWORDS: Cryptanalysis, block ciphers

1 INTRODUCTION

For every starting cryptanalyst, it would usually take quite some time before he starts to settle down and get the feel of cryptanalysis. One factor that adds to the difficulty is the absence of a standard textbook on cryptanalysis. With nothing to refer but research papers from journals and conferences, the student needs some form of guidance so that he can progress in the correct direction. To fill that void, Schneier [5] organized the existing literature on block-cipher cryptanalysis into a self-study course in an effort to help students to get a head start in learning cryptanalysis.

More than a year has passed since then, and various new cryptanalytic methods have sprung up. Among the notable developments is the extensive cryptanalysis of the 5 finalists [2] for the Advanced Encryption Standard (AES), culminating in the final selection of Rijndael as the AES in October 2000 [4]. While attempting to serve as further notes to the self-study course in block-cipher cryptanalysis, the main purpose of this paper is to acquaint the student with the new cryptanalytic methods, namely the Square attack, slide attacks, the saturation attack, impossible differential cryptanalysis, the boomerang attack, the amplified boomerang attack and the rectangle attack.

2 COURSE MATERIAL

The course material is mainly from the proceedings of the Crypto, Eurocrypt and FSE conferences plus proceedings of the AES conferences [3]. References made would be to the papers that are related to the new cryptanalytic methods.

3 FURTHER NOTES FOR THE SELF-STUDY COURSE

3.1 Recap

In [5], the course syllabus covered the very basics of block-cipher cryptanalysis starting from the time when modern cryptanalysis first began in 1991 with differential cryptanalysis, and later linear cryptanalysis and key-schedule cryptanalysis up until the state of cryptanalytic research in the year 1998.

Within those first few years, we saw the extensions of all the three basic cryptanalytic methods, the differential cryptanalysis, linear cryptanalysis and key-schedule cryptanalysis.

The idea of differential cryptanalysis was extended to higher-order differential cryptanalysis, truncated differential cryptanalysis and differential-linear cryptanalysis. As for the linear cryptanalysis, the concept of multiple approximations and non-linear approximations were introduced. Linear cryptanalysis was also generalized and later extended into an attack called partitioning cryptanalysis. And in 1997, a new attack similar to the linear cryptanalysis but unique in its own right was introduced. It was the interpolation attack. Meanwhile, research into the weaknesses of key-schedules had resulted in related-key cryptanalysis.

Towards the end of the self-study course syllabus in [51, the student was introduced to the concept of the Square attack. We continue off from there.

3.2 The Square Attack

Read up to Section 8.3 of J. Daemen, and V. Rijmen, "AES proposal:

3.3 The Square Attack of Crypton

Read the description of Crypton in C. H. Lim, "Crypton: A New 128-bit Block Cipher", AES submission, 1998, available at http://www. nist. gov/aes. Try to implement the Square attack on Crypton. The solution is in C. D'Halluin,

G. Bijnens, V. Rijmen, B. Preneel, "Attack on Six Rounds of Crypton", Advances in Cryptology Proceedings of FSE 1999, 46-59, 1999.

3.4 Improved Square Attacks of Rjjndael

See if you can extend the Square attack to more than 6 rounds of Rijndael. The answer lies in exploiting the Rijndael key-schedule. Read S. Lucks, "Attacking Seven Rounds of Rijndael under 192-bit and 256-bit Keys", Proceedings of 3rd Advanced Encryption Standard Candidate Conference, available at http://www.nist.gov/aes. Think of how you can improve on the Square attack by reducing its computation complexity. The solution is in N. Ferguson, J. Kelsey, S. Lucks, B. Schneier, M. Stay, D. Wagner and D. Whiting, "Improved Cryptanalysis of Rijndael", Advances in Cryptology Proceedings of FSE 2000, 2001. Also read H. Gilbert, and M. Minier, "A Collision Attack on Seven Rounds of Rijndael", Proceedings of 3rd Advanced Encryption Standard Candidate Conference, April 2000, 230-241, available at http: //www. nist. gov/aes.

3.5 Slide Attacks

Read up to Section 4 of A. Biryukov and D. Wagner, "Slide Attacks", Advances in Cryptology Proceedings of FSE 1999, 245-259, 1999. Proceed to read the description of Treyfer in Section 5 but try to apply a slide attack on Treyfer on your own before reading the description of the attack.