From daw@cs.berkeley.edu Sat Jun 28 23:38:12 PDT 1997 Article: 1043 of isaac.lists.cryptography Path: news.isaac.cs.berkeley.edu!not-for-mail From: daw@cs.berkeley.edu (David Wagner) Newsgroups: isaac.lists.cryptography Subject: Re: cracking n-DES? Date: 27 Jun 1997 23:04:12 -0700 Organization: ISAAC Group, UC Berkeley Lines: 46 Sender: daemon@abraham.cs.berkeley.edu Approved: mail2news@news.isaac.cs.berkeley.edu Distribution: isaac Message-ID: <5p2666$br@joseph.cs.berkeley.edu> References: <199706272331.TAA08744@smb.research.att.com> <3.0.2.32.19970627232231.00ae15a0@cybercash.com> NNTP-Posting-Host: abraham.cs.berkeley.edu X-Authentication-Warning: blacklodge.c2.net: majordom set sender to owner-cryptography@c2.org using -f In article <3.0.2.32.19970627232231.00ae15a0@cybercash.com>, Carl Ellison 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? From daw@cs.berkeley.edu Sat Jun 28 23:39:14 PDT 1997 Article: 1047 of isaac.lists.cryptography Path: news.isaac.cs.berkeley.edu!not-for-mail From: David Wagner Newsgroups: isaac.lists.cryptography Subject: Re: cracking n-DES? Date: 28 Jun 1997 09:15:42 -0700 Organization: ISAAC Group, UC Berkeley Lines: 18 Sender: daemon@abraham.cs.berkeley.edu Approved: mail2news@news.isaac.cs.berkeley.edu Distribution: isaac Message-ID: <199706280821.BAA00727@joseph.cs.berkeley.edu> NNTP-Posting-Host: abraham.cs.berkeley.edu Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Authentication-Warning: blacklodge.c2.net: majordom set sender to owner-cryptography@c2.org using -f X-Mailer: ELM [version 2.4 PL25] In article <199706280618.CAA06654@jekyll.piermont.com> you write: > > I have to study > Dave's attack more, [...] > Here's the cliff notes: You exploit a lack of diffusion. You put in a one-byte difference in the plaintext (say). Each ECB-DES layer can only increase the number of bytes that differ by a factor of 8 (and then the trans re-shuffles them around). After two des|trans passes, you've only got 8^2 = 64 bytes differing, out of a total of 8192 bytes per "trans permutation block" -- that's very minimal avalanche. Now you just guess the last DES key, peel off the last layer, and check whether the result has the reduced-avalanche pattern that you expect to see after 2 passes.