# Higher Order Integral Property

Written By:

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

### Idea #1

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

$c_0$ had the All Property. $c_i$ for $0<i \leq 15$ had Constant property.

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

$\forall$ $i$ in $0\leq i \leq15$ $c_i$ has the Balanced property.

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.

### Now,

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 Balanced property.

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

# AES 4-Round Distinguisher

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.

### Construction

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$.

## Now let's prepend one round to AES 3-round to make it 4 - rounds

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 the following,

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}$$

### Now the distinguisher,

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 )

#### Current State

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.

#### Step1. Inverse AddRoundKey

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

#### Step2. Inverse MixColumn

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

#### Step3. Inverse ShiftRow

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 All property. Hence after Inverse Shift Row, individual property is preserved.

#### Step4. Inverse SubBytes

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

#### Step5. XOR with boss key

No change in structure

## Conclusion

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 AES rounds have the balanced property in all the 16 bytes that is $$\bigoplus_{i=0}^{2^{32}-1}C_i[j]=0 , 0 \leq j \leq 15$$

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

### References

• Kazuo Sakiyama, Yu Sasaki, Yang Li-Security of Block Ciphers_ From Algorithm Design to Hardware Implementation-Wiley (2015)