Large Block DES Newsletter
Terry Ritter
ritter at cactus.org
Tue Mar 1 16:25:01 PST 1994
Large Block DES Newsletter
Vol. I, No. 1
Feb. 28, 1994
Terry Ritter, Ed.
Current Standings for the Large-Block DES Proposals:
I. NxM DES:
A B
v v
k1 -> DES1 k2 -> DES2
v v
C D
Exchange Right 4 Bytes
E F
v v
k3 -> DES3 k4 -> DES4
v v
G H
Falls to meet-in-the-middle like double-DES. Falls to a
practical attack by Biham, now called "fix-in-the-middle."
II. NxM DES Found Weak
Announcement of above.
III. Isolated Double-DES
2x construct found weak in original article.
The 1x construct:
A
v
k1 -> DES1
v
B
v
km -> XOR
v
C
v
k2 -> DES2
v
D
was found weak by Chris Dodd <dodd at csl.sri.com> who pointed
out that two different blocks of known-plaintext (A,D) and
(A',D') will allow matching (B XOR B') and (C xor X'). (This
is similar to Biham's "fix-in-the-middle.") Good going Chris!
Also found by Stefan Lucks <lucks at namu01.gwdg.de>.
IV. Ladder-DES
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
Joseph C. Konczal <jkonczal at nist.gov> points out that the
construct is indeed vulnerable to meet-in-the-middle. I
agree, but note that this seems to imply a 112-bit search.
Since we don't need more than 112 or 120 bits of strength,
I don't see it as a problem. (Indeed, if we could get more
strength, we might want to trade it for speed anyway.) 112
bits (or so) is the design goal, which should be enough for
a couple of decades.
In a normal cipher design, I would expect each key bit to
contribute toward strength, but these are hardly normal cipher
designs. Especially when we try to expand block size, extra
keys may simply provide another small block with the same
strength as a previous small block. Keys will be delivered
electronically, so the relatively rare delivery of 2x or 4x
or even 8x the expected key material should not pose a serious
problem.
However, Biham reports:
"ladder DES is not more secure than 2**88 steps and
2**64 chosen plaintexts."
Now, 2^88 cipherings is 2^32 times as strong as the 2^56
currently in DES (and larger than Skipjack), but hardly the
2^112 intended. For the current design the current options
are:
1) live with the 2^88 strength (so far!),
2) design the rest of the system to prevent chosen
plaintexts, or
3) prevent more than, say, 2^32 block cipherings under a
single key.
Actually, we need to know exactly what the problem is, and the
limits of it, before we can propose a fix, or decide whether
the ladder-DES scheme is unfixable.
Summary
Three substantially different constructs proposed; of these, two
fall, and one is wounded.
To review, the intent is to find some relatively-simple construct
which builds on the assumed strength of DES to deliver wide blocks
and something like 112 bits of strength, with less processing than
triple-DES. (I see no need for super-strength, unless it is free.)
We still do not know whether or not this is possible.
More information about the cypherpunks-legacy
mailing list