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.