[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Ladder DES
Ritter Software Engineering
2609 Choctaw Trail
Austin, Texas 78745
(512) 892-0494, [email protected]
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.