A testbed for cryptanalysis students

Mini advanced encryption standard (mini-AES): A testbed for cryptanalysis students

Phan, Raphael Chung-Wei

ABSTRACT: In this paper, we present a mini version of Rijndael, the symmetric-key block cipher selected as the Advanced Encryption Standard (AES) recently. Mini-AES has all the parameters significantly reduced while at the same time preserving its original structure. It is meant to be a purely educational cipher and is not considered secure for actual applications. The purpose is such that once undergraduate students and amateur cryptanalysts have grasped the basic principles behind how Mini-AES works, it will be easy for them to move on to the real AES. At the same time, an illustration of how the Square attack can be applied to Mini-AES is presented in the hope that Mini-AES would also serve as a testbed for students to begin their cryptanalysis efforts.

KEYWORDS: Advanced Encryption Standard, Rijndael, block cipher, cryptanalysis, square attack.

1 INTRODUCTION

The National Institute of Standards and Technology (NIST) issued in 1997 a call for proposals for the Advanced Encryption Standard (AES) [7]. Twenty one proposals were submitted, out of which 15 were accepted. Two years later, after undergoing public review and analysis, the list was narrowed down to 5 finalists, and more extensive analysis ensued. In October 2000, Rijndael emerged as the winner and was selected as the Advanced Encryption Standard [8]. The specifications of the AES are now available as a Federal Information Processing Standard (FIPS) [9].

The AES has a block size of 128 bits, and supports key sizes of 128, 192 and 256 bits. The number of rounds is 10, 12 or 14 for the three different key sizes respectively. Just like the DES, the AES is expected to draw much attention from cryptographers and cryptanalysts alike within the space of time from now until the next few decades. In order to aid undergraduate cryptography students and aspiring cryptanalysts in better understanding the internal workings of the AES, we present a mini version of the AES, with all the parameters significantly reduced while preserving its original structure. This mini version is purely educational and hence it is hoped to aid students in grasping the underlying concepts in the design of Rijndael-like ciphers and also to serve as a testbed for aspiring cryptanalysts to try out various cryptanalytic attacks.

In section 2, we present the mathematical background to help the student in understanding the components of Mini-AES. We then proceed to describe Mini– AES in Section 3. In Section 4, we relate Mini-AES to the real AES. The Square attack, a fairly new cryptanalytic attack popularised by Rijndael is presented in detail in Section 5. We conclude in Section 6.

2 MATHEMATICAL BACKGROUND

Mini-AES has a component, NibbleSub, which operates on a nibble (4 bits) at a time. In addition, another component, MixColumn operates on words of 4 nibbles. In this section, we present the mathematical background needed for the reader to have a clearer understanding of the components of Mini-AES.

4 THE ADVANCED ENCRYPTION STANDARD (AES)

In this section, we relate Mini-AES to the actual Advanced Encryption Standard (AES). Instead of having a block of 16 bits, the AES is a 128-bit block cipher, and supports secret key sizes of 128, 192 or 256 bits. We will describe the details of the AES with reference to a 128-bit key. The other variants are similar in nature.

The 128-bit block of the AES is expressed as a matrix of 4 x 4 bytes, in contrast to Mini-AES being expressed as a matrix of 2 x 2 nibbles.

AES consists of 10 rounds, where each round is similar to the round of Mini– AES, with the last round having no MixColumn. There is also a KeyAddition prior to the first round. The purpose of the extra KeyAddition and the omission of MixColumn is so that encryption and decryption of the AES would be similar in structure, and this simplifies implementation. The same basic hardware can then be used for both encryption and decryption.

The round components of the AES are ByteSub, ShiftRow, MixColumn and KeyAddition. ByteSub is similar to NibbleSub, but operates on one byte instead of one nibble. Likewise, ShiftRow rotates each row of the input block to the left by different byte amounts. The first row is unchanged, the second rotated left by 1 byte, the third by 2 and the fourth by 3. MixColumn takes each column of the input block and multiplies it with a constant 4 x 4 matrix. KeyAddition is similar to that of Mini-AES.

