The number at the positions of “x” can be any number. If this key is used, the bit-wise XOR of certain plaintext pairs guarantees the bit-wise XOR of the resultant ciphertext pairs.

In any case, the chance of accidentally generating one of these weak keys is very small: one in 2⁹⁶. There is no danger if you choose keys at random. And it is easy to modify IDEA so that it doesn’t have any weak keys: XOR every subkey with the value 0x0dae [409].

I know of no other cryptanalytic results against IDEA, although many people have tried.

IDEA Modes of Operation and Variants

IDEA can work within any block cipher mode discussed in Chapter 9. Any double-IDEA implementation would be susceptible to the same meet-in-the-middle attack as DES (see Section 15.1). However, because IDEA’s key length is more than double DES’s, the attack is impractical. It would require a storage space of 64*2¹²⁸ bits, or 10³⁹ bytes. Maybe there’s enough matter in the universe to create a memory device that large, but I doubt it.

Figure 13.10  PES.

If you’re worried about parallel universes as well, use a triple-IDEA implementation (see Section 15.2):

C = E_K3(D_K2(E_K1(P)))

It is immune to the meet-in-the-middle attack.

There’s also no reason why you can’t implement IDEA with independent subkeys, especially if you have key-management tools to handle the longer key. IDEA needs a total of 52 16-bit keys, for a total key length of 832 bits. This variant is definitely more secure, but no one knows by how much.

A naïve variation might double the block size. The algorithm would work just as well with 32-bit sub-blocks instead of 16-bit sub-blocks, and a 256-bit key. Encryption would be quicker and security would increase 2³² times. Or would it? The theory behind the algorithm hinges on the fact that 2¹⁶ + 1 is prime; 2³² + 1 is not. Perhaps the algorithm could be modified to work, but it would have very different security properties. Lai says it would be difficult to make it work [926].

While IDEA appears to be significantly more secure than DES, it isn’t always easy to substitute one for the other in an existing application. If your database and message templates are hardwired to accept a 64-bit key, it may be impossible to implement IDEA’s 128-bit key.

For those applications, generate a 128-bit key by concatenating the 64-bit key with itself. Remember that IDEA is weakened considerably by this modification.

If you are more concerned with speed than security, you might consider a variant of IDEA with fewer rounds. Currently the best attack against IDEA is faster than brute force only for 2.5 rounds or less [1050]; 4 round IDEA would be twice as fast and, as far as I know, just as secure.

Caveat Emptor

IDEA is a relatively new algorithm, and many questions remain. Is IDEA a group? (Lai thinks not [926].) Are there any still-undiscovered ways of breaking this cipher? IDEA has a firm theoretical basis, but time and time again secure-looking algorithms have fallen to new forms of cryptanalysis. Several academic and military groups have cryptanalyzed IDEA. None of them has gone public about any successes they might have had. One might—someday.

Patents and Licenses

IDEA is patented in Europe and the United States [1012, 1013]. The patent is held by Ascom-Tech AG. No license fee is required for non-commercial use. Commercial users interested in licensing the algorithm should contact Ascom Systec AG, Dept CMVV, Gewerbepark, CH-5506, Mägenwil, Switzerland; +41 64 56 59 83; Fax:+41 64 56 59 90; idea@ascom.ch.

13.10 MMB

A complaint against IDEA, that it uses a 64-bit encryption block, was addressed by Joan Daemen in an algorithm called MMB (Modular Multiplication-based Block cipher) [385, 405, 406]. MMB is based on the same basic theory as IDEA: mixing operations of different algebraic groups. MMB is an iterative algorithm that mainly consists of linear steps (XOR and key applications) and the parallel applications of four large nonlinear invertible substitutions. These substitutions are determined by a multiplication modulo 2³² – 1 with constant factors. The result is an algorithm that has both a 128-bit key and a 128-bit block size.

MMB operates on 32-bit sub-blocks of text (x₀, x₁, x₂, x₃) and 32-bit sub-blocks of key (k₀, k₁, k₂, k₃). This makes the algorithm well suited for implementation on modern, 32-bit processors. A nonlinear function, f, is applied six times alternating with XORing. Here it is (all index operations are mod 4):

x_i = x_i ⊕ k_i, for i = 0 to 3

f(x₀,x₁,x₂,x₃)

x_i = x_i ⊕ k_{i + 1}, for i = 0 to 3

f(x₀,x₁,x₂,x₃)

x_i = x_i ⊕ k_{i + 2}, for i = 0 to 3

f(x₀,x₁,x₂,x₃)

x_i = x_i ⊕ k_i, for i = 0 to 3

f(x₀,x₁,x₂,x₃)

x_i = x_i ⊕ k_{i + 1}, for i = 0 to 3

f(x₀,x₁,x₂,x₃)

x_i = x_i ⊕ k_{i + 2}, for i = 0 to 3

f(x₀,x₁,x₂,x₃)

The function f has three steps:

(1)  x_i = c_i * x_i, for i = 0 to 3 (If the input to the multiplication is all 1s, the output is also all 1s.)

(2)  If the least significant bit of x₀ = 1, then x₀ = x₀ ⊕ C. If the least significant byte of x₃ = 0, then x₃ = x₃ ⊕ C.

(3)  x_i = x_{i – 1} ⊕ x_i ⊕ x_{i + 1}, for i = 0 to 3

All index operations are mod 4. The multiplication operation in step (1) is modulo 2³² – 1. For the purposes of the algorithm, if the second operand is 2³² – 1, then the result is 2³² – 1. The various constants are:

C = 2aaaaaaa

c₀ = 025f1cdb

c₁ = 2 * c₀

c₂ = 2³ * c₀

c₃ = 2⁷ * c₀

The constant C is the “simplest” constant with a high ternary weight, a least-significant bit of zero, and no circular symmetry. The constant c₀ has certain other characteristics. The constants c₁, c₂, and c₃ are shifted versions of c₀, preventing attacks based on symmetry. See [405] for more details.

Decryption is the reverse process. Steps (2) and (3) are their own inverse. Step (1) uses c_i^-1 instead of c_i. The value of c₀^-1 is 0dad4694.