From: (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
Message-ID: <>

 In <2t2guc$> (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

 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,

>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

 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,

 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

>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