Biclique attack

Uses your system voice; voice and rate in settings.

Snapshot

≈ 7 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

A biclique attack is a variant of the meet-in-the-middle (MITM ) method of cryptanalysis. It utilizes a biclique structure to extend the number of possibly attacked rounds by the MITM attack. Since biclique cryptanalysis is based on MITM attacks, it is applicable to both block ciphers and (iterated) hash-functions.

Biclique attacks are known for having weakened both full AES and full IDEA, though only with slight advantage over brute force. It has also been applied to the KASUMI cipher and preimage resistance of the Skein-512 and SHA-2 hash functions. The biclique attack is still ( ) the best publicly known single-key attack on AES.

The computational complexity of the attack is 2^{126.1} , 2^{189.7} and 2^{254.4} for AES128, AES192 and AES256, respectively. It is the only publicly known single-key attack on AES that attacks the full number of rounds. Previous attacks have attacked round reduced variants (typically variants reduced to 7 or 8 rounds).

As the computational complexity of the attack is 2^{126.1} , it is a theoretical attack, which means the security of AES has not been broken, and the use of AES remains relatively secure. The biclique attack is nevertheless an interesting attack, which suggests a new approach to performing cryptanalysis on block ciphers.…

A biclique attack is a variant of the meet-in-the-middle (MITM ) method of cryptanalysis. It utilizes a biclique structure to extend the number of possibly attacked rounds by the MITM attack. Since biclique cryptanalysis is based on MITM attacks, it is applicable to both block ciphers and (iterated) hash-functions.

Biclique attacks are known for having weakened both full AES and full IDEA, though only with slight advantage over brute force. It has also been applied to the KASUMI cipher and preimage resistance of the Skein-512 and SHA-2 hash functions. The biclique attack is still ( ) the best publicly known single-key attack on AES.

The computational complexity of the attack is 2^{126.1} , 2^{189.7} and 2^{254.4} for AES128, AES192 and AES256, respectively. It is the only publicly known single-key attack on AES that attacks the full number of rounds. Previous attacks have attacked round reduced variants (typically variants reduced to 7 or 8 rounds).

As the computational complexity of the attack is 2^{126.1} , it is a theoretical attack, which means the security of AES has not been broken, and the use of AES remains relatively secure. The biclique attack is nevertheless an interesting attack, which suggests a new approach to performing cryptanalysis on block ciphers.

The attack has also rendered more information about AES, as it has brought into question the safety-margin in the number of rounds used therein. This mapping process requires (2^d)_{\text{number of intermediate states}} \cdot (2^d)_{\text{num of ciphertexts per intermed. st.}} = 2^{d+d} = 2^{2d} key-recoveries, since each intermediate state needs to be linked to all ciphertexts (not to just one ciphertext).

Step three: Since the trails do not share any non-linear components (e.g., trails not sharing any S-boxes), the trails can be combined to get: 0\xrightarrow[f]{\Delta^K_i}\Delta_i \oplus \nabla_j \xrightarrow[f]{\nabla^K_j}0 = \nabla_j \xrightarrow[f]{\Delta^K_i \oplus \nabla^K_j}\Delta_i , which conforms to the definitions of both the differentials from step 2. It is trivial to see that the tuple (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 S_0, C_0 K[0,0] into any of the two definitions, will yield 0\xrightarrow[f]{0}0 since \Delta_0 = 0, \nabla_0 = 0 and \Delta^K_0 = 0 . This means that the tuple of the base computation, can also be XOR'ed to the combined trails: S_0 \oplus \nabla_j \xrightarrow[f]{K[0,0] \oplus \Delta^K_i \oplus \nabla^K_j}C_0 \oplus \Delta_i Step four: It is trivial to see that: S_j = S_0 \oplus \nabla_j K[i,j] = K[0,0] \oplus \Delta^K_i \oplus \nabla^K_j C_i = C_0 \oplus \Delta_i If this is substituted into the above combined differential trails, the result will be: S_j \xrightarrow[f]{K[i,j]}C_i \forall i,j : S_j \xrightarrow[f]{K[i,j]}C_i It is thus possible to create a biclique of size 2^{2d} ( 2^{2d} since all 2^d keys of the first set of keys, can be combined with the 2^d keys from the second set of keys).

This means a biclique of size 2^{2d} can be created using only 2*2^d computations of the differentials \Delta_i and \nabla_j over f . If \Delta_i \neq \nabla_j for i+j>0 then all of the keys 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.

Step one: The attacker groups all possible keys into key-subsets of size 2^{2d} for some d , where the key in a group is indexed as K[i,j] in a matrix of size 2^d \times 2^d . The attacker splits the cipher into two sub-ciphers, f and g (such that E = f \circ g ), as in a normal MITM attack. The set of keys for each of the sub-ciphers is of cardinality 2^d , and is called K[i,0] and K[0,j] . The combined key of the sub-ciphers is expressed with the aforementioned matrix K[i, j] . Step two: The attacker builds a biclique for each group of 2^{2d} keys.

The biclique is of dimension-d, since it maps 2^d internal states, S_j , to 2^d ciphertexts, C_i , using 2^{2d} keys. The section "How to build the biclique" suggests how to build the biclique using "Independent related-key differentials". The biclique is in that case built using the differentials of the set of keys, K[i,0] and K[0,j] , belonging to the sub-ciphers.

Step three: The attacker takes the 2^d possible ciphertexts, C_i , and asks a decryption-oracle to provide the matching plaintexts, P_i . Step four: The attacker chooses an internal state, S_j and the corresponding plaintext, P_i , and performs the usual MITM attack over f and g by attacking from the internal state and the plaintext. Step five: Whenever a key-candidate is found that matches S_j with P_i , that key is tested on another plain-/ciphertext pair. if the key validates on the other pair, it is highly likely that it is the correct key.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1361808240 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

5 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.