Biclique attack

Get ${\displaystyle 2^{d}}$ intermediate states and ${\displaystyle 2^{d}}$ ciphertexts, then compute the keys that maps between them. This requires ${\displaystyle 2^{2d}}$ key-recoveries, since each intermediate state needs to be linked to all ciphertexts.

(This method was suggested by Bogdanov, Khovratovich and Rechberger in their paper: Biclique Cryptanalysis of the Full AES[1])

Preliminary:
Remember that the function of the biclique is to map the intermediate values, ${\displaystyle S}$, to the ciphertext-values, ${\displaystyle C}$, based on the key ${\displaystyle K[i,j]}$ such that:
${\displaystyle \forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

Procedure:
Step one: An intermediate state(${\displaystyle S_{0}}$), a ciphertext(${\displaystyle C_{0}}$) and a key(${\displaystyle K[0,0]}$) is chosen such that: ${\displaystyle S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}}$, where ${\displaystyle f}$ is the function that maps an intermediate state to a ciphertext using a given key. This is denoted as the base computation.

Step two: Two sets of related keys of size ${\displaystyle 2^{d}}$ is chosen. The keys are chosen such that:

• The first set of keys are keys, which fulfills the following differential-requirements over ${\displaystyle f}$ with respect to the base computation: ${\displaystyle 0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}}$
• The second set of keys are keys, which fulfills the following differential-requirements over ${\displaystyle f}$ with respect to the base computation: ${\displaystyle \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0}$
• The keys are chosen such that the trails of the ${\displaystyle \Delta _{i}}$- and ${\displaystyle \nabla _{j}}$-differentials are independent – i.e. they do not share any active non-linear components.

In other words:
An input difference of 0 should map to an output difference of ${\displaystyle \Delta _{i}}$ under a key difference of ${\displaystyle \Delta _{i}^{K}}$. All differences are in respect to the base computation.
An input difference of ${\displaystyle \nabla _{j}}$ should map to an output difference of 0 under a key difference of ${\displaystyle \nabla _{J}^{K}}$. All differences are in respect to the base computation.

Step three: Since the trails do not share any non-linear components (such as S-boxes), the trails can be combined to get:
${\displaystyle 0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}}$,
which conforms to the definitions of both the differentials from step 2.
It is trivial to see that the tuple ${\displaystyle (S_{0},C_{0},K[0,0])}$ from the base computation, also conforms by definition to both the differentials, as the differentials are in respect to the base computation. Substituting ${\displaystyle S_{0},C_{0}}$ ${\displaystyle K[0,0]}$ into any of the two definitions, will yield ${\displaystyle 0{\xrightarrow[{f}]{0}}0}$ since ${\displaystyle \Delta _{0}=0,\nabla _{0}=0}$ and ${\displaystyle \Delta _{0}^{K}=0}$.
This means that the tuple of the base computation, can also be XOR'ed to the combined trails: ${\displaystyle S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}}$

Step four: It is trivial to see that:
${\displaystyle S_{j}=S_{0}\oplus \nabla _{j}}$
${\displaystyle K[i,j]=K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}$
${\displaystyle C_{i}=C_{0}\oplus \Delta _{i}}$
If this is substituted into the above combined differential trails, the result will be:
${\displaystyle S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$
Which is the same as the definition, there was earlier had above for a biclique:
${\displaystyle \forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

It is thus possible to create a biclique of size ${\displaystyle 2^{2d}}$ (${\displaystyle 2^{2d}}$ since all ${\displaystyle 2^{d}}$ keys of the first set of keys, can be combined with the ${\displaystyle 2^{d}}$ keys from the second set of keys). This means a biclique of size ${\displaystyle 2^{2d}}$ can be created using only ${\displaystyle 2*2^{d}}$ computations of the differentials ${\displaystyle \Delta _{i}}$ and ${\displaystyle \nabla _{j}}$ over ${\displaystyle f}$. If ${\displaystyle \Delta _{i}\neq \nabla _{j}}$ for ${\displaystyle i+j>0}$ then all of the keys ${\displaystyle K[i,j]}$ will also be different in the biclique.

This way is how the biclique is constructed in the leading biclique attack on AES. There are some practical limitations in constructing bicliques with this technique. The longer the biclique is, the more rounds the differential trails has to cover. The diffusion properties of the cipher, thus plays a crucial role in the effectiveness of constructing the biclique.

Bogdanov, Khovratovich and Rechberger also describe another way to construct the biclique, called 'Interleaving Related-Key Differential Trails' in the article: "Biclique Cryptanalysis of the Full AES[1]".

The key-space is partitioned into ${\displaystyle 2^{112}}$ groups of keys, where each group consist of ${\displaystyle 2^{16}}$ keys.
For each of the ${\displaystyle 2^{112}}$ groups, a unique base-key ${\displaystyle K[0,0]}$ for the base-computation is selected.
The base-key has two specific bytes set to zero, shown in the below table (which represents the key the same way AES does in a 4x4 matrix for AES128):

${\displaystyle {\begin{bmatrix}-&-&-&0\\0&-&-&-\\-&-&-&-\\-&-&-&-\end{bmatrix}}}$

The remaining 14 bytes (112 bits) of the key is then enumerated. This yields ${\displaystyle 2^{112}}$ unique base-keys; one for each group of keys.
The ordinary ${\displaystyle 2^{16}}$ keys in each group is then chosen with respect to their base-key. They are chosen such that they are nearly identical to the base-key. They only vary in 2 bytes (either the ${\displaystyle i}$'s or the ${\displaystyle j}$'s) of the below shown 4 bytes:

${\displaystyle {\begin{bmatrix}-&-&i&i\\j&-&j&-\\-&-&-&-\\-&-&-&-\end{bmatrix}}}$

This gives ${\displaystyle 2^{8}K[i,0]}$ and ${\displaystyle 2^{8}K[0,j]}$, which combined gives ${\displaystyle 2^{16}}$ different keys, ${\displaystyle K[i,j]}$. these ${\displaystyle 2^{16}}$ keys constitute the keys in the group for a respective base key.

${\displaystyle 2^{112}}$ bicliques is constructed using the "Independent related-key differentials" technique, as described in the "How to construct the biclique" section.
The requirement for using that technique, was that the forward- and backward-differential trails that need to be combined, did not share any active non-linear elements. How is it known that this is the case?
Due to the way the keys in step 1 is chosen in relation to the base key, the differential trails ${\displaystyle \Delta _{i}}$ using the keys ${\displaystyle K[i,0]}$ never share any active S-boxes (which is the only non-linear component in AES), with the differential trails ${\displaystyle \nabla _{j}}$ using the key ${\displaystyle K[0,j]}$. It is therefore possible to XOR the differential trails and create the biclique.

When the bicliques are created, the MITM attack can almost begin. Before doing the MITM attack, the ${\displaystyle 2^{d}}$ intermediate values from the plaintext:
${\displaystyle P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}}$,
the ${\displaystyle 2^{d}}$ intermediate values from the ciphertext:
${\displaystyle {\xleftarrow[{v_{j}}]{}}{\xleftarrow[{}]{K[0,j]}}S_{j}}$,
and the corresponding intermediate states and sub-keys ${\displaystyle K[i,0]}$ or ${\displaystyle K[0,j]}$, are precomputed and stored, however.

Now the MITM attack can be carried out. In order to test a key ${\displaystyle K[i,j]}$, it is only necessary to recalculate the parts of the cipher, which is known will vary between ${\displaystyle P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}}$ and ${\displaystyle P_{i}{\xrightarrow[{}]{K[i,j]}}{\xrightarrow[{v_{i}}]{}}}$. For the backward computation from ${\displaystyle S_{j}}$ to ${\displaystyle {\xleftarrow[{v_{j}}]{}}}$, this is 4 S-boxes that needs to be recomputed. For the forwards computation from ${\displaystyle P_{i}}$ to ${\displaystyle {\xrightarrow[{v_{i}}]{}}}$, it is just 3 (an in-depth explanation for the amount of needed recalculation can be found in "Biclique Cryptanalysis of the full AES[1]" paper, where this example is taken from).

When the intermediate values match, a key-candidate ${\displaystyle K[i,j]}$ between ${\displaystyle P_{i}}$ and ${\displaystyle S_{j}}$ is found. The key-candidate is then tested on another plain-/ciphertext pair.

This attack lowers the computational complexity of AES128 to ${\displaystyle 2^{126.18}}$, which is 3–5 times faster than a bruteforce approach. The data complexity of the attack is ${\displaystyle 2^{88}}$ and the memory complexity is ${\displaystyle 2^{8}}$.