From: ritter@cactus.org (Terry Ritter)
Date: Tue, 1 Mar 94 16:25:01 PST
To: cypherpunks@toad.com
Subject: Large Block DES Newsletter
Message-ID: <9403020024.AA06224@cactus.org>
MIME-Version: 1.0
Content-Type: text



                Large Block DES Newsletter

                      Vol. I, No. 1
                      Feb. 28, 1994

                    Terry Ritter, Ed.



 Current Standings for the Large-Block DES Proposals:


 I. NxM DES:

             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

      Falls to meet-in-the-middle like double-DES.  Falls to a
      practical attack by Biham, now called "fix-in-the-middle."


 II.  NxM DES Found Weak

      Announcement of above.


 III.  Isolated Double-DES

      2x construct found weak in original article.

      The 1x construct:

            A
            v
     k1 -> DES1
            v
            B
            v
     km -> XOR
            v
            C
            v
     k2 -> DES2
            v
            D

      was found weak by Chris Dodd <dodd@csl.sri.com> who pointed
      out that two different blocks of known-plaintext (A,D) and
      (A',D') will allow matching (B XOR B') and (C xor X').  (This
      is similar to Biham's "fix-in-the-middle.")  Good going Chris!

      Also found by Stefan Lucks <lucks@namu01.gwdg.de>.


 IV. Ladder-DES

             A              B
             |      k1      |
             v      v       |
            XOR <- DES1-----|
             |              |
             |      k2      |
             |      v       v
             |---- DES2 -> XOR
             |              |
             |      k3      |
             v      v       |
            XOR <- DES3 ----|
             |              |
             |      k4      |
             |      v       v
             |---- DES4 -> XOR
             |              |
             v              v
             C              D

      Joseph C. Konczal <jkonczal@nist.gov> points out that the
      construct is indeed vulnerable to meet-in-the-middle.  I
      agree, but note that this seems to imply a 112-bit search.
      Since we don't need more than 112 or 120 bits of strength,
      I don't see it as a problem.  (Indeed, if we could get more
      strength, we might want to trade it for speed anyway.)  112
      bits (or so) is the design goal, which should be enough for
      a couple of decades.

      In a normal cipher design, I would expect each key bit to
      contribute toward strength, but these are hardly normal cipher
      designs.  Especially when we try to expand block size, extra
      keys may simply provide another small block with the same
      strength as a previous small block.  Keys will be delivered
      electronically, so the relatively rare delivery of 2x or 4x
      or even 8x the expected key material should not pose a serious
      problem.


      However, Biham reports:

           "ladder DES is not more secure than 2**88 steps and
           2**64 chosen plaintexts."

      Now, 2^88 cipherings is 2^32 times as strong as the 2^56
      currently in DES (and larger than Skipjack), but hardly the
      2^112 intended.  For the current design the current options
      are:

         1) live with the 2^88 strength (so far!),
         2) design the rest of the system to prevent chosen
            plaintexts, or
         3) prevent more than, say, 2^32 block cipherings under a
            single key.

      Actually, we need to know exactly what the problem is, and the
      limits of it, before we can propose a fix, or decide whether
      the ladder-DES scheme is unfixable.


 Summary

 Three substantially different constructs proposed; of these, two
 fall, and one is wounded.

 To review, the intent is to find some relatively-simple construct
 which builds on the assumed strength of DES to deliver wide blocks
 and something like 112 bits of strength, with less processing than
 triple-DES.  (I see no need for super-strength, unless it is free.)

 We still do not know whether or not this is possible.