Newsgroups: sci.crypt Path: cactus.org!ritter From: ritter@cactus.org (Terry Ritter) Subject: Re: Strong Block Ciphers from Weak Ones: NxM DES Message-ID: <1994Feb12.073133.28333@cactus.org> Summary: Nx2 DES Found Weak Keywords: DES replacement, triple-DES Organization: Capital Area Central Texas UNIX Society, Austin, Tx References: <1994Feb2.071956.29014@cactus.org>Date: Sat, 12 Feb 1994 07:31:33 GMT Ritter Software Engineering 2609 Choctaw Trail Austin, Texas 78745 (512) 892-0494, ritter@cactus.org Nx2 DES Found Weak Terry Ritter February 11, 1994 Summary Any Nx2 DES system succumbs to meet-in-the-middle attack at a cost only N times that of normal DES, and is probably not worth using. If we assume that DES would fall with 2^55 cipherings (on average), then the 4x2+ DES system which I previously recommended would require only 2^57 cipherings. Such an attack, however, might require substantially more storage and might be more difficult to mechanize and slower in operation than an attack on normal DES. Nx3 DES systems seem not to be affected by this attack, but they are also not faster than triple-DES (1x3 DES), which was the main reason for recommending Nx2 DES over triple-DES. On the other hand, Nx3 DES systems apparently would provide added strength against dictionary attacks; such attacks might be possible against ASCII plaintext when ciphered in small 8-byte blocks. Double-DES A 1x2 DES construct (double-DES) is something like this: A v k1 -> DES1 v B v k2 -> DES2 v C Each single capital letter represents an 8-byte DES block. Meet-In-The-Middle Attack on 1x2 DES (double-DES) [ This is probably similar to: Merkle, R. and M. Hellman. 1981. On the security of multiple encryption. Comm. ACM 27(4): 465. which I have not seen. This analysis resulted from trying to understand the comments on NxM DES made by email from Eli Biham, which led me to: Davies, D. and W. Price. 1984. Security for Computer Networks. Wiley. 75. and the attack on double-DES. Obviously I did not expect that attack to work on Nx2 DES, or I would have skipped Nx2 entirely. ] First we need some known-plaintext (A) and its associated ciphertext (C). Now we encipher A with every possible random key k1 and save the results. Then we decipher C with random keys k2, eventually finding a match to the enciphered data. There are many possible pairs of keys (k1, k2) which will produce matching B's. Since there are 112 key bits (k1, k2), and we match 64 bits each time, there should be about 112 - 64 or 48 bits of freedom (that is, 2^48 possibilities) to be resolved with one or two more known-plaintext blocks. We can guarantee to find the correct key pair if we try every possible key for k1 and also every possible key for k2; this is only twice the effort of a full DES key search, and we need only search half that, on average. (In practice, we would do some k1's and then some k2's, repeated until success occurred.) However, we should note that this technique may require the intermediate storage of 2^56 results. This would be over 2^59 bytes of store, and this amount of storage and lookup is not nearly as easy or fast as the on-chip ciphering-and-compare solution for DES. Still, the result is not comforting. A 2x2 DES construct is something like this: A B v v k1 -> DES1 k2 -> DES2 v v C D Exchange Half E F v v k3 -> DES3 k4 -> DES4 v v G H Meet-In-The-Middle Attack on 2x2 DES Suppose we first try the 2x1 approach: With one known-plaintext block, we can search two keys (say k1 and k2) until a match is found for the center block. Then we can validate that match with additional known-plaintext blocks. (Since there is only a 32-bit match-check and a 112-bit keyspace, there will be 112 - 32 or 80 bits of freedom to resolve at about 32 bits per known-plaintext pair, so we would want to check a minimum of 3 or 4 other known-plaintexts. The cost of the subsequent cipherings and comparisons would be relatively insignificant, however.) We can guarantee that the two keys will be found by searching all possible k1 and k2. This is only twice the normal DES keyspace, and we only need search half of that, on average. And we can do this again for the other two keys at a similar cost. Again, the attack hardware will be considerably more awkward than any simple search for a DES key which matches a given ciphertext value, but the total number of DES cipherings will be about twice the DES keyspace, on average. Nx2 DES Falls Similar arguments lead to the conclusion that, for any N, Nx2 DES must be generally comparable in strength to DES itself. This means that the larger block has not helped strength much in any Nx2 DES system, despite the fact that every ciphertext bit is demonstrably a function of every plaintext bit in the large block as well as every bit in all the separate DES keys. Note that the form of the inter-stage permutation has absolutely no effect on this attack or overall strength, despite the fact that a great deal has been written about designing S-P permutations. The meet-in-the-middle attack seems not to apply to Nx3 DES. Dictionary Attacks Normally we define "strength" as the *minimum* effort expected to "break" a cipher, when taken over *all possible attacks*. Working out the extent of "all possible attacks" is a major part of the effort in cryptography. With respect to DES, most of the current attacks have considered the relatively-small 56-bit keyspace. But I am also concerned by the relatively-small 8-byte block size. Consider an 8-byte block of ASCII text: Modern data-compression programs typically compress such data by 60 percent. This means that we typically have less than 26 bits or so of "uniqueness" in the various blocks. Rigidly-formatted business documents, letters, or forms would be even less unique, and, thus, even more attackable. To the extent that a substantial amount of known-plaintext could be acquired (or possibly even inferred), a dictionary attack becomes possible. For this reason, if a change is to be made, then I would like to see a block size at least four times that now used. This would be a reasonable approach with a 4x3+ DES system, which would be comparable in throughput to a 1x3 DES system, but, alas, not faster. Conclusion A two-stage or Nx2 DES construction is probably not worth using.