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 broken 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.
Contents
- History
- The biclique
- Bruteforce
- Independent related key differentials
- Other ways of constructing the biclique
- Biclique Cryptanalysis procedure
- Example attack
- Key partitioning
- Biclique construction
- MITM attack
- Results
- References
The biclique attack is still the best publicly known single-key attack on AES. The computational complexity of the attack is
As the computational complexity of the attack is
History
The original MITM attack was first suggested by Diffie and Hellman in 1977, when they discussed the cryptanalytic properties of DES. They argued that the key-size was too small, and that reapplying DES multiple times with different keys could be a solution to the key-size; however, they advised against using double-DES and suggested triple-DES as a minimum, due to MITM attacks (MITM attacks can easily be applied to double-DES to reduce the security from
Since Diffie and Hellman suggested MITM attacks, many variations have emerged that are useful in situations, where the basic MITM attack is inapplicable. The biclique attack variant was first suggested by Khovratovich, Rechberger and Savelieva for use with hash-function cryptanalysis. However, it was Bogdanov, Khovratovich and Rechberger who showed how to apply the concept of bicliques to the secret-key setting including block-cipher cryptanalysis, when they published their attack on AES. Prior to this, MITM attacks on AES and many other block ciphers had received little attention, mostly due to the need for independent key bits between the two 'MITM subciphers' in order to facilitate the MITM attack — something that is hard to achieve with many modern key schedules, such as that of AES.
The biclique
For a general explanation of what a biclique structure is, see the wiki-page for bicliques.
In a MITM attack, the keybits
Simply put: The more rounds you attack, the larger subciphers you will have. The larger subciphers you have, the fewer independent key-bits between the subciphers you will have to bruteforce independently. Of course, the actual number of independent key-bits in each subcipher depends on the diffusion properties of the key-schedule.
The way the biclique helps with tackling the above, is that it allows one to - for instance - attack 7 rounds of AES using MITM attacks, and then by utilizing a biclique structure of length 3 (i.e. it covers 3 rounds of the cipher), you can map the intermediate state at the start of round 7 to the end of the last round, e.g. 10 (if it is AES128), thus attacking the full number of rounds of the cipher, even if it was not possible to attack that amount of rounds with a basic MITM attack.
The meaning of the biclique is thus to build a structure effectively, which can map an intermediate value at the end of the MITM attack to the ciphertext at the end. Which ciphertext the intermediate state gets mapped to at the end, of course depends on the key used for the encryption. The key used to map the state to the ciphertext in the biclique, is based on the keybits bruteforced in the first and second subcipher of the MITM attack.
The essence of biclique attacks is thus, besides the MITM attack, to be able to build a biclique structure effectively, that depending on the keybits
Bruteforce
Get
Independent related-key differentials
(This method was suggested by Bogdanov, Khovratovich and Rechberger in their paper: Biclique Cryptanalysis of the Full AES)
Preliminary:
Remember that the function of the biclique is to map the intermediate values,
Procedure:
Step one: An intermediate state(
Step two: Two sets of related keys of size
In other words:
An input difference of 0 should map to an output difference of
An input difference of
Step three: Since the trails do not share any non-linear components (such as S-boxes), the trails can be combined to get:
which conforms to the definitions of both the differentials from step 2.
It is trivial to see that the tuple
This means that the tuple of the base computation, can also be XOR'ed to the combined trails:
Step four: It is trivial to see that:
If this is substituted into the above combined differential trails, the result will be:
Which is the same as the definition, there was earlier had above for a biclique:
It is thus possible to create a biclique of size
This way is how the biclique is constructed in the leading biclique attack on AES. It should be noted that 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.
Other ways 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".
Biclique Cryptanalysis procedure
Step one: The attacker groups all possible keys into key-subsets of size
Step two: The attacker builds a biclique for each group of
Step three: The attacker takes the
Step four: The attacker chooses an internal state,
Step five: Whenever a key-candidate is found that matches
Example attack
The following example is based on the biclique attack on AES from the paper "Biclique Cryptanalysis of the Full AES".
The descriptions in the example uses the same terminology that the authors of the attack used (i.e. for variable names, etc).
For simplicity it is the attack on the AES128 variant that is covered below.
The attack consists of a 7-round MITM attack with the biclique covering the last 3 rounds.
Key partitioning
The key-space is partitioned into
For each of the
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):
The remaining 14 bytes (112 bits) of the key is then enumerated. This yields
The ordinary
This gives
Biclique construction
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
MITM attack
When the bicliques are created, the MITM attack can almost begin. Before doing the MITM attack, the
the
and the corresponding intermediate states and sub-keys
Now the MITM attack can be carried out. In order to test a key
When the intermediate values match, a key-candidate
Results
This attack lowers the computational complexity of AES128 to