Impossible differential cryptanalysis of Mini-AES

Cryptologia, Oct 2003 by Phan, Raphael Chung-Wei

Considering Mini-AES up to 4 rounds, suppose we choose two plaintexts, P and P' such that they differ in only one nibble and are equal in the other nibbles.

The nibble in which P and P' differ is called the active nibble whereas the nibble in which they are equal is called a passive nibble. Hence, in Example 2a, there is one active nibble (the leftmost nibble) and three passive nibbles.

Let's observe how these two plaintexts behave as they go through the round components of Mini-AES.

At the output of Inverse NibbleSub, we have the same number of active and passive nibbles, in the same positions.

Notice that we have gone through the last two rounds, Rounds 3 and 4 in reverse, and are now at the end of Round 2.

Therefore, as a consequence of Example 4a and 4b, we conclude that given two ciphertexts such that they are equal in exactly one nibble in each row and column, we will always get two outputs with one active and one passive nibble in each column at the end of Round 2.

However, this contradicts with our previous argument derived from Example 3 about the behaviour two plaintexts through the first two rounds where we mentioned that at the output of round 2, all nibbles are active. Hence, we conclude that if we have two plaintexts, P and P' such that they differ in only one nibble, then after encryption with 4-round Mini-AES, we will never have ciphertexts, T and T' such that they differ in only one nibble in each row and column. This is illustrated in Figure 2, and is called a 4-round impossible differential.

By making use of this 4-round impossible differential, we can mount impossible differential attacks on Mini-AES with even more rounds. Simply place the impossible differential in the middle rounds, and then guess the round keys in the outer rounds and use them to verify if the impossible differential occurs. If so, then the guessed round key values are wrong and removed from the list of possible round keys. This is really the gist behind impossible differential cryptanalysis.

3.2 Attacking 5-round Mini-AES

In this section, we consider how to use the 4-round impossible differential to mount an impossible differential cryptanalysis on Mini-AES with up to 5 rounds. An attack on Mini-AES up to 6 rounds works along the same lines and we leave it to the interested reader to work it out. As a hint, the attack is very much similar to the impossible differential attack on 6 rounds of the real AES presented in [8].

We now describe how to mount an impossible differential cryptanalysis on Mini-AES up to 5 rounds. We apply the impossible differential to the last 4 rounds of this Mini-AES version. Then we make guesses of some nibbles of the 0th round key, K^sub 0^ and partially encrypt plaintexts with K^sub 0^. If we discover that the impossible differential holds for the last 4 rounds, then the guessed key value is wrong since it caused an impossible condition that will never happen for the correct key. The attack proceeds as follows, with illustration in Figure 3: