Previous | Table of Contents | Next |
Decryption is exactly the same, except that the subkeys are reversed and slightly different. The decryption subkeys are either the additive or multiplicative inverses of the encryption subkeys. (For the purposes of IDEA, the all-zero sub-block is considered to represent 2^{16} = – 1 for multiplication modulo 2^{16} + 1; thus the multiplicative inverse of 0 is 0.) Calculating these takes some doing, but you only have to do it once for each decryption key. Table 13.4 shows the encryption subkeys and the corresponding decryption subkeys.
Speed of IDEA
Current software implementations of IDEA are about twice as fast as DES. IDEA on a 33 megahertz 386 machine encrypts data at 880 kilobits per second, and 2400 kilobits per second on a 66 megahertz 486 machine. You might think IDEA should be faster, but multiplications aren’t cheap. To multiply two 32-bit numbers on a 486 requires 40 clock cycles (10 on a Pentium).
A VLSI implementation of PES encrypts data at 55 megabits per second at 25 megahertz [208, 398]. Another VLSI chip developed at ETH Zurich, consisting of 251, 000 transistors on a chip 107.8 square millimeters, encrypts data using the IDEA algorithm at a 177 megabit-per-second data rate when clocked at 25 megahertz [926, 207, 397].
Table 13.4 IDEA Encryption and Decryption Subkeys | ||
---|---|---|
Round | Encryption Subkeys | Decryption Subkeys |
1st | Z_{1}^{(1)} Z_{2}^{(1)} Z_{3}^{(1)} Z_{4}^{(1)} Z_{5}^{(1)} Z_{6}^{(1)} | Z_{1}^{(9) - 1} –Z_{2}^{(9)} –Z_{3}^{(9)} Z_{4}^{(9) - 1} Z_{5}^{(8)} Z_{6}^{(8)} |
2nd | Z_{1}^{(2)} Z_{2}^{(2)} Z_{3}^{(2)} Z_{4}^{(2)} Z_{5}^{(2)} Z_{6}^{(2)} | Z_{1}^{(8) - 1} –Z_{3}^{(8)} –Z_{2}^{(8)} Z_{4}^{(8) - 1} Z_{5}^{(7)} Z_{6}^{(7)} |
3rd | Z_{1}^{(3)} Z_{2}^{(3)} Z_{3}^{(3)} Z_{4}^{(3)} Z_{5}^{(3)} Z_{6}^{(3)} | Z_{1}^{(7) - 1} –Z_{3}^{(7)} –Z_{2}^{(7)} Z_{4}^{(7) - 1} Z_{5}^{(6)} Z_{6}^{(6)} |
4th | Z_{1}^{(4)} Z_{2}^{(4)} Z_{3}^{(4)} Z_{4}^{(4)} Z_{5}^{(4)} Z_{6}^{(4)} | Z_{1}^{(6) - 1} –Z_{3}^{(6)} –Z_{2}^{(6)} Z_{4}^{(6) - 1} Z_{5}^{(5)} Z_{6}^{(5)} |
5th | Z_{1}^{(5)} Z_{2}^{(5)} Z_{3}^{(5)} Z_{4}^{(5)} Z_{5}^{(5)} Z_{6}^{(5)} | Z_{1}^{(5) - 1} –Z_{3}^{(5)} –Z_{2}^{(5)} Z_{4}^{(5) - 1} Z_{5}^{5(4)} Z_{6}^{(4)} |
6th | Z_{1}^{(6)} Z_{2}^{(6)} Z_{3}^{(6)} Z_{4}^{(6)} Z_{5}^{(6)} Z_{6}^{(6)} | Z_{1}^{(4) - 1} –Z_{3}^{(4)} –Z_{2}^{(4)} Z_{4}^{(4) - 1} Z_{5}^{(3)} Z_{6}^{(3)} |
7th | Z_{1}^{(7)} Z_{2}^{(7)} Z_{3}^{(7)} Z_{4}^{(7)} Z_{5}^{(7)} Z_{6}^{(7)} | Z_{1}^{(3) - 1} –Z_{3}^{(3)} –Z_{2}^{(3)} Z_{4}^{(3) - 1} Z_{5}^{(2)} Z_{6}^{(2)} |
8th | Z_{1}^{(8)} Z_{2}^{(8)} Z_{3}^{(8)} Z_{4}^{(8)} Z_{5}^{(8)} Z_{6}^{(8)} | Z_{1}^{(2) - 1} –Z_{3}^{(2)} –Z_{2}^{(2)} Z_{4}^{(2) - 1} Z_{5}^{(1)} Z_{6}^{(1)} |
output transformation | Z_{1}^{(9)} Z_{2}^{(9)} Z_{3}^{(9)} Z_{4}^{(9)} | Z_{1}^{(1) - 1} –Z_{2}^{(1)} –Z_{3}^{(1)} Z_{4}^{(1) - 1} |
Cryptanalysis of IDEA
IDEA’s key length is 128 bits—over twice as long as DES. Assuming that a brute-force attack is the most efficient, it would require 2^{128}(10^{38}) encryptions to recover the key. Design a chip that can test a billion keys per second and throw a billion of them at the problem, and it will still take 10^{13} years—that’s longer than the age of the universe. An array of 10^{24} such chips can find the key in a day, but there aren’t enough silicon atoms in the universe to build such a machine. Now we’re getting somewhere—although I’d keep my eye on the dark matter debate.
Perhaps brute force isn’t the best way to attack IDEA. The algorithm is still too new for any definitive cryptanalytic results. The designers have done their best to make the algorithm immune to differential cryptanalysis; they defined the concept of a Markov cipher and showed that resistance to differential cryptanalysis can be modeled and quantified [931, 925]. (Figure 13.10 shows the original PES algorithm to be contrasted with the IDEA algorithm of Figure 13.9 which was strengthened against differential cryptanalysis. It’s amazing how a few subtle changes can make such a big difference.) In [925], Lai argued (he gave evidence, not a proof) that IDEA is immune to differential cryptanalysis after only 4 of its 8 rounds. According to Biham, his related-key cryptanalytic attack doesn’t work against IDEA, either [160].
Willi Meier examined the three algebraic operations of IDEA, and pointed out that while they are incompatible, there are instances where they can be simplified in such a way as to facilitate cryptanalysis some percentage of the time [1050]. His attack is more efficient than brute-force for 2-round IDEA (2^{42} operations), but less efficient for 3-round IDEA or higher. Normal IDEA, with 8 rounds, is safe.
Joan Daemen discovered a class of weak keys for IDEA [406, 409]. These are not weak keys in the sense of the DES weak keys; that is, the encryption function is self-inverse. They are weak in the sense that if they are used, an attacker can easily identify them in a chosen-plaintext attack. For example, a weak key is (in hex):
Previous | Table of Contents | Next |