Cryptography Reference
In-Depth Information
5.3.5 Cryptanalyzing IDEA
After these impressive and theoretically underpinned properties of this algo-
rithm, you'll not be surprised to hear that so far the most successful attacks
against IDEA have become stuck after 3.5 rounds (where the output transfor-
mation is counted as half a round). The method is optimized against differential
cryptanalysis; Lai thinks that it is resistant to this attack after only four rounds.
And an attempted attack with related keys by Biham also failed.
There are
weak keys
in the sense that their use by foisting chosen plaintexts can
be proved, which could be interesting for chip cards with a 'burnt-in key'. First
of all, however, these keys can be easily avoided — one only needs to XOR
all subkeys with the hexadecimal number 0x0dae — and second, the probability
that such a key can be caught is 2
−
96
; that is about one out of 10
29
randomly
selected keys (this number even has a name: 100 quadrilliards).
An effective cryptanalysis was presented by Philip Hawkes at the EURO-
CRYPT '98 [HawIDEA]. Hawkes discovered 265 weak keys for which roughly
20 chosen plaintexts would suffice to recover 72 bits of the key. The remaining
56 bits are then recovered by brute force — a cost comparable to cryptana-
lyzing DES. This means for an attacker that he can fire up his IDEA crack
machine (which is slightly larger and slower than his DES crack machine)
every 9 trillion (9 000 000 000 000 000 000) sessions he listened in on to com-
pute the key. This doesn't sound particularly dangerous. Nevertheless, Hawkes
recommends changing IDEA's key generation system. This is no paranoia — the
next cryptanalytic improvement could be more effective.
Another attack was demonstrated by Borst, Knudsen, and Rijmen at the EURO-
CRYPT '97 [BorstIDEA], but only against a 3.5-round IDEA (i.e., three rounds
plus final transformation). In about 5/6 of all cases, this attack finds the key
using 2
56
chosen plaintexts (accordingly more than 500 000 terabytes of plain-
text). Though the authors assume that this attack could be mounted more
effectively, they doubt whether it would change the security of the full 8.5-
round IDEA. In his work mentioned above [HawIDEA], Hawkes studied a
4-round IDEA. With a little less than 40 chosen plaintexts, he recovered 15
bits of the key, which is only of theoretical interest for the time being.
It would be absolutely hopeless to ever want to brute-force IDEA. With a key
length of 128 bits, this belongs to the realm of science-fiction movies (see also
'Brute Force' entry in the Glossary and Section 5.9).
