Newsgroups: sci.crypt
Path: cactus.org!cs.utexas.edu!howland.reston.ans.net!europa.eng.gtefsd.com!
+     news.umbc.edu!eff!news.kei.com!ddsw1!chinet!schneier
From: schneier@chinet.chinet.com (Bruce Schneier)

Subject: Re: Strong Block Ciphers from Weak Ones: NxM DES
Message-ID: 
Keywords: DES replacement, triple-DES
Organization: Chinet - Public Access UNIX
References: <1994Feb2.071956.29014@cactus.org>
Date: Mon, 7 Feb 1994 16:59:28 GMT
Lines: 53

In article <1994Feb2.071956.29014@cactus.org>,
Terry Ritter  wrote:
>
>          Strong Block Ciphers from Weak Ones: NxM DES
>               A New Class of DES Operating Modes
>
>                          Terry Ritter
>                        January 31, 1994


Eli Biham has this comment on Ritter's paper:


I claim that the cryptosystem described in your email is not stronger than
a single DES, when it uses only two passes -- i.e., Mx2 DES.

Ritters cryptosystems Mx2 DES have the same security as of a single DES,
and an exhaustive search for the keys can be done just as in a single DES!
given the appropriate encryptions.

Either:
1. two pairs of chosen plaintexts. One block of the each pair is fixed,
and the other varies.
2. or, 2^34 known plaintexts (in which the birthday paradox predict the
existance of the data required in item 1).

The attack:
Since one block is the same in both members of a pair, the input to the
second pass of encryption differ only in 32 bits of each block for 2x2, or
in more bits for Mx2, m>2. Thus, exhaustive search of the second pass
keys is feasible, looking for the known (in)difference.
Then, exhaustive search for the first pass keys can be done easily.
The total complexity of exhaustive search is M*2*2^56+M*2^56=3*M*2^56 for
finding all the keys.

The attack can be applied also as a chosen ciphertext attack, and thus it
can be applied in a CBC mode just as in item 1.

The complementation property of DES remains, and might be used to reduce
the complexity by a factor of two at least in the chosen plaintext case
(it might also work in the known plaintext case with more data, but I did
not calculate it).

He claims that a large block size is better for security. That's not true,
at least without some other method of strengthening the wider cipher against
attacks based on the larger block size (and smaller avalanche caused by the
larger blocksize, etc.)

Best regards,

Eli