From: ritter@cactus.org (Terry Ritter)
Date: Tue, 22 Feb 94 00:57:22 PST
To: cypherpunks@toad.com
Subject: Ladder DES
Message-ID: <9402220836.AA26111@cactus.org>
MIME-Version: 1.0
Content-Type: text






                    Ritter Software Engineering
                        2609 Choctaw Trail
                        Austin, Texas 78745
                 (512) 892-0494, ritter@cactus.org



          Ladder-DES: A Proposed Candidate to Replace DES

                           Terry Ritter
                         February 22, 1994


 Introduction

 Data enciphered by DES, the US Data Encryption Standard, has become
 vulnerable to modern technical attacks.  Currently, such attacks
 require substantial capital and high-tech engineering development
 to produce a special "DES breaking" machine.  However, once such a
 machine is built, attacks would become relatively fast and cheap.
 Businesses which currently protect very expensive and marketable
 secrets with DES should take immediate notice.

 To maintain earlier levels of security, DES must be replaced with
 a stronger cipher.  The one obvious alternative to DES is a simple
 construct built from DES called triple-DES.  Triple-DES, while
 generally being thought of as "strong enough," also carries the
 baggage of requiring three times the processing of normal DES.

 Because every security system is required to provide more benefit
 than its cost, raising costs by a factor of three (when compared
 to the alternative of normal DES) is a significant issue.  Such
 costs could dangerously delay the retirement of ordinary DES.


 Requirements

 The goal of this sequence of designs is to identify one or more
 better candidates to replace DES.  Obviously, the first requirement
 is that each candidate be substantially "stronger" than normal DES.
 One problem here is that we can only _argue_ strength, so it is
 important that candidate designs be openly presented and reviewed.
 We cannot expect that most proposals will withstand such review.

 The second requirement is that each candidate design also be faster
 than triple-DES; otherwise, we might just as well use triple-DES
 and be done with it.  Speed is a measurable design quantity.

 My third requirement is to include operation on data blocks larger
 than the 8-byte DES block.  Although DES is not normally used in a
 way which is conducive to "dictionary" attack, such attacks could be
 effective on the bare cipher itself.  This raises the possibility
 that a "certificational" weakness may exist which we currently do
 not know how to exploit, but which may be dangerous anyway.  This
 particular weakness depends upon small blocks.

 At this point there is still some question as to whether it is
 _possible_ to come up with candidate designs which meet these
 three requirements.


 Ladder Diagrams

 DES itself is frequently shown in figures which are described as
 "ladder diagrams" because of their appearance:

                    |
                    v
           Initial Permutation
                    v
              <-- SPLIT -->
             |             |
             |      k1     |
             v      v      |
            XOR <-- f -----|
             |             |
             |      k2     |
             |      v      v
             |----- f --> XOR
             |             |
                  . . .

             |      k16    |
             |      v      v
             |----- f --> XOR
             |             |
             |             |
             --> COLLECT <--
                    v
             Inv. Init. Perm.
                    |
                    v

 This is the data-transformation part of DES.  Not shown is the
 key-schedule computation which produces k1 through k16, the 48-bit
 "round" keys.  Also not shown is the construction of function "f."

 It will later be interesting to note that in DES each 32-bit data
 rail value is expanded to 48 bits, the XOR occurs with a 48-bit key,
 and the result contracted to 32 bits in 6-bit to 4-bit substitutions
 known as "S-boxes."


 Ladder-DES

 Consider this simple construct which looks something like two
 rungs or steps on a ladder:

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

 A, B, C and D represent 8-byte blocks; k1 and k2 represent 56-bit
 DES keys.  This enciphers two DES data blocks in two DES operations;
 this is a data rate similar to normal DES.  It can be described as
 working on a single large block composed of A and B.  Note that the
 data paths are twice the size of those used in DES itself.

 Also note that the design is asymmetric:  While ciphertext block C
 is a function of every bit in plaintext blocks A and B, as well as
 every bit in key k1, ciphertext block D is _also_ a function of
 key k2.


 Known-Plaintext Attack on Two-Rung Ladder-DES

 With known-plaintext, we essentially have a single-DES complexity:
 Since A is known and C is known, the output of DES1 is known.  Since
 the input to DES1 is also known, to find k1 we just do a normal DES
 search.

 Alternately, since B is known and D is known, the output of DES2 is
 known.  Since the input to DES2 is also known, to find k2 we just do
 a normal DES search.

 Total complexity: twice DES; thus, hardly worth using.


 Four-Rung Ladder-DES

 Now consider a similar construct, twice as long:

             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

 A and B are 64-bit DES blocks; k1 through k4 are 56-bit DES keys.
 A total of four DES operations process two DES blocks at double-DES
 rates.  We would expect this to be both stronger than normal DES
 and faster than triple-DES.

 In general, the left-leg of a ladder-DES structure is affected by
 one fewer key than the right-leg.


 Belief

 Can we "believe" in this basic structure?  Well, DES itself is
 based on it.  But we do need to remember that DES also includes
 seriously nonlinear data expansions and contractions around each
 XOR.  Certainly expansion and contraction could be added to ladder-
 DES, although this could be expensive.  (To avoid specifying
 particular S-box contents, we could specify a cryptographic RNG
 which would be used to permute a base S-box arrangement; this
 should also avoid normal differential attacks.)  It is not clear
 that the lack of expansion and contraction operations necessarily
 negates the overall approach.


 Key Reduction

 The four-rung ladder-DES construct uses four 56-bit DES keys, but
 certainly a cipher would be strong enough if it had "only" a real
 two-key (112-bit) keyspace.  Thus, we might consider making k3 = k1,
 and k4 = k2, or perhaps, k3 = k1 and k4 = k1 XOR k2.

 On the other hand, perhaps it would be worthwhile to support
 additional keys simply to avoid the necessity of showing that a
 reduced key approach could never reduce strength.


 Known-Plaintext Attack on Four-Rung Ladder-DES

 No longer do we have the advantage of knowing both the input to
 and the output from XOR operations, so we can no longer gain access
 to the output of particular DES operations.  Thus, the obvious
 search strategy is not available.


 Divide-And-Conquer Attack on Four-Rung Ladder-DES

 Normally we try to separate the effects of the different DES
 operations, so we can "divide and conquer" each separately.
 In this case, DES4 is the obvious first choice, since with the
 keys k1..k3 fixed, only k4 affects the output, and then it only
 affects block D.  However, unless we know the values of k1 and k2,
 we don't know the input to the bottom XOR, and so apparently
 cannot separate DES4 to work on it.


 Meet-In-The-Middle Attack on Four-Rung Ladder-DES

 With four keys involved, and no obvious "middle," it is not clear
 how this attack could be applied.


 2x Four-Rung Ladder-DES

 The basic Ladder-DES construct can be expanded to cipher four
 blocks at once:

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

                         Re-arrange Blocks

             H              E         F              G
             |      k5      |         |      k6      |
             v      v       |         |      v       |
            XOR <- DES5 ----|        XOR <- DES6 ----|
             |              |         |              |
             |      k7      |         |      k8      |
             |      v       v         |      v       v
             |---- DES7 -> XOR        |---- DES8 -> XOR
             |              |         |              |
             v              v         v              v
             I              J         K              L

 This construct enciphers four DES data blocks in eight DES
 operations; again, this is a speed comparable to double-DES, and
 substantially faster than triple-DES.

 Ciphertext block I is now a function of every bit in plaintext
 blocks A, B, C, and D, as well as every bit in keys k1, k2, k4,
 and k5.  Every bit in the 64-bit I is a complex function of
 480 bits.

 We could certainly afford to reduce the number of keys in these
 constructs, and this might be done in any number of ways.  For
 the 2x construct, for example:

      k2 := k1 XOR k3;  k4 := k3 XOR k5;
      k6 := k5 XOR k7;  k8 := k7 XOR k1;

 leaving us with a need for four keys:  k1, k3, k5 and k7.  It is
 also possible that the same two keys could be used in every two-
 rung ladder-DES section, for a total of two keys.


 Conclusion

 DES operations can be arranged into a "ladder-DES" constructs which
 are especially-clean and familiar and seem to resist known attacks.
 These constructs seem potentially stronger than normal DES and are
 demonstrably faster than triple-DES.  Thus, ladder-DES could be a
 reasonable candidate to replace DES.