< Day Day Up > |

## Between DES and AES: Common Ciphers of the Transition PeriodBut 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). ## 3DESRecall 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 K, and d decryption of the same block, _{k}(x)Kc = e and, if you want to decrypt it, _{k3}(d_{k2}(e_{k1}(x)))x = d._{k1}(e_{k2}(d_{k3}(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 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. ## BlowfishBlowfish 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: - 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
`P`(less the initial 3). For example:_{i}
P1 = 0x243f6a88 P2 = 0x85a308d3 P3 = 0x13198a2e P4 = 0x03707344 - 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.) - Encrypt the all-zero string with the Blowfish algorithm, using the subkeys described in Steps 1 and 2.
- Replace
`P1`and`P2`with the output of Step 3. - Encrypt the output of Step 3 using the Blowfish algorithm with the modified subkeys.
- Replace
`P3`and`P4`with the output of Step 5. - 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. ## IDEAThe 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 ( 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, 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. |

< Day Day Up > |