20 Crypto-Years After…

The event has been completely unnoticed, but I think it is worth to come back on it, as it is now part of the crypto history: the European patent protecting the IDEA (International Data Encryption Algorithm) block cipher has expired a few days ago, on May 16th, 2011, and hence felt into the public domain. Note however that, according to its Wikipedia page, the cipher is still protected in the US until January 7th, 2012.

IDEA is really an amazing block cipher and definitely deserves a seat in the Crypto Hall of Fame. IDEA has been designed by James L. Massey and his PhD student Xuejia Lai at ETH Zurich on behalf of the Swiss company Ascom Tech AG. The IDEA block cipher has been implemented in a variety of applications, including PGP.

Technically, IDEA can encrypt blocks of 64 bits under a 128-bit key. Its design rely on a simple, but very clever idea (!): mix three algebraically incompatible group operations on 16-bit words:

  • the addition \oplus of vectors in \mathrm{GF}(2)^{16}, which can actually be computed using a simple XOR;
  • the addition \boxplus of 16-bit words modulo 2^{16};
  • the multiplication \odot used in the multiplicative group of \mathrm{GF}(2^{16}+1), where the word 0x0000 is identified with the integer 2^{16}.

One salient feature of the IDEA block cipher is that, despite its (too) simple key-schedule, it has withstood 20 years of intense cryptanalysis, and IDEA is therefore a prominent counter-example to Shamir‘s law (“A cipher is generally broken after 13 years”, or something approaching). In summary, IDEA remains a very nice piece of engineering !