Newsgroups: sci.crypt
Path: cactus.org!ritter
From: ritter@cactus.org (Terry Ritter)

Subject: Re: Strong Block Ciphers from Weak Ones: NxM DES
Message-ID: <1994Feb10.185728.23990@cactus.org>
Summary: Can Anyone Clarify?
Keywords: DES replacement, triple-DES
Organization: Capital Area Central Texas UNIX Society, Austin, Tx
References: <1994Feb2.071956.29014@cactus.org> 
Date: Thu, 10 Feb 1994 18:57:28 GMT



 In "Strong Block Ciphers from Weak Ones: NxM DES," which I posted
 to sci.crypt as <1994Feb2.071956.29014@cactus.org>, I proposed a
 2x2 DES construct something like this:

             A             B
             v             v
      k1 -> DES1    k2 -> DES2
             v             v
             C             D
              Exchange Half
             E             F
             v             v
      k3 -> DES3    k4 -> DES4
             v             v
             G             H

 (Yes, I am collecting references to prior proposals :-)


 Then, in 
 schneier@chinet.chinet.com (Bruce Schneier) forwards a response:


>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.


 Clearly, Biham is not impressed.

 However, the response seems obscure, even self-contradictory in
 some places.  For example, Biham says "an exhaustive search for the
 keys can be done just as in single DES" but then says that one
 requirement would be for 2^34 known plaintexts, which is certainly
 not a requirement for a DES keysearch.

 We would all like to find a cipher which was provably secure in
 every possible application.  But when that is not possible, we
 also realize that the cipher per se is not the entire security
 system.  If sending 2^34 messages under a single set of keys is a
 problem, we can arrange the rest of the system to not allow that,
 and simply use a conditionally-secure cipher in its secure area.
 Similarly, chosen plaintext may not be an issue in some or even
 many applications.

 However, before I open mouth wide and insert foot, I would like
 to be able to understand the attack that Biham describes.  I find
 the description of the attack confusing, and have not yet found
 an interpretation which will produce the asserted results.  For
 example, is this a key search attack?  (Surely yes.)  But if so,
 how can we assume that part of the key set is active but
 unreachable, while one DES key is available for searching?

 If anyone thinks they understand the situation, please contact me
 by email and try and clue me in.  Thanks.

 ---
 Terry Ritter   ritter@cactus.org