Eurocrypt 2012: Bicliques and IDEA

Dmitry Khovratovich of Microsoft Research UK gave an interesting talk in the Eurocrypt session on symmetric cryptanalysis entitled Narrow-Bicliques: Cryptanalysis of Full IDEA, which is joint work with Gaetan Leurent, and Christian Rechberger. The work is an extension of previous research from Khovratovich on attacking AES (pdf), both in terms of strategy, by discussing an enhancement in the application of the bicliques, and in terms of target; shifting focus from AES to the block cipher IDEA. The initial result on AES was notable for providing the first faster-than-brute-force attack on the full versions of AES-128,-192,and -256. The strategy defines a meet-in-the-middle attack on the block cipher, enhanced in power by the concept of bicliques.

Meet-in-the-middle (MITM) attacks using bicliques were initially evaluated in the context of hash function cryptanalysis. The basic premise is to split an invertible transformation into two parts, with selected parameters affecting only one of the two parts. The parameter space can be searched exhaustively, with matching 'middle' values for the two parts indicating that the parameters were chosen correctly (see the MITM attack on double-DES as a basic example). The difficulty in an application to block cipher rounds is identifying a sequence of rounds that are not dependent on a particular key bit; prominent modern block ciphers typically utilise the full key in the first few rounds.

The application of the biclique essentially extends the beginning or end of the meet-in-the-middle attack to help overcome this difficulty. A biclique itself is a set of internal states constructed in the first or last rounds of the block cipher, mapped to each other by specific keys. The speed-up over brute-force comes from being able to split up the key-space into equally-sized groups, which are tested using a meet-in-the-middle strategy. The 'narrowness' lending to this paper's name comes from an observations that allows the authors to reduce the diffusion of differential trails in the cipher, and as a result reduce the data complexity of an attack.

IDEA was designed in 1991 by Lai and Massey. It has an 128-bit key, and has 8.5 rounds in full. There are two narrow biclique attacks presented that target the full 8.5 rounds, the first with data complexity of 2⁵² and complexity 2^126.06, and the second with data complexity of 2⁵⁹ and complexity 2^125.97. Both require negiible amounts of memory.

An interesting observation is that whilst the biclique attacks on IDEA presented here do not in any way threaten the practical use of the cipher, they do surpass the efficiency of known attacks so far, and so indicate that there may be potential for similar approaches to do significantly better than a brute-force attack. A second notable observation is that a countermeasure against such attacks is likely to require expensive key-scheduling designs.