290 lines
11 KiB
Plaintext
290 lines
11 KiB
Plaintext
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.
|