APPLIED CRYPTOGRAPHY, SECOND EDITION: Protocols, Algorithms, and Source Code in C:Other Block Ciphers

Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)
(Publisher: John Wiley & Sons, Inc.)
Author(s): Bruce Schneier
ISBN: 0471128457
Publication Date: 01/01/96

Table of Contents

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¹⁶ = – 1 for multiplication modulo 2¹⁶ + 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₁⁽¹⁾ Z₂⁽¹⁾ Z₃⁽¹⁾ Z₄⁽¹⁾ Z₅⁽¹⁾ Z₆⁽¹⁾	Z₁^{(9) - 1} –Z₂⁽⁹⁾ –Z₃⁽⁹⁾ Z₄^{(9) - 1} Z₅⁽⁸⁾ Z₆⁽⁸⁾
2nd	Z₁⁽²⁾ Z₂⁽²⁾ Z₃⁽²⁾ Z₄⁽²⁾ Z₅⁽²⁾ Z₆⁽²⁾	Z₁^{(8) - 1} –Z₃⁽⁸⁾ –Z₂⁽⁸⁾ Z₄^{(8) - 1} Z₅⁽⁷⁾ Z₆⁽⁷⁾
3rd	Z₁⁽³⁾ Z₂⁽³⁾ Z₃⁽³⁾ Z₄⁽³⁾ Z₅⁽³⁾ Z₆⁽³⁾	Z₁^{(7) - 1} –Z₃⁽⁷⁾ –Z₂⁽⁷⁾ Z₄^{(7) - 1} Z₅⁽⁶⁾ Z₆⁽⁶⁾
4th	Z₁⁽⁴⁾ Z₂⁽⁴⁾ Z₃⁽⁴⁾ Z₄⁽⁴⁾ Z₅⁽⁴⁾ Z₆⁽⁴⁾	Z₁^{(6) - 1} –Z₃⁽⁶⁾ –Z₂⁽⁶⁾ Z₄^{(6) - 1} Z₅⁽⁵⁾ Z₆⁽⁵⁾
5th	Z₁⁽⁵⁾ Z₂⁽⁵⁾ Z₃⁽⁵⁾ Z₄⁽⁵⁾ Z₅⁽⁵⁾ Z₆⁽⁵⁾	Z₁^{(5) - 1} –Z₃⁽⁵⁾ –Z₂⁽⁵⁾ Z₄^{(5) - 1} Z₅⁵⁽⁴⁾ Z₆⁽⁴⁾
6th	Z₁⁽⁶⁾ Z₂⁽⁶⁾ Z₃⁽⁶⁾ Z₄⁽⁶⁾ Z₅⁽⁶⁾ Z₆⁽⁶⁾	Z₁^{(4) - 1} –Z₃⁽⁴⁾ –Z₂⁽⁴⁾ Z₄^{(4) - 1} Z₅⁽³⁾ Z₆⁽³⁾
7th	Z₁⁽⁷⁾ Z₂⁽⁷⁾ Z₃⁽⁷⁾ Z₄⁽⁷⁾ Z₅⁽⁷⁾ Z₆⁽⁷⁾	Z₁^{(3) - 1} –Z₃⁽³⁾ –Z₂⁽³⁾ Z₄^{(3) - 1} Z₅⁽²⁾ Z₆⁽²⁾
8th	Z₁⁽⁸⁾ Z₂⁽⁸⁾ Z₃⁽⁸⁾ Z₄⁽⁸⁾ Z₅⁽⁸⁾ Z₆⁽⁸⁾	Z₁^{(2) - 1} –Z₃⁽²⁾ –Z₂⁽²⁾ Z₄^{(2) - 1} Z₅⁽¹⁾ Z₆⁽¹⁾
output transformation	Z₁⁽⁹⁾ Z₂⁽⁹⁾ Z₃⁽⁹⁾ Z₄⁽⁹⁾	Z₁^{(1) - 1} –Z₂⁽¹⁾ –Z₃⁽¹⁾ Z₄^{(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¹²⁸(10³⁸) 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¹³ years—that’s longer than the age of the universe. An array of 10²⁴ 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⁴² 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):

0000, 0000, 0x 00, 0000, 0000, 000x,xxxx,x000

Table of Contents

[an error occurred while processing this directive]