Path: illuminati.io.com!uunet!cs.utexas.edu!not-for-mail
From: ritter@io.com (Terry Ritter)
Newsgroups: sci.crypt

Subject: Re: Algorithms
Date: 18 Nov 1994 03:13:02 -0600
Organization: UTexas Mail-to-News Gateway
Lines: 138
Sender: nobody@cs.utexas.edu
Message-ID: <199411180913.DAA06647@pentagon.io.com>
NNTP-Posting-Host: news.cs.utexas.edu

 In <1994Nov15.231930.1060@Princeton.EDU> dawagner@tucson.princeton.edu
 (David A. Wagner) writes:


>>  The sweeping generalization that Triple <anything> is *necessarily*
>>  stronger than <anything> on its own is false by contrary example,
>>  and the groupiness of <anything> is irrelevant.
>>
>
>I agree; but that's not the point here.

 It may not be *your* point, but it *is* *my* point.


>It does seem reasonable
>to believe that triple DES is stronger than DES.  Why?  Because
>crypto experts have tried their darndest to break triple DES,
>without much success.  Because single DES seems to be a very
>well-designed primitive -- except for the short keylength.

 There are several more problems with DES: one is the small block
 size.  If 2**56 keys is a problem, 2**64 elements should be a
 similar problem.  Why do we not consider 2**8-element tables
 secure?  Are 2**32-element tables secure?  I claim that if 2**64
 elements is not a problem now, it soon will be, in any case
 certainly long before the next 20 years.

 Yet another problem is the internal use of tiny, fixed (and thus
 well-known) substitution tables.  This is just asking for trouble.
 We know how to do better than this, and we can afford to do far
 better, even as the original designers could not.


>[For example, read about how DES becomes more resistant to both
>differential and linear cryptanalysis when more rounds are added.
>Read about how the best attacks on two-key triple DES require
>2^56 memory, 2^56 chosen plaintexts, and 2^56 operations; or else
>(from memory here) much much more than 2^56 operations, and a whole
>bunch of known plaintexts -- see Crypto '90.  Anyone know of any
>attacks on three-key triple DES better than brute force?]

 Again, *this* is beside my point.

 If I had a workable attack I could defeat your argument, but
 requiring me to have and disclose such an attack before you will
 move to a stronger cipher must defeat your own security.  It
 is instead necessary to anticipate attacks, instead of simply
 responding to attacks as they become disclosed.  Attacks may
 exist and we may not know them, and yet, to provide good crypto,
 we must defeat them anyway.  Thus we must assume that such
 attacks exist.  This is the way the game works.


>Ok, so what are the real underlying problems, in your opinion?

 First, much of the commercial security world has been essentially
 locked into DES because it is the only cipher "certified" for use
 by the US Government.  Because most systems are not set up to use
 multiple ciphers, the idea that DES has become attackable is scary
 and rejected.  DES is being used beyond its advisable life.

 We should at all costs avoid being trapped into yet another single
 standard cipher.  Instead, we should standardize the ability to
 negotiate a mutually-agreeable cipher by textual name, instead of
 some number assigned by a standards body.  Standard interfaces
 should allow the dynamic replacement of ciphers which are found
 weak, as soon as such indications occur.  Replacement ciphers which
 defeat new attacks could be made available in weeks or months, and
 used automatically.

 Next, Triple-DES is being promoted as the major savior, since
 it will essentially function like DES, albeit with more key
 material.  Surprisingly, many systems people hate Triple-DES,
 because of the increased processing overhead.  It is a facile
 argument to say "get a larger computer" when it is difficult to
 keep up with processing growth as it is.  Cipher execution is
 an obvious overhead which has the potential to delay *every*
 *transaction* in a modern data-based organization.  Because of
 the overhead of the proposed replacement, the old solution is
 being retained in the face of evidence of weakness.

 Nevertheless, Triple-DES is being touted as the saving force,
 based on assumptions that it is more secure than DES alone.
 As usual, there is no proof of this.  In fact, it seems very
 reasonable to me that if some defect is found in DES, the use of
 DES three times may not hide that defect.  There are alternatives,
 and they include using larger, stronger ciphers, perhaps based on
 DES itself, or to at least use three levels each with a different
 block cipher, or, more generally, totally different, much-stronger,
 and much-faster ciphers.

 At least one attack exists in which Triple <block cipher> is not
 stronger than <block cipher> alone, and that is an attack on the
 overall permutation.  We assume that that attack is prevented by
 using CBC.  But it is a real example of a real attack, and we have
 no particular reason to believe that it is the only possible attack
 in that class.

 In fact, the function of a block cipher is to emulate, as well as
 possible, a huge keyed substitution table.  It should be evident
 that any simple machine can do this only imperfectly.  With
 increasing advances in processing, it may be possible to start
 to delineate that imperfection.  In particular, it may be that
 the output of the cipher is in some way defined or bounded in
 permutation space.  Such a bound might be large enough to not
 affect DES itself, and yet make Triple-DES almost as weak as DES.

 This is a situation which separates cryptography from classical
 Science:  In Science, it is expected that something not be stated
 unless it is proven true in some way.  Alas, there is no final
 proof in cryptography, yet we hear claims just the same, because
 it is necessary to somehow describe something we cannot measure.
 The conventional approach:  "DES is strong unless you have a
 provable attack" does not serve us well to define the cipher of
 the future.  Not only do we not know whether or not someone has
 some effective attack *today*, we cannot even know what *tools* will
 be available for future analysis and understanding.  Our only hope
 of cipher success is the design of ciphers which are vastly stronger
 in every way we know, thus hopefully to serve well into tomorrow.

 I think we want new ciphers which will last at least a couple of
 decades.  We are constrained to build these ciphers only on the
 basis of research that we know, research which was conducted in the
 past, with the capability of past tools.  But the new ciphers must
 survive in an environment of the future, with massively more-
 effective tools.  We all know that past research (especially the
 sort of negative information we get in cryptography) does not
 necessarily imply the outcome of the future.  We know DES is weak,
 and we know DES is small, and if we are going to fix the problem
 of weak DES, we should really *fix* it, instead of doing the same
 old thing (three times as hard) and wishing and hoping it will work
 for the next twenty years.

 ---
 Terry Ritter   ritter@io.com