[1110] in cryptography@c2.net mail archive
Re: cracking n-DES?
daemon@ATHENA.MIT.EDU (David Wagner)
Sat Jun 28 02:02:18 1997
To: cryptography@c2.net
From: daw@cs.berkeley.edu (David Wagner)
Date: 27 Jun 1997 22:07:18 -0700
In article <3.0.2.32.19970627232231.00ae15a0@cybercash.com>,
Carl Ellison <cme@cybercash.com> wrote:
> There are several reasons I have advocated the combination
>
> des|tran|des|tran|des
>
> if you want really serious multiple-DES.
Ok, challenge taken. If I understand the proposal correctly, d|t|d|t|d
isn't nearly as strong as 3-DES: this post describes how to break it with
3 * 2^{56} trial decryptions and one chosen plaintext query, I think.
The intuition behind the attack is that des|tran|des|tran|des is using some
form of (roughly speaking) "inner chaining". As Biham has shown for other
inner chaining modes, outer chaining tends to be much stronger.
The lesson to walk away with (IMHO): if you use triple-DES, use it as a
black box, i.e. as a block cipher with a 168-bit key and a 64-bit block size.
Here is the attack. I assume you have a known plaintext/ciphertext pair
(P,C) which is about two blocks (16kB) long, or longer. Generate
another chosen plaintext P' which differs from P only in the first 8
bytes of the second block. Get the corresponding ciphertext C' by doing
a chosen-plaintext encryption with d|t|d|t|d. Note that tran does a
transposition on the bytes, keyed by (a histogram on) the (8k) bytes of
the first block. This means that (des|tran)(P) differs from
(des|tran)(P') in only 8 bytes, which are probably pretty evenly spaced
out over the second block. Each such byte input to the 2nd des pass
will avalanche to affect an entire 8-byte DES-output. (I am assuming
des is in ECB mode throughout.) Therefore, (des|tran|des|tran)(P) will
differ from (des|tran|des|tran)(P') in just 64 bytes, and those 64 bytes
will be pretty evenly spaced out over the 8k bytes of the second block.
Finally, we can see that C and C' will differ in the second block only
at 64 8-byte DES-outputs (corresponding to the 64 bytes which differ at
the input to the 3rd des pass). Pick one such 8-byte DES-output where
C,C' differ: suppose those two DES-outputs are x,x'. For each possible
DES key k, try decrypting x,x'; recognize the correct guess at k by the
fact that D(k,x) differs from D(k,x') in just one of the 8 resulting
bytes. This recovers the 56-bit DES key used in the 3rd des pass.
Strip off the final des pass to obtain known texts for des|tran|des, and
recover the 2nd-pass DES key with 2^56 more trial decryptions by using
a similar technique.
Did I misunderstand the proposed mode of operation? Any comments?
