Previous Section  < Day Day Up >  Next Section

Between DES and AES: Common Ciphers of the Transition Period

But what about the period between the time when DES weakness became apparent and the final round of AES competition did not discover a winner? Were communication channels unsafe? Apparently not. There were multiple attempts to improve DES, including DESX from RSA Data Security (which used whitening in addition to traditional DES rounds and IP/FP), CRYPT(3) used on some UNIX systems as a one-way function for password hashing (we'll cover one-way functions and hashes soon), RDES (with key-depending swapping), and so on. The most famous and implemented attempt to improve DES is triple DES (3DES).

3DES

Recall that the weakness of DES lies in a limited key space and key scheduling function that doesn't use the full key space. If we combine three DES iterations using three different keys into a single process, the "key size" is tripled: 56 bits x 3 = 164 bits. If ek(x) is encryption of a 64-bit data block with the key K, and dk(x) decryption of the same block, Kc = ek3(dk2(ek1(x))) and, if you want to decrypt it, x = dk1(ek2(dk3(c))).

Many experts consider 3DES to be the most secure 64-bit block cipher. However, running DES three times is a very slow, resource-consuming process, at least in software. When implemented in hardware, 3DES can be reasonably efficient, because its operations are simple (see the case of Serpent discussed earlier). One can compromise and run 2DES: From the preceding formulas you can see that k1 can be the same with k3, which gives you a 112-bit key space.

Alternatively, a variety of 64-block ciphers came into being before the world shifted to the 128-bit realm. The most remarkable algorithms from that group are probably IDEA and Blowfish.

Blowfish

Blowfish was proposed by Bruce Schneier in 1993 and is license and royalty free. It is used by OpenSSH, password encryption in OpenBSD, and many commercial and free products listed at http://www.counterpane.com/products.html. On the contrary, IDEA is patented. Its main fame comes from the use of IDEA in the original PGP software.

Blowfish uses 16 rounds and key sizes from 32 to 448 bits. It is faster than DES on 32-bit CPUs and can run in less than 5 kb of memory. However, it uses a large number of subkeys that must be precomputed before encryption and decryption take place. Unlike DES, Blowfish runs the f function on the left side of the block, obtaining a result that is XORed to the right half of the block. This happens in more recent cipher designs including the AES candidates, so Blowfish was somewhat ahead of the times at its birth.

For each Blowfish round, first the left half of the block is XORed with the subkey for that round. Then the f function is run on the left half of the block, and the right half of the block gets XORed with the result. Finally, after all but the last round, halves of the block are swapped. There is only one subkey for each round; the f function does not consume any subkeys, but uses S-boxes that are key-dependent (see the preceding review of Blowfish'es offspring Twofish).

After the last round, the right half is XORed with subkey 17, and the left half with subkey 18 as a form of whitening (because there are 16 rounds, these subkeys are not used for anything apart from the whitening operation, as it should be).

For the more mathematical among us:







Divide x into two 32-bit halves: xL, xR

For i = 1 to 16:

xL = xL XOR Pi

xR = F(xL) XOR xR

Swap xL and xR

Swap xL and xR (Undo the last swap.)

xR = xR XOR P17

xL = xL XOR P18

Recombine xL and xR

Function F:

Divide xL into four eight-bit quarters: a, b, c, and d

F(xL) = ((S1,a + S2,b mod 232) XOR S3,c) + S4,d mod 232

For subkey generation, the following steps are performed:

  1. First initialize the P-array and then the four S-boxes, in order, with a fixed string. This string consists of the hexadecimal digits of Pi (less the initial 3). For example:

    




    
P1 = 0x243f6a88

P2 = 0x85a308d3

P3 = 0x13198a2e

P4 = 0x03707344

  2. XOR P1 with the first 32 bits of the key, XOR P2 with the second 32 bits of the key, and so on, for all bits of the key (possibly up to P14). Repeatedly cycle through the key bits until the entire P-array has been XORed with key bits. (For every short key, there is at least one equivalent longer key; e.g., if A is a 64-bit key, then AA, AAA, etc., are equivalent keys.)

  3. Encrypt the all-zero string with the Blowfish algorithm, using the subkeys described in Steps 1 and 2.

  4. Replace P1 and P2 with the output of Step 3.

  5. Encrypt the output of Step 3 using the Blowfish algorithm with the modified subkeys.

  6. Replace P3 and P4 with the output of Step 5.

  7. Continue the process, replacing all entries of the P-array, and then all four S-boxes in order, with the output of the continuously changing Blowfish algorithm.

In total, 521 iterations are required to generate all required subkeys. Applications can store the subkeys rather than execute this derivation process multiple times. In one case we consume memory, otherwise we consume CPU cycles. Because the function F implements addition, Blowfish can be partially susceptible to power-consumption and timing attacks.

IDEA

The International Data Encryption Algorithm (IDEA) was proposed by Xuejia Lai and James Massey at the Swiss Institute of Technology. IDEA uses a 128-bit key from which 52 16-bit subkeys are derived. Two subkeys are used during each round proper, and four are used before every round and after the last round. IDEA has eight rounds.

The plaintext block in IDEA is divided into four quarters (X1-X4), each 16 bits long. Three operations are used in IDEA to combine two 16-bit values to produce a 16-bit result: addition, XOR, and multiplication. The best brief description of IDEA we have seen in the literature is in Chapter 13 of Schneier's Applied Cryptography, Second Edition (John Wiley & Sons, 1996, ISBN: 0471117099). The sequence of round events follows, with round description represented by Figure 11-7 and rounds in sequence represented by Figure 11-8.









1. X1 * first_subkey

2. X2 + second_subkey

3. X3 + third_subkey

4. X4 * fourth_subkey

5. Step 1 result ^= Step 3 result

6. Step 2 result ^= Step 4 result

7. Step 5 result * fifth_subkey

8. Step 6 result + Step 7 result

9. Step 8 result * sixth_subkey

10. Step 7 result + Step 9 result

11. Step 1 result ^= Step 9 result

12. Step 3 result ^= Step 9 result

13. Step 2 result ^= Step 10 result

14. Step 4 result ^= Step 10 result

Figure 11.7. IDEA round structure.

graphics/11fig08.gif


Figure 11.8. IDEA operation and rounds structure.

graphics/11fig09.gif


After the final eighth round there is a final output transformation:







a) X1 * first_subkey



b) X2 + second_subkey



c) X3 + third_subkey



d) X4 * fourth_subkey

The subkey generation in IDEA is straightforward: The 128-bit IDEA key is taken as the first eight subkeys, K(1) through K(8). The next eight subkeys are obtained exactly the same way, after a 25-bit circular left shift, and this is repeated until all 52 encryption subkeys are derived.

So, let's count all multiplications and additions in iteration:

  • 4 per round x 8 rounds + 2 in a final output transformation = 34 multiplications (many literature sources state 32, forgetting about the final output transformation).

  • 4 per round x 8 rounds + 2 in a final output transformation = 34 additions.

As you can imagine, software-implemented IDEA is second to 3DES when it comes to slow performance, and hardware to run IDEA cipher must be rather specific.

Although all academic attacks on IDEA have failed so far, and the cipher is still considered to be very secure, we would expect it to be very difficult to defend against power consumption and timing attacks, as well as other possible implementation attacks to come.

    Previous Section  < Day Day Up >  Next Section