Jun 08, 2020

Higher Order Integral Property

Written By: Ahaan Dabholkar, Aikata

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.

AES State

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

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

How is this property ensured -


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.


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:-


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 ?

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

Inverse AddRoundKey

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

Inverse MixColumn

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.

Inverse ShiftRow

Step4. Inverse SubBytes

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

Inverse SubBytes

Step5. XOR with boss key

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


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