|< Day Day Up >|
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).
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 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:
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.
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.
Figure 11.8. IDEA operation and rounds structure.
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:
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.
|< Day Day Up >|