Path: news.io.com!uunet!in2.uu.net!news.mathworks.com!gatech!swrinde!cs.
+     utexas.edu!not-for-mail
From: ritter@io.com (Terry Ritter)
Newsgroups: sci.crypt

Subject: Variable Size Block Ciphers II
Date: 26 Aug 1995 02:41:01 -0500
Organization: UTexas Mail-to-News Gateway
Lines: 72
Sender: nobody@cs.utexas.edu
Message-ID: <199508260740.CAA19029@tristero.io.com>
NNTP-Posting-Host: news.cs.utexas.edu

 There appears to have been some confusion with respect to the
 short sci.crypt introduction to the Variable Size Block Cipher
 designs:

 A casual examination of the fixed-size 80-bit examples in the
 "full" HTML document should indicate that each substitution is
 intended to be a separate keyed (shuffled) table.  It is also
 mentioned that a dynamically-variable-size design would dynamically
 select a table for each operation from an array or heap of
 separately keyed tables.  Saying that the structures are based
 on similar columns is not intended to mean that all tables at
 each level are the same!

 Currently, I am less interested in strength than overall diffusion.
 My point is that it seems amazing -- wondrous -- that an overall
 bit-level diffusion effect can be generated for an essentially
 arbitrary block width by a fixed-depth structure.

 Now, it is obvious that the diffusion "bandwidth" is limited by the
 number of diffusion paths, so this may not be "true" diffusion in
 some sense.  (Perhaps a 10-diffusion-layer structure would come
 closer.)  However, to the extent that the diffusion we produce cannot
 be externally *distinguished* from "true" diffusion, it may be good
 enough.  Certainly single-bit overall diffusion is often considered
 a worst case, and that is demonstrably present or closely approached
 in all these examples.

 To the extent that the diffusion itself is linear (in the first
 and third examples), the results are rendered nonlinear at each
 level.  In contrast to the comments in Kaliski-Robshaw (which I
 have recently re-read several times), I would expect that a fencing
 array of keyed substitutions which protects a true nonlinear
 overall diffusion *should* be strong.  Thus, *if* we can protect
 the input from attacks intended to separate the individual elements,
 and then produce a nonlinear overall diffusion, a single subsequent
 fencing layer should be sufficient for strength.

 In the first example, I am of course aware that attacks on, say,
 the first two elements could produce values which "cancel out" and
 thus not conduct further diffusion.  However, a zero exclusive-OR
 result is just one of the values we should expect to get at *any*
 particular stage.  We would expect that *any* substitution result
 could zero-out a confusion-chain at *any* level.  Indeed, this
 happens all the time.  My feeling is that we should consider zero
 just another value; it is not a lack of diffusion, it *is* the
 diffusion.  The bit-level diffusion experiments do not show a
 problem.  Perhaps some other experiment would.

 At this point I am not greatly concerned, but of course a lot of
 analysis is still needed.  If it turns out that there is a problem,
 I expect that adding one or more sets of confusion / diffusion
 stages should be a big help.  One advantage of this type of
 architecture is that strength can be added without re-design of
 the rest of the cipher.  Apparently.

 These Variable Size Block Cipher designs are *new* structures.
 They have not had 20 years of analysis.  They have not had 20 years
 of understanding about when, and when not, they should be used.
 It is ridiculous to expect them to conform to the level of analysis
 that DES has collected.  They are not Feistel block ciphers!

 After more than six years, I feel that we finally have a good
 handle on the weaknesses of Dynamic Substitution, which was
 fundamentally-new stream-cipher cryptography in 1990, and still is.
 It will be some time before the same understanding can occur with
 respect to Variable Size Block Ciphers.  Any and all insights
 would be appreciated.

 ---
 Terry Ritter   ritter@io.com   http://www.io.com/~ritter