Path: news.io.com!news.fc.net!news3.net99.net!news.cais.net!news.sprintlink.
+     net!cs.utexas.edu!not-for-mail
From: ritter@io.com (Terry Ritter)
Newsgroups: sci.crypt

Subject: Re: Variable Size Block Ciphers
Date: 23 Aug 1995 11:09:07 -0500
Organization: UTexas Mail-to-News Gateway
Lines: 112
Sender: nobody@cs.utexas.edu
Message-ID: <199508231608.LAA16883@tristero.io.com>
References: <419qs5$pej@lyra.csx.cam.ac.uk>
NNTP-Posting-Host: news.cs.utexas.edu

 In <419qs5$pej@lyra.csx.cam.ac.uk> rja14@cl.cam.ac.uk (Ross Anderson)
 writes:

>ritter@io.com (Terry Ritter) writes:
>
>>  For some time now I have been working with some apparently new
>>  ciphering structures which I call "Variable Size Block Ciphers."
>>  As the name suggests, these constructs can be made to cipher blocks
>>  of essentially arbitrary size (typically in byte-size steps),
>>  *without* changing the number of layers or "rounds" in the cipher.
>
>Two such ciphers appeared in 1993 - WAKE by David Wheeler and a
>proposal from Burt Kaliski and Matt Robshaw. They are both in `Fast
>Software Encryption', Springer LNCS 809

 I'm always honored by a response from Ross, and we've had several
 discussions over the past years, but this time I think he misses
 the point.  While Kaliski-Robshaw does handle large 1 KB blocks,
 we can search in vain for any reference to a size-parameterized
 design or operation on data blocks of dynamically-variable size.
 This is a particular design for a particular (fixed) size block.

 WAKE is an autokey stream cipher.  In a stream cipher, diffusion
 can occur only to that part of the stream following a particular
 datum.  In contrast, in a good block cipher, every input bit is
 diffused throughout the block, even to "earlier" bits.  This means
 that a block cipher can take advantage of any and all of the
 uniqueness in a plaintext block.  In this respect, Variable Size
 Block Ciphers are true block ciphers.


 Now, I know that a new paradigm like this is bound to cause some
 irritation and off-hand rejection.  Nevertheless, there are
 significant advantages to a VARIABLE-SIZE block cipher:

    1. There will be some applications in which data-expansion can
       be eliminated.

    2. There will be other applications which can avoid buffering
       by directly ciphering application-dependent field sizes.

    3. There may be a few applications (perhaps database ciphering,
       or voice CODEC's) which actually can use a cipher of
       dynamically-variable size.

    4. A single design can handle all of the above, as well as
       64-bit blocks, 256-Byte blocks and 1 KB blocks.  Thus, a
       single cipher can handle database ciphering, disk sector
       ciphering, and communications.

    5. Tiny versions of the same cipher can be exhaustively studied,
       and this can be done by parameterizing production-capable
       code.  (Validating results between this and the actual
       production code then validates the high-efficiency
       realization.)


 There are other advantages to VSBC technology:

    1. These ciphers can closely approach the ideal of "overall
       diffusion," in which a change to *any* input *bit* changes
       *every* output *bit* with probability 0.5.  This is what
       we should expect and demand from a quality block cipher.

    2. Ciphers which depend on algorithmic operations -- even
       nonlinear operations -- seem more likely to be vulnerable
       to attack than ciphers which contain massive internal state.

    3. VLSI design likes regular structures, and also likes regular
       relationships between structures.

    4. Additional independent strength is easily added with new
       layers, without disturbing the rest of the design.  In
       contrast, simply increasing the number of rounds which do
       the same old algorithmic thing may not improve strength at
       all.  (Is a 32-round DES stronger than 16-round DES?)

    5. VSBC technology produces a clear, regular, understandable
       structure in which the role of each element can be addressed
       mathematically.  In contrast, irregular and ad hoc designs
       depend on the mysterious strength of complex manipulations.
       While such manipulations may be "mathematical," they often
       do not carry any useful analytical properties.  Absent a
       comprehensive theory of design, such ciphers can only be
       analyzed individually, which is one of the major problems
       that cryptography has today.


 On the other hand, in the same proceedings, Massey's "SAFER K-64:
 A Byte-Oriented Block-Ciphering Algorithm" seems to come closer to
 my (earlier) work.  In this we see a FFT-like mixing array similar
 to one I suggested in the first Block Mixing Transform article in
 sci.crypt in the Spring of 1994.  (This was admittedly after
 Massey's paper was presented, but before I had access to it.)

 In SAFER K-64 we see a "Pseudo-Hadamard Transform" which is
 certainly as weak as my Balanced Block Mixers, but -- unlike my
 mixers -- also unbalanced.

 SAFER K-64 does not use "fencing" layers (arrays of keyed
 substitutions), and does use iterative "rounds" which my ciphers
 do not.  Still, if somebody has a problem with weak mixing (as a
 lot of people did on sci.crypt last year), I encourage them to
 take it up with Massey.  :-)


 There are VSBC example flow-diagrams on my web page.

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