Impossible differential cryptanalysis of Mini-AES

Cryptologia, Oct 2003 by Phan, Raphael Chung-Wei

1. Obtain 2^sup 13^ plaintexts, P, and another 2^sup 13^ corresponding plaintexts, P' which are equal in the second and third nibble and differ in the other nibbles. Since each P and P'a pair with passive second and third nibbles while the first and third nibbles are active, we then have 2^sup 13^ such pairs.

2. Obtain the ciphertexts, C and C'ponding to these plaintext pairs. Choose only the pairs whose ciphertext pairs differ in only one nibble in each column and each row. We expect that out of 2^sup 13^ pairs, we will get such ciphertext pairs with probability (2^sup -4^ x 2^sup -4^) (2^sup -4^ x 2^sup -4^) = 2^sup -7^, hence 2^sup 13^ x 2^sup -7^ = 2^sup 6^ pairs will satisfy the requirement.

b. A randomly guessed key value would cause a pair X and X' that differs in only one nibble in the first column with probability 2^sup -4^ x 2 = 2^sup -3^.

c. This will ensure that the 4-round impossible differential as in Figure 2 will hold in the last 4 rounds. The guessed nibble values of K^sub 0^ that caused these pairs are wrong values and are discarded.

4. After analyzing 2^sup 6^ pairs, there are only about 2^sup 8^(1 - 2^sup -3^)26 [asymptotically =] 2^sup 8^e^sup -2^sup 3^^ [asymptotically =] 0 wrong values of the two nibbles of K^sub 0^ so only the right value remains.

4 CONCLUSION

We have presented an introduction to the impossible differential cryptanalysis by demonstrating step by step how a 4-round impossible differential of Mini-AES can be constructed. As a further step in understanding the concepts behind this attack, the reader is encouraged to verify the 4-round impossible differential by hand. This is an important part of impossible differential cryptanalysis because the difficulty mostly lies in trying to find impossible differentials before an impossible differential attack can be applied on encryption algorithms.

Once the reader is comfortable with the idea of the attack, he should refer to the following papers [5, 6, 7, 8] for details on how the impossible differential cryptanalysis is applied to the real AES.

REFERENCES

1. NIST. 2001. AES Homepage. Available at: http://www.nist.gov/ aes.

2. Stallings, W. 2002. The Advanced Encryption Standard. Cryptologia. 26(3): 165-188.

3. Phan, R. C.-W. 2002. Mini Advanced Encryption Standard (Mini-AES): A Testbed for Cryptanalysis Students. Cryptologia. 26(4): 283-306.

4. Biham, E., A. Biryukov, and A. Shamir. 2001. Miss in the Middle Attacks on IDEA and Khufu. In Advances of Cryptology - FSE '99 (Lecture Notes in Computer Science No. 1636). 124-138.

5. Biham, E. and N. Keller. 2000. Cryptanalysis of Reduced Variants of Rijndael. Submitted to 3rd AES Candidate Conference. Available at http://csrc. nist.gov/CryptoToolkit/aes/round2/conf3/papers/35-ebiham.pdf.

6. Phan, R. C. W. and M. U. Siddiqi. 2001. Generalised Impossible Differentials of Advanced Encryption Standard. IEE Electronics Letters. 37(14): 896-898.

7. Phan, R. C. W. 2002. Classes of Impossible Differentials of Advanced Encryption Standard. IEE Electronics Letters. 38(11): 508-510.