Path: illuminati.io.com!uunet!cs.utexas.edu!not-for-mail
From: ritter@indial1.io.com (Terry Ritter)
Newsgroups: sci.crypt
Subject: Re: Toward Axiomatic Fenced DES (long!)
Date: 9 Jun 1994 03:49:31 -0500
Organization: UTexas Mail-to-News Gateway
Lines: 214
Sender: nobody@cs.utexas.edu
Message-ID: <199406090849.DAA18692@indial1.io.com>
NNTP-Posting-Host: news.cs.utexas.edu
In <2t2guc$l89@news.umbc.edu> olson@umbc.edu (Bryan G. Olson; CMSC (G))
comments on my comments on his comments on my comments on his comments
on my Axiomatic Fenced DES article:
(Obviously I have failed to communicate my overall argument.
I will try to put together something which will outline my approach
better, so that it will be clearer where I am trying to take this,
and, thus, what I may have failed to do. I had expected that the
reason for this stuff would be fairly obvious, even if the proofs
themselves were faulty.)
>:I *do not wish* to assume
>: a random selection, and therefore do not say that. I wish instead
>: to assume every possibility
>
>Fine. Phrase your assertions as the average of all elements in a
>given set.
Ahem. I was under the impression that the phrases "the average"
or "the arithmetic average" were in fact synonymous with "the mean."
Note that I wish to describe the population mean, not a sample mean.
Perhaps I should just say that.
>: >[...Terry:]
>: >: >: 4.7 THEOREM: (Probable change propagation.) Any change whatsoever
>: >: >: to the input value to a complete invertible substitution is likely
>: >: >: to change about half the bits in the output value.
>: >: >
>: >: >: (Proof: Changing the input value selects among all remaining
>: >: >: output code values. If the output is considered to be binary
>: >: >: bits, we expect about half those bits to change (2.9).)
>: >: >
>[...]
>: So the point of these comments was that I should change "likely"--
>: which may have an unintended meaning--to "expected"? Fine.
>
>It's worse than that. Here you neither specify a probability, nor an
>average over any set. The way the assertion is stated, it should mean
>that any complete invertible substitution should have this property.
Yes. That's correct, that's the way I want it, and that's what
happens.
It is standard practice to model a strong block cipher as a large
invertible substitution. The keyed part of this is the selection
of one substitution out of all possible substitutions. If we cared
about the structure of a particular substitution, there would be
better and worse keys, which would not be encouraging.
This is a different situation than the small, fixed and known
tables inside DES.
Given this amount of confusion, I have obviously failed to provide
a proper context for this exercise.
>A derangement is how I would model a change. In your definition you
>didn't say what your set of changes included.
OK. I sure assumed that developing section 2 in terms of "n-position
code values" and then "the number of elements which differ" would
introduce the context of element-change, instead of re-arrangement.
Not all possible code values can be produced by permutation from
any particular n elements. However, I will try to write a
description which will make my type of "change" crystal clear.
>: Oh, they fulfill *my* definition. Perhaps I have not communicated
>: that definition to you, or perhaps you would rather not see it.
>
>I was talking about what you wrote, not necessarily what you meant.
Naturally, *I* am stuck with addressing both.
>Ouch. You said any input change, not an average over all. With this
>modification I grant you that a block cipher has the avalanche
>property, as does the identity function, or for that matter, any
>permutation, and most functions. This is certainly not how the
>avalanche property is used in the literature.
This is indeed the same avalanche property which is described in
the literature. It may not seem to be described in these terms,
however.
>Is this what you meant by avalanche being an inherent property of
>an invertible substitution ?
>
> For any permutation P on the set of all n-bit codewords S, and any
> given n-bit codeword x, the average number of different bits between
> P(x) and P(y) over all y in S-{x} is:
> n* 2**(n-1)/(2**n -1)
Probably. I think I used the phrase "about half" or something
like it. I did this not to avoid working out the actual value,
but rather to relate it to the observational reality which is the
source of the definition "avalanche." Since avalanche does not
have a precise definition, it is also necessary to argue that any
particular equation produces the observed properties of avalanche:
About half the output bits change, on average.
>It would seem that to be useful, the definition of avalanche should
>be hold for some permutations and not hold for others. Certainly
>the way avalanche is used in the literature, this is the case.
I am describing the original avalanche. Presumably, it could
have picked up some rather strange implications as time has gone
on.
But, if there really were some permutations which were "better"
than others, then, when we model a strong block cipher as a large
substitution, we would have to say that some particular substitutions
would be "better" than others. This would imply that even strong
block ciphers would necessarily have keys which are better than
others, in a fundamental sense, which is not what we hope for at
all. In contrast, we normally think of keys as interchangeable
in all ways, and it is this property, along with their number,
which gives us security.
>: >Are you saying that ALL invertible permutations are bit mixers ?
>
>: Yes.
>
>So the identity function is a bit mixer.
Yes. But recall that it is my intention to speak of the set of
all possible invertible permutations. If the chosen one happens
to be the identity function, so be it. But, over all possible
choices, this set of functions is balanced and flat. Each input
bit affects each output bit to the same extent, on average,
guaranteed.
Note that if the substitution were non-invertible (a random
discrete function?) then we would have some form of sampling
distribution in the values in the function: probably binomial, or
effectively Poisson. This would make things much more difficult,
for then we would indeed have better or worse keys, depending on
particular substitution constructions. In this case we would
truly have an "expectation," instead of a mixing balance
guarantee.
>If
>the identity function is an invertible substitution, then it is not
>the case that being an invertible substitution makes a function a good
>block cipher.
If the invertible substitution is one of all possible such
substitutions, then, on average, about half of the output bits
change for a value change on any input bit. This is avalanche.
This is where it comes from. This is why it happens.
To be a good block cipher, a function must be invertible, and
also must be an arbitrary (keyed) selection among a huge number
of possibilities.
Now, in the same way that an additive stream cipher could have a
"confusion stream" of all-zeros for any arbitrary length (even
with a "really random" generator), it is technically possible to
build the identity permutation. If we believe that the shuffling
process is random-like, the chances of this are one in n!. That
is, for a simple 8-bit permutation, there is exactly one chance in
256! of getting the identity permutation. This is a big value.
But for a 64-bit permutation, there is one chance in (2**64)!, a
somewhat larger value. :) Yes, the situation exists. No, we
don't worry about it.
>You present no reason to believe that either fenced DES
>or your substitution boxes will have properties which are approximately
>average for invertible substitutions.
My substitutions are created dynamically by shuffling with a
large-state keyed cryptographic RNG. That gives *me* reason to
assume that the resulting substitutions will have the expected
distribution. We can discuss the distribution from RNG's, but
since these sequences are intended to be "individually independently
distributed," again, it is perfectly reasonable that they may
someday produce a counting sequence *while operating perfectly*,
and thus fail to change a substitution during shuffling. Indeed,
if we operate the RNG long enough, it *must* produce such a
sequence, or it is not producing iid sequences. We don't go
into stream cipher RNG's and modify them to not produce some
particular long sequence. If we did, we would give The Opponent
information about the resulting sequences.
However, note that the expected distribution is *not* the main
argument for Fenced DES strength. Indeed, the telling argument is
that, even in the worst possible case of any invertible permutation,
for any bit-change in, we get *at least* one bit change out,
*guaranteed*. (It was the pursuit of this sort of guarantee in
hashing functions which lead to the development of the CRC, and
this guarantee is limited by the size of the CRC polynomial.)
In Fenced DES, these changes are propagated directly into (and out
of) four independent DES operations. As long as we get one bit-
change into one DES, we don't care how many other bit-changes
there are; the result is the same (on average), because any
change of any number of bits will cause avalanche. This allows
us to "guarantee" overall avalanche if DES has it (again, note
that avalanche is a statistical property), and avalanche is what
we expect from a good block cipher. It is also what would happen
automatically, if we could afford to build and shuffle a huge
substitution table.
---
Terry Ritter ritter@io.com