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