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.