From: ritter@cactus.org (Terry Ritter)
To: cypherpunks@toad.com
Message Hash: 545ea9d99796fac60c649768a5476b873e84216cb937fda883ccc24ad8d3241e
Message ID: <9402220836.AA26111@cactus.org>
Reply To: N/A
UTC Datetime: 19940222 08:57:22 UTC
Raw Date: Tue, 22 Feb 94 00:57:22 PST
From: ritter@cactus.org (Terry Ritter)
Date: Tue, 22 Feb 94 00:57:22 PST
To: cypherpunks@toad.com
Subject: Ladder DES
MessageID: <9402220836.AA26111@cactus.org>
MIMEVersion: 1.0
ContentType: text
Ritter Software Engineering
2609 Choctaw Trail
Austin, Texas 78745
(512) 8920494, ritter@cactus.org
LadderDES: 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 hightech 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 tripleDES. TripleDES, 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 tripleDES; otherwise, we might just as well use tripleDES
and be done with it. Speed is a measurable design quantity.
My third requirement is to include operation on data blocks larger
than the 8byte 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 datatransformation part of DES. Not shown is the
keyschedule computation which produces k1 through k16, the 48bit
"round" keys. Also not shown is the construction of function "f."
It will later be interesting to note that in DES each 32bit data
rail value is expanded to 48 bits, the XOR occurs with a 48bit key,
and the result contracted to 32 bits in 6bit to 4bit substitutions
known as "Sboxes."
LadderDES
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 8byte blocks; k1 and k2 represent 56bit
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.
KnownPlaintext Attack on TwoRung LadderDES
With knownplaintext, we essentially have a singleDES 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.
FourRung LadderDES
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 64bit DES blocks; k1 through k4 are 56bit DES keys.
A total of four DES operations process two DES blocks at doubleDES
rates. We would expect this to be both stronger than normal DES
and faster than tripleDES.
In general, the leftleg of a ladderDES structure is affected by
one fewer key than the rightleg.
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 Sbox contents, we could specify a cryptographic RNG
which would be used to permute a base Sbox 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 fourrung ladderDES construct uses four 56bit DES keys, but
certainly a cipher would be strong enough if it had "only" a real
twokey (112bit) 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.
KnownPlaintext Attack on FourRung LadderDES
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.
DivideAndConquer Attack on FourRung LadderDES
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.
MeetInTheMiddle Attack on FourRung LadderDES
With four keys involved, and no obvious "middle," it is not clear
how this attack could be applied.
2x FourRung LadderDES
The basic LadderDES 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
Rearrange 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 doubleDES, and
substantially faster than tripleDES.
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 64bit 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 ladderDES section, for a total of two keys.
Conclusion
DES operations can be arranged into a "ladderDES" constructs which
are especiallyclean and familiar and seem to resist known attacks.
These constructs seem potentially stronger than normal DES and are
demonstrably faster than tripleDES. Thus, ladderDES could be a
reasonable candidate to replace DES.
Return to February 1994
Return to “ritter@cactus.org (Terry Ritter)”
19940222 (Tue, 22 Feb 94 00:57:22 PST)  Ladder DES  ritter@cactus.org (Terry Ritter)