Written By:

The idea of creating a distinguisher based on the HOIP is based on the following -

Recall the integral property of AES. We used to consider a set $P$ of $256$ plaintexts with the following properties.

$c_0$ had the

AllProperty. $c_i$ for $0<i \leq 15$ hadConstantproperty.

Then after applying **AES 3-round** on $P$ we observed the following-

$\forall$ $i$ in $0\leq i \leq15$ $c_i$ has the

Balancedproperty.

Now consider the following: Suppose I generate 2 sets of plaintexts $P_1$ and $P_2$ according to the following rules

- In $P_1$ byte position $1$ i.e. $c_1 = 0$ while $c_0$ takes all $256$ values.
- In $P_2$ byte position $2$ i.e. $c_2 = 0$ while $c_0$ takes all $256$ values.

Now apply **AES 3-round** on $P_1$ and $P_2$ to obtain $C_1$ and $C_2$ ( sets of 256 ciphertexts each )
We observe that both $C_1$ and $C_2$ show **Balanced** property.

If I mix the two sets $C_1$ and $C_2$ without caring for the order, the new set $C_{12}$ of $512$ texts will still show the

Balancedproperty.

How is this property ensured -

- $\oplus$ sum of $C_1 = 0$
- $\oplus$ sum of $C_2 = 0$
- $\implies$ $\oplus$ of $C_1 \: and \:C_2 = 0$ even without knowing which ciphertext belongs to which set.

Now lets try building a distinguisher for **AES 4-round**

First things first.

What's a

distinguisher? Ideally a cipher should behave as a random output generator. However if we can find a construction which differentiates the output of a cipher from a random output, then we call it a distinguisher.

Lets first take $2^{24}$ sets of plaintexts $P_0, P_1, P_2, ...$*( why ? Ill answer it later )*, where each set has $256$ plaintexts.
Each set is generated as follows:-

- For $P_0$ the value of $c_1 || c_2 || c_3$ is fixed to $0$, $c_0$ takes all $256$ possibilities. ($c_1, c_2$ is byte position 1 and 2 respectively)
- For $P_1$ the value of $c_1 || c_2 || c_3$ is fixed to $1$, $c_0$ takes all $256$ possibilities.
- ...
- For $P_{2^{24} - 1}$ the value of $c_1 || c_2 || c_3$ is fixed to $2^{24} - 1$, $c_0$ takes all $256$ possibilities.

Thus total no. of plaintexts is $2^{24}. 256 = 2^{32}$

Also let $P = \{P_0, P_1,P_2, ... ,P_{2^{24}-1}\}$

Now apply **AES 3-round** on all plaintexts and obtain corresponding ciphertexts.
From previous discussion, each set of ciphertexts shows **balanced** property.
Hence, the $\oplus$ sum of all $2^{24}$ sets is also $0$.

Just to recap, what did we do ?

- Constructed $2^{24}$ sets of $256$ plaintexts according to
*some rules* - Encrypted the plaintexts using AES 3-rounds
- Mixed all of the $2^{24}$ sets together to get a set of $2^{32}$ matrices which show the
**balanced**property ( i.e. $\oplus$ sum$=0$ )

Consider all the $2^{32}$ plaintexts i.e. $P$ as $1$ set. From our construction, $c_1 || c_2 || c_3$ takes all possible values.

$c_1 || c_2 || c_3$ is 3 bytes and therefore can have $2^{24}$ distinct values. We took care of this during the construction of $P$ remember !!!

We also know that in set $P_i$, $c_0$ shows **All** property

Thus if we consider $c_0 || c_1 || c_2 || c_3$ ( the first column ) in $P$, it takes all possible $2^{32}$ values. And that is why we had taken $2^{24}$ sets of plaintexts in the beginning !!!

Lets take an example to understand this, Look at just the first column Corresponding to $c_0=0$ we have all $2^{24}$ values in the lower part of the column ( from the other sets ) Corresponding to $c_0=1$ we have all $2^{24}$ values in the lower part of the column ( from the other sets )

Thus as $c_0$ can take $2^{8}$ values and corresponding to each value we have $2^{24}$ values. Thus, by multiplication rule $$Total \:values = 2^8.2^{24} = 2^{32}$$

At this point of time we have with us $P$ which is a set of $2^{32}$ plaintexts in which the first column takes all $2^{32}$ possible values. Let us take $P$ and observe what happens to it when we compute it in the backward direction ( refer to figure )

We have the state matrix in which the first column takes all $2^{32}$ possible values. ( represented by purple color ). The fig shows the state as well as the AES round.

XOR does not change the structure of the state matrix as it is a *bijective mapping* from $byte \rightarrow byte$.

This too does not change the structure of the state matrix as it is a *bijective mapping* from $4\:bytes \rightarrow 4\:bytes$.

This **does** change the structure, but as it is simply *bitewise* relocation, the **individual property of the byte does not change.**

We know that the first column takes all possible values. Since each byte in the column can have only 256 values, each value is repeated $2^{24}$ times. Thus we can say that each position in the column individually shows

Allproperty. Hence after Inverse Shift Row, individual property is preserved.

Again its a bijective mapping. Therefore no change in structure.

No change in structure

Now we have our distinguisher.

Let $P$ be a set of $2^{32}$ plaintexts in which the byte positions $0, 5, 10, and \:15$ take all possible values, and the other bytes take a fixed value. The corresponding $2^{32}$ states $C_0 , C_1 , . . . , C_{2^{32} −1}$ after four

AESrounds have thebalanced property in all the 16 bytesthat is $$\bigoplus_{i=0}^{2^{32}-1}C_i[j]=0 , 0 \leq j \leq 15$$

</div> </div> </div>