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

Subject: Re: Ladder DES
Message-ID: <1994Feb25.175146.1205@cactus.org>
Keywords: DES replacement, large blocks
Organization: Capital Area Central Texas UNIX Society, Austin, Tx
References: <1994Feb22.083353.26012@cactus.org> 
Date: Fri, 25 Feb 1994 17:51:46 GMT


 In  dbarber@crash.cts.com
 (David C. Barber) writes:

>An interesting post, but begs a question on why don't we want to
>use IDEA to replace DES?

 Speaking for myself, I have trouble *believing* that IDEA (or PES
 or IPES) is strong.  I am of course aware that my intuition of
 strength has little to do with reality.  However, since we cannot
 *test* or *prove* strength, the mere *feeling* of weakness is what
 every formal attack must be before it is born.

 As I reported on sci.crypt, I have performed some experiments on
 automatically attacking complex combining mechanisms.  I found
 that some apparently complex mechanisms are attackable *provided*
 their internal operations are linear.  For example, it is fairly
 easy to break PKZIP encryption which has had the output nonlinear
 operation removed.  I have yet to find a way around that section.
 Occasionally I issue a call for any literature anyone has seen
 on the solution of large systems of Boolean equations.  Surely,
 with sufficient information, even a system with nonlinear elements
 must be directly solvable.

 When I look at IDEA I see a structure which seems complex, but
 every operation is linear (with the possible exception of
 multiplication mod 2^16+1).  There is no substitution.  There is
 no selection.  The innermost four-operation transformation is the
 same (albeit with different keys) for each round, and it is the
 rounds which appear to build strength.  Thus, my intuition is to
 not trust IDEA.

 I don't know what the current results are (I think IDEA became
 PES, and weakness in PES resulted in IPES), but I have read the
 comments in:

      Lai, X. and J. Massey.  1991.  Markov Ciphers and Differential
      Cryptanalysis.  Advances in Cryptology--Eurocrypt '91.  17-38.

 In the conclusions (p. 38) we find:

      ". . . the true strength of the standard PES algorithm is of
      the order of 2^64 encryptions, a considerable reduction from
      the work that a cryptanalyst would expected (sic) in an
      exhaustive key search for the 128-bit key."

 I note that this is comparable to realizing that double-DES, with
 a putative 112-bit key, actually has a strength similar to a
 57-bit key.  Since double-DES has twice the expense of normal 56-bit
 DES, this was sufficient to make double-DES essentially useless.

 The improved IPES apparently does not fall to the same
 (differential) attack, so maybe it is better.  But maybe we can fix
 up double-DES without changing the internals of the proven cipher.

 If we believe that strong ciphers are possible, then we already
 recognize the ability to build a strong large cipher out of less-
 strong components.  If we can limit the intellectual distance in
 a cipher (from the base exclusive-OR and the final result), we
 might understand ciphers better, even at their lowest levels.

 If we can take a structure of known strength that we do believe in,
 and use it as a building-block in a relatively-simple construct
 which we can build a belief in, we can hope to avoid the need for
 the terrible depth of analysis required to certify an entire cipher.
 We have no public institutions set up to fund or organize such a
 certification.

 If it eventually comes down to the need for the banking industry
 to set up and fund a cipher certification facility, we may get to
 see just how badly the banks want to avoid government-designed
 secret cipher systems.



 Terry