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
In common usage and in philosophy, ideas are the results of thought. Also in philosophy, ideas can also be mental representational images of some object. Many philosophers have considered ideas to be a fundamental ontological category of bei ...
, though only with slight advantage over brute force. It has also been applied to the
KASUMI
Kasumi may refer to:
Places
* Kasumi, Hyōgo (香住), a former town in Hyōgo Prefecture, Japan
* Kasumigaseki (霞が関 "Gate of Mist"), a district in downtown Tokyo
* Kasumi, Jajce, a village in Bosnia and Herzegovina
Other uses
* Kasumi (gi ...
cipher and preimage resistance of the
Skein-512 and
SHA-2
SHA-2 (Secure Hash Algorithm 2) is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compression ...
hash functions.
The biclique attack is still () the best publicly known single-key attack on
AES. The computational complexity of the attack is
,
and
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
, 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.
History
The original MITM attack was first suggested by
Diffie and
Hellman Hellman is a surname. Notable people with the surname include:
* Åke Hellman (1915–2017), Finnish centenarian, painter, and art professor
*Bonnie Hellman (born 1950), American actress
*C. Doris Hellman (1910–1973), American historian of scienc ...
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
to just
, since one can independently bruteforce the first and the second DES-encryption if they have the plain- and ciphertext).
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
Dmitry Khovratovich
Dmitry Khovratovich is a cryptographer, currently a Lead Cryptographer for the Dusk Network, researcher for the Ethereum Foundation, and member of the International Association for Cryptologic Research. He developed, together with Alex Biryu ...
, 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 article for
bicliques.
In a MITM attack, the keybits
and
, belonging to the first and second subcipher, need to be independent; that is, they need to be independent of each other, else the matched intermediate values for the plain- and ciphertext cannot be computed independently in the MITM attack (there are variants of MITM attacks, where the blocks can have shared key-bits. See the
3-subset MITM attack). 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. 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
and
can map a certain intermediate state to the corresponding ciphertext.
How to build the biclique
Bruteforce
Get
intermediate states and
ciphertexts, then compute the keys that maps between them. This requires
key-recoveries, since each intermediate state needs to be linked to all ciphertexts.
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,
, to the ciphertext-values,
, based on the key