Ritter Software Engineering 2609 Choctaw Trail Austin, Texas 78745 (512) 892-0494, ritter@cactus.org 2x Isolated Double-DES: Another Weak Two-Level DES Structure Terry Ritter February 16, 1994 Introduction The time has come to replace DES, the US Data Encryption Standard, but there is no clear alternative. While there are many ciphers which are demonstrably faster and also arguably stronger than DES, the fact that cipher strength cannot be _tested_ but must instead be_argued_ makes many users nervous. The US government offers some alternative ciphers, but those are secret designs whose strength _cannot_ be argued, again making users nervous. The current leading candidate for a replacement to DES is "triple- DES," a three-level construct using DES at each level. This is a comforting design, because users are already convinced that DES can be relied upon for a certain level of strength. Unfortunately, a software implementation of triple-DES takes three times the processing of normal DES. While this is a mere detail on systems which process the occasional enciphered email message, operational speed is fundamental to widespread industrial use. Ciphering speed is essential in LAN servers and other fully-enciphered communications nodes. Speed is also important when ciphering is an integral part of laptop software which communicates to a central facility. Fast software ciphering is important. Because the ciphering speed for triple-DES is not acceptable, no three-or-more-level construct could possibly be satisfactory in this respect. This limits our design alternatives to one-or two- level constructs based on DES. The goal, then, is to find--if possible--a construct which is based on DES, has strength substantially beyond normal DES, but requires less processing than triple-DES. This time we start from the base of double-DES, and directly confront the known weakness of that approach: Double-DES The classical double-DES construct is something like this: A v k1 -> DES1 v B v C v k2 -> DES2 v D where each single capital letter represents an 8-byte DES block. Double-DES is normally not used, because of the meet-in-the-middle attack: Meet-In-The-Middle Attack on Double DES Assume we have known-plaintext A for ciphertext D: Encipher A under every possible key k1, and decipher D under every possible key k2. (The cost for this is only two full DES key searches.) Then check for matches between B and C. If there are multiple matches, the correct k1 and k2 will be there somewhere, and we can isolate the correct pair with one or two more known-plaintext blocks (this is a loose interpretation of [2]). This works for the normal double-DES construction because it is possible to check for matches between B and C; the weakness seems to be the ability to check for a match. Assuming that we have properly identified the principal weakness of double-DES, let's fix it: We can isolate the two values, making a match check impossible, so that not even one bit can be checked. Isolated Double-DES Consider a two-level DES construct like this: A v k1 -> DES1 v B v km -> XOR v C v k2 -> DES2 v D where k1 and k2 are 56-bit keys, but km is a 64-bit key. Technically, this construct could be considered to be either double-DES with an intermediate ("isolating") XOR operation, or triple-DES with XOR replacing the middle DES operation. But since the processing cost for this system is similar to double-DES, it is reasonable to call it a form of double-DES. While it is true that we now have three keys for a two-level DES structure, this is no worse than triple-DES with separate keys. But is it stronger than double-DES? Isolated Double-DES Meet-In-The-Middle Attack Again, encipher A under every possible key k1, and decipher D under every possible key k2 and check for matches between B and C. But in the isolated construction, every possible pair of values (B,C) has some key km which would make that pair match. Thus, the weakness of match identification in the original construction is not possible in the alternate construction. The keyspace seems to be 56 + 64 = 120 bits, which would probably be satisfactory for another couple of decades, or until an open science of cryptographic machine design has matured. It still has a small block size, however. Larger Blocks DES uses a relatively-small 8-byte block, so if DES were used in Electronic Code Book (ECB) mode and large amounts of plaintext were known, a dictionary attack would be possible. Fortunately, DES is normally used in Cipher Block Chain (CBC) mode, making dictionary attacks difficult. But a dictionary attack on ECB mode could be viewed as a "certificational attack" which is "indicative of weakness" in the cipher itself. [1:466] If we make the modest assumption that ordinary text has an information content of under 40 percent of the binary size, then a 64-bit block of text generally contains less than 26 bits of uniqueness. Worse, short words occur far more often than an even distribution would indicate. Although it would certainly be ill- advised to send 2^26 blocks (2^29 bytes) of data under a single set of keys, it is interesting to note the relatively small size of this figure when compared to other cryptographic quantities. For this reason, it seems appropriate that any new standard specify an expanded block width. Here is a double-width approach, 2x2 DES described in an earlier article: A B v v k1 -> DES1 k2 -> DES2 v v C D Exchange Right 4 Bytes E F v v k3 -> DES3 k4 -> DES4 v v G H Note that the 64-bit quantity G (for example) is a complex nonlinear function of A, B, k1, k2, and k3; a total of 296 bits. Nevertheless the system is still solvable with meet-in-the-middle: 2x2 DES Meet-In-The-Middle Attack With one known-plaintext block, we can search one top key and one bottom key (say, k1 and k3) and find pairs (E,C) which match at the appropriate 32 bit-positions. Then we can identify the correct pair with additional known-plaintext blocks, resolving the keys at 32-bits per known-plaintext pair. We can guarantee that the two keys will be found by searching all possible k1 and k3. This is only twice the normal DES keyspace, but may well require a huge amount of storage to identify all the values and associated keys (say, E and k3) which match a particular result (say, C). We do not want to run through every k3 every time we change k1. 2x2 DES Differential Attack Eli Biham [1] points out that a differential attack can eliminate the need to store the result from every possible key. In this case we need two different large blocks of known-plaintext with plaintext or ciphertext half the same (say, A:B -> G:H and A:X -> Y:Z). With A the same in both large blocks, we know that the left-half of E must also be the same. Then, since we have two different blocks, we can step through all possible values for k3, deciphering G into E and Y into E' each time, looking for any results with the left-half the same. This should occur about every 2^32 trials, producing 2^24 trials which match, which should be resolved in only one or two more set of known-plaintext blocks. No huge storage is needed. 2x Isolated Double-DES Consider a pair of isolated double-DES structures, combined as described for 2x2 DES: A B v v k1 -> DES1 k2 -> DES2 v v km -> XOR1 kn -> XOR2 v v Exchange Right 4 Bytes v v k3 -> DES3 k4 -> DES4 v v C D The result is a double-width structure, in which every ciphertext bit in C depends on each and every bit in A, B, k1, k2, and k3, as well as half the bits in km and kn. Ciphering occurs at the rate of double-DES. While it is certainly true that six keys are needed, keys need be transmitted far less often than data, and by having separate keys we avoid attacks which depend upon having the same key at multiple parts of the operation. If we say that enciphering occurs "from the top down," (XOR before exchange) then we would say that deciphering occurs "from the bottom up" (exchange before XOR). 2x Isolated Double-DES Meet-In-The-Middle Attack The double-DES meet-in-the-middle attack depended upon having a structure in which the enciphered plaintext was identical to the deciphered ciphertext. This allowed both keys to be manipulated and the resulting data space searched for matches. In isolated double-DES any enciphered plaintext value can be related to any deciphered ciphertext value by varying the middle or "isolating" key. Thus, meet-in-the-middle seems not very useful. 2x Isolated Double-DES Differential Attack The 2x2 differential attack depended not upon identical top and bottom values, but upon producing an identical value (in particular known bit positions) from a bottom deciphering (for example). This situation is not affected by the XOR and so the differential attack will still work. Conclusion 2x Isolated double-DES falls to a differential attack. References [1] Biham, E. Mon, 7 Feb 1994 16:59:28 GMT. Comments on Nx2 DES. <CKv5v5.EnF@chinet.chinet.com> [2] Merkle, R. and M. Hellman. 1981. On the Security of Multiple Encryption. Communications of the ACM. 24(7): 465-467.