A biclique attack is a variant of the meet-in-the-middle (MITM) method of cryptanalysis.
Since biclique cryptanalysis is based on MITM attacks, it is applicable to both block ciphers and (iterated) hash-functions.
It has also been applied to the KASUMI cipher and preimage resistance of the Skein-512 and SHA-2 hash functions.
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.
The original MITM attack was first suggested by Diffie and Hellman in 1977, when they discussed the cryptanalytic properties of DES.
[4] 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
The biclique attack variant was first suggested by Dmitry Khovratovich, Rechberger and Savelieva for use with hash-function cryptanalysis.
[5] 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.
This property is often hard to exploit over a larger number of rounds, due to the diffusion of the attacked cipher.
Simply put: The more rounds you attack, the larger subciphers you will have.
Of course, the actual number of independent key-bits in each subcipher depends on the diffusion properties of the key-schedule.
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.
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,
is the function that maps an intermediate state to a ciphertext using a given key.
This means that the tuple of the base computation, can also be XOR'ed to the combined trails:
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]".
Step one: The attacker groups all possible keys into key-subsets of size
The combined key of the sub-ciphers is expressed with the aforementioned matrix
The biclique is in that case built using the differentials of the set of keys,
The descriptions in the example uses the same terminology that the authors of the attack used (i.e. for variable names, etc).
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.
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.
never share any active S-boxes (which is the only non-linear component in AES), with the differential trails
It is therefore possible to XOR the differential trails and create the biclique.
, 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).