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: 27 Aug 1995 15:11:59 -0500
Organization: UTexas Mail-to-News Gateway
Lines: 296
Sender: nobody@cs.utexas.edu
Message-ID: <199508272011.PAA17751@tristero.io.com>
References:
NNTP-Posting-Host: news.cs.utexas.edu
In John Kelsey
writes:
>- From what I've seen of this construction, it seems odd to me that
>you don't need more rounds to handle larger blocks. (Intuitively,
>getting full diffusion through a 256-bit block should take more
>work than getting full difusion through a 64-bit block.)
Apparently there is "diffusion," and then there is "diffusion."
It is certainly clear that a substitution table will conduct any
input bit-change to an output bit change. It is also clear that
an exclusive-OR chain *must* conduct any of those bit changes to
all subsequent elements. Given shuffled substitution tables at
the next level, it is clear that this will produce a randomized
result (in the subsequent elements).
My point is that experiments show that multiple layers of this
structure test very much like a "true" overall diffusion. To avoid
particular attacks, it may be that at least two layers must go in
each direction, leading to five confusion layers. But, once we
have full nonlinear diffusion, one more confusion layer should
provide "strength."
>Unfortunately, I don't have access to a web browser that will let
>me view images, so I'm stuck with ASCII diagrams--so I may be
>missing something.
Ah, now I see the problem. I assumed that I was the last person
in the known universe to have webbing capabilities.
Although I have used ASCII diagrams in the past, I was never
satisfied with the diagrams I made for these VSBC things. The
.GIF's turned out *so* much better that I didn't bother putting
ASCII diagrams in the HTML document on the web page. I didn't
(and don't) really intend to post the design document to the
newsgroup.
I believe that it is academically important to have webbing
available, at least occasionally. To do this, one first needs an
Internet Service Provider which handles SLIP or PPP (preferred)
logons. Next, one needs a 386/486/P5 PC, typically one running
Microsoft Windows. Then, one needs protocol "middleware" like
Trumpet Winsock (shareware), which the ISP may provide. Last, one
needs a browser, typically Netscape, which is free for individuals.
That's pretty much it, and if you know somebody with a similar
set-up, you can probably get up in an hour or so. It *is* worth
the effort.
>> 1. There will be some applications in which data-expansion can
>> be eliminated.
>
>This is do-able with any fixed-length block cipher, if you're
>willing to do some extra work in encryption and decryption. If you
>eliminated data expansion by changing the block size of the last
>block, it seems like you'd be saving yourself little work.
Define "do-able": Typically this is done by switching to stream-
cipher mode for the last block. But if this were really acceptable,
it would be used for the whole message: Normal stream-cipher mode
has no data diffusion at all, compared to the full diffusion we
expect and demand in a block cipher.
So, we save having two modes, potentially additional hardware for
one, and the complexity of switching between them. There is some
advantage; just how much depends on the individual case.
These advantages are cumulative: a new cipher need not be the
best in every possible category. Nor do the VSBC designs need to
better every known cipher in every way. In certain important
applications, for example database ciphering, they could be a
significant improvement over anything now available. In other
applications, they could be at least competitive.
>> 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.)
>
>All four of these depend on the idea that it's possible to come up
>with equally-secure versions of your block cipher for any given
>size.
These are advantages relating to variable size, which is in fact
the issue I have addressed in these designs.
>I really would like to see some explanation of why you are
>convinced that this is the case.
"Convinced" is not a word I would use. I guess that I currently
accept (as a reasonable basis for action) that a full, nonlinear
balanced, bit-level diffusion implies overall "strength" in just
one more confusion layer. I can measure diffusion experimentally.
I don't know how to measure "strength," and neither does anybody
else who is talking. It is consequently difficult to build a
cipher with measurable "strength."
>It's easy to create variants of
>Blowfish, SAFER, and many other ciphers with different block sizes,
>but it looks like changing the block size changes the security
>properties of these ciphers, perhaps requiring more rounds to be
>secure.
In which case, "creating variants" does not seem all that "easy."
Indeed, most Feistel-style block ciphers will have power-of-2
block sizes. One *can* use smaller mixings, of course, but that
seems contrary to the usual practice of a broad half-block mixing.
It is *NOT* easy to diddle with existing block ciphers to provide
a god block cipher for data of different sizes. One can, of
course, always use a stream cipher, but then one gets into the
"re-origination" issue (which I addressed in my Penknife commercial
stream cipher for e-mail).
"Re-origination" refers to the a cipher starting in the same state
multiple times. This sort of thing is necessary when we want to
provide for messages being ciphered in some unknown sequence (like
network packets). With a stream cipher working on bytes, this
immediately leads to an attack in which The Opponent can collect
many messages which start out in the same way. We can think to
include other data (essentially keying data) with each "message,"
but this may not always be possible. On the other hand, if we
have the ability to cipher blocks of variable size, most of
which are very large (20..1500 Bytes), a similar attack is
difficult or impossible.
>> 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.
>
>Here, you're just saying that you have full diffusion, right?
The word "just" in this sentence implies a fact not in evidence.
It is not trivial or easy to get full diffusion. Admittedly,
diffusion appears as a side-effect in Feistel-type iterated block
ciphers, so one might conclude that it just "happens" as a side-
effect of a strong cipher. But diffusion is *necessary*, and it is
difficult to discuss diffusion in the context of Feistel ciphers
*because* in these ciphers diffusion is only a side effect.
>This
>is a necessary but not sufficient condition for block cipher
>security, since without full diffusion, it's possible to perform
>various divide-and-conquer attacks on the block cipher.
Right. My point exactly.
But I would further say that, once one has a non-linear, balanced,
full diffusion, then one more confusion layer (e.g., a layer of
keyed fencing substitutions) should be sufficient for strength.
At least that seems to me to be a reasonable position given the
current evidence.
>> 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?)
>
>Can you explain this a bit more clearly? I'm not too sure I
>understand how you can be more certain that adding layers in your
>design adds strength, than you can be that adding rounds to DES
>adds strength.
Triple-DES is not just DES with more rounds, it is DES with more
rounds and also more *keys*. Simply adding rounds to DES is not
the way to improve strength.
On the other hand, if we add new diffusion and confusion layers to
an existing VSBC design, we typically add a new layer of keyed
substitution operations. This is additional state which The
Opponent must confront.
It would be difficult to deny that, if four layers have strength
x, then five layers must have strength x+delta or x*delta or
x**delta or some such. The real issue is whether the delta is
low or the advantage weak, for then we may need to add too many
layers to be practical. I can only say that my bit-diffusion
experiments indicate good diffusion (in *some* designs; a
surprising number did not) with as few as three one-way diffusion
layers. I take full diffusion as a precursor to strength.
>> 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.
>
>I would say that a number of block cipher designs fit this
>description, such as balanced Feistel networks with subkeys applied
>outside the f() functions, block cipher designs based on cellular
>automata, etc.
Fine. Let's just test this, shall we? Given the well-known
definition for DES, please provide a formula to describe the number
of rounds needed for "full diffusion." Also provide formulas or
other reasoning showing that the resulting diffusion is "balanced"
in each bit. Now extend these formulas for arbitrary functions f().
Given *any* keyed (randomized) substitutions, I suggest that we
can make a good argument that at least three one-way diffusion
layers (in two directions) and four confusion layers will produce
something approaching experimental "full diffusion." (I have so
far approached the issue experimentally.)
Another such set of layers would then protect against "fix
in-the-middle" attacks, but these are already impractical in the
context of a huge block size and huge keyspace. Indeed, the
ability to have and easily use a large keyspace is another
advantage of the VSBC design over Feistel designs. (My
experimental versions all use a 992-bit keyspace and a huge
Jitterized RNG like that in my Cloak2 commercial design to
shuffle the tables.)
One of the main problems with analyzing Feistel designs is that
their structure supports arbitrary non-invertible f() functions.
This is a problem because such functions do *not* guarantee that
diffusion will *necessarily* be propagated in each mixing.
This makes it difficult to make strong statements about diffusion
without restricting f() to functions of some particular form.
Presumably there are multiple such forms which support such
reasoning, but we have not been given the Feistel design handbook.
With respect to Cellular Automata, it seems to me that the bloom
has faded from the CA rose. CA designs were often touted as great
stream-cipher RNG's which could never be analyzed, but they turned
out to be just as analyzable as most other state-machine RNG's.
>> 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. :-)
>
>Actually, you could go back to the earliest work on SP networks--
>fixed bit permutations are weak mixing layers, but nobody seems to
>doubt that they're useful in designing strong ciphers.
Well, I doubt that anybody really denies that permutations can
be useful. In this particular case, I was looking for mixing
transformations which would guarantee to propagate diffusion
(element diffusion) across a large block. Then these element
values were *confused*, either by DES or by keyed substitutions.
The fast, scalable, invertible, balanced transformations which I
found were linear (although I subsequently have used an order-256
randomized Latin square which is of course exceedingly nonlinear
but also non-scalable). The argument was made that the mixing
transformations *obviously* did not contribute to strength
*because* they were linear. This argument was specious, because
the transformations were not *intended* to provide primary strength
per se, but were intended mainly to provide *provably* balanced
diffusion *as a precursor* to strength. This result was then fed
into keyed substitutions which I believe *do* provide strength
*under those proven conditions*.
This is a completely different design strategy, one which separates
confusion and diffusion. The advantage is that we *can* generate
*provable* and understandable small confusions. We can also
generate *provable* and understandable diffusion of various kinds.
Then we can combine these things. The one-way chain-style
diffusion used in the VSBC designs follows that same path.
---
Terry Ritter ritter@io.com http://www.io.com/~ritter