The usage of the various round components of the AES follow the Wide Trail Strategy [31, where every component has its own purpose. ByteSub provides the non-linearity that is vital for the security of any block cipher. ShiftRow and MixColumn provide the linear mixing component that ensures very high diffusion over multiple rounds. KeyAddition allows the secret key bits to influence the encryption process.

The Mini-AES key schedule takes the 16-bit secret key and expresses it as a group of four nibbles. Meanwhile, the AES key schedule takes the 128-bit secret key and expresses it as a group of four 32-bit words. The 0th round key. K^sub 0^ equals the secret key itself while each subsequent round key is derived from the secret key is almost the same way as Mini-AES. Further details of the AES can be found online at [9] and in a book [3].

5 THE SQUARE ATTACK

The structure of the AES is derived from its predecessor, the block cipher Square [2]. It is susceptible to a dedicated attack that was first developed on Square, also called the Square attack. In order to demonstrate to the student how the attack works on the AES, we will apply it on Mini-AES.

We have just seen through an illustrative example that NibbleSub does not spread the active nibbles, nor does it affect the balancedness of a delta set. ShiftRow does not affect the balancedness either, but just interchanges the position of two nibbles. MixColumn spreads one active nibble to two active nibbles in the same column. KeyAddition does not affect the balancedness nor spreads the active nibbles. Here we see that the balancedness and number of active nibbles in a delta set are influenced by only the MixColumn and ShiftRow.

Consider a 4-round Mini-AES. If we have a set of 16 plaintexts such that they are equal in all nibbles except in the first nibble where they have all the 16 possible different values, then after the first round, we will have a delta set that is still balanced and where there are two active nibbles in the first column.

After NibbleSub of the second round, the set is still balanced and the number of active nibbles is two. This remains the same after ShiftRow, but one of the active nibbles has been interchanged with a passive nibble in column 2. Due to this, then passing through MixColumn causes a still balanced delta set, but all nibbles are now active.

At the input of Round 3, we have a balanced delta set with all active nibbles. Passing through NibbleSub causes the same situation to exist. Likewise, ShiftRow does not change the situation either, so at the input of MixColumn, a balanced delta set exists that contains all active nibbles.

Recall again that a balanced delta set means that the XOR of each nibble position, either active or passive is zero. Now, at the input of MixColumn, the delta set is balanced and it contains all active nibbles. This means that each nibble contains all 16 possible values. We see how MixColumn influences this delta set by using an example.

CONCLUSION

We have presented a mini version of the Advanced Encryption Standard (AES) that is well-suited for undergraduate cryptography and cryptanalysis courses. Once the student feels comfortable with Mini-AES, then he will have no problem in understanding the inner workings of the real Advanced Encryption Standard. Mini-AES is also intended to be a testbed for students and aspiring cryptanalysts to experiment with the various cryptanalysis methods that are currently available in academic literature. As an example, we demonstrated in detail how the Square attack can be used on Mini-AES. With this, we hope to have provided the vital stepping stone for the student to advance into the fascinating world of cryptanalysis research.

ACKNOWLEDGEMENTS

We wish to thank the anonymous referees for their comments which have greatly enhanced this paper.

REFERENCES

1. Biham, Eli and Nathan Keller. 2000. Cryptanalysis of Reduced Variants of Rijndael. Available at http://csrc.nist.gov/encryption/aes/round2/ conf3/papers/35-ebiham.pdf.

2. Daemen, Joan, Lars Ramkilde Knudsen, and Vincent Rijmen. 1997. The Block Cipher Square. Proceedings of Fast Software Encryption 1997. (Lecture Notes in Computer Science No. 1267). New York: Springer-Verlag. pp. 149-165.

3. Daemen, Joan and Vincent Rijmen. 2002. The Design of Rijndael: AES – The Advanced Encryption Standard. Information Security and Cryptography series. New York: Springer-Verlag.

4. Ferguson, Niels and John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner, and Doug Whiting. 2000. Improved Cryptanalysis of Rijndael. Proceedings of Fast Software Encryption 2000. Available at http: //www. counterpane.com/rijndael.html.

5. Gilbert, Henri, and Marine Minier. 2000. A Collision Attack on 7 Rounds of Rijndael. Proceedings of 3d AES Conference. Available at http: //csrc. nist.gov/encryption/aes/round2/conf3/papers/11-hgilbert.pdf.

6. Lucks, Stefan. 2000. Attacking Seven Rounds of Rijndael under 192-bit and 256-bit Keys. Proceedings of 3d AES Conference. Available at http://csrc. nist.gov/encryption/aes/round2/conf3/papers/04-slucks.pdf.

7. NIST. 2000. AES Development Effort. Available at http: //csrc. nist. gov/encryption/aes/index2.html.

8. NIST. 2000. Commerce Department Announces Winner of Global Information Security Competition. October. Available at http://www.nist.gov/ public-affairs/releases/gOO-176.htm.

9. NIST. 2002. AES Homepage. Available at http://www.nist.gov/aes.

Raphael Chung-Wei Phan

ADDRESS: Swinburne Sarawak Institute of Technology, 1st Floor, State Complex, 93576 Kuching, Sarawak MALAYSIA. rphan(swinburne.edu.my.

BIOGRAPHICAL SKETCH

Raphael Phan Chung Wei received his BEng (Hons) degree in Computer Engineering from the Multimedia University (MMU), Cyberjaya MALAYSIA in 1999. He was a tutor with the Faculty of Engineering, MMU and researcher at the Center for Smart Systems and Innovation, MMU from June 1999 to June 2001 where he also pursued his MEngSc degree by research in the `Cryptanalysis of the Advanced Encryption Standard & Skipjack’. He is currently an Engineering lecturer and researcher with the Swinburne Sarawak Institute of Technology, Kuching MALAYSIA. His research interests include cryptanalysis, block ciphers, and antivirus techniques.

Copyright Cryptologia Oct 2002

Provided by ProQuest Information and Learning Company. All rights Reserved