From: ritter@cactus.org (Terry Ritter)
Date: Fri, 11 Feb 94 01:30:24 PST
To: cypherpunks@toad.com
Subject: Nx2 DES Found Weak
Message-ID: <9402110926.AA01707@cactus.org>
MIME-Version: 1.0
Content-Type: text





                   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.