From: (Terry Ritter)
Newsgroups: sci.crypt

Subject: Re: Toward Axiomatic Fenced DES (long!)
Date: 6 Jun 1994 01:10:21 -0500
Organization: UTexas Mail-to-News Gateway
Lines: 319
Message-ID: <>

 In <2stndb$> (Bryan G. Olson; CMSC (G))

>Maybe I'm nit-picking again, but if you want to re-include stuff I
>edited out of your post, please use a different annotation mark from
>what you use to denote my writing.

 You say that if I want to include *my own* previously-posted stuff,
 in *my own* article, I should use *your* formatting convention?

 Most conversations on Usenet do not use different annotation marks
 for each individual author, even though that might appear to be

 Of course, I am sorry if I confused anyone.

>:   >When no
>:   >distribution is given, we generally assume the uniform distribution.
>That's only if you do say, as I did, that the selection is at random
>from some set.  If you don't use the language of statistics the
>default assumption is universal quantification, or in some contexts
>existential quantification.

 This will probably fall on deaf eyes, but I *do not wish* to assume
 a random selection, and therefore do not say that.  I wish instead
 to assume every possibility, which is, of course, the ultimate
 uniform distribution.  This is statistical in the sense that I can
 report some statistic values, and I can do this independent of any
 random selection.  If someone later wishes to make some "random"
 selections, statistics would tell them to expect to sample the set
 of all possible results, which I quantify in terms of mean and

 It may be that, at some point, it will be necessary to introduce
 random selection.  I wish to postpone that as long as possible.

>: > 2.7  THEOREM:  (Position difference counts.)   The number of
>: > n-position code values which differ in exactly m positions is
>: > (n)          m
>: > (m) * (|S|-1) .
>: >
>I didn't pick on this one, but you better say "from any given code
>word", or it's not clear what they differ from.

 Good comment.

>The first line of your proof asks us to assume the theorem is true.
>From this assumption you derive something known to be true.  So ?
>If you derive the result from something true, that's a proof; if
>you derive something false from the assumption the theorem is false,
>that's also a proof.  That the theorem implies something true is
>not a proof.  I tell my students to be clear as to whether each
>line is something you know, or something you want to prove.
>:  This proof (2.9) looks good to me as it stands.

 I'm not at all sure that ask that assumption.  I do ask one to
 assume that two expressions which are identical necessarily have
 identical properties.  If one is expressed as a binomial, the
 other necessarily has a binomial distribution.

 Alternately, from the disputed proof it is obvious that simple
 algebraic manipulations can convert 2.7 into the binomial form.
 Since this would clearly define the distribution, I fail to see
 the distinction.  In any case, including the actual algebra is
 probably overkill, in which case the proof itself is similar to
 the one given, less the initial assumption comment.

>: >:  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).)
>: >
>: >Not true.  The identity function is a complete invertible permutation.
>: >I can give you many input changes which result in significantly less than
>: >half the output bits changing.
>: >
>: >You need some idea of probability here.
>:  I imply that in "expect."  I take the expectation to be the
>:  arithmetic average over all possibilities, each one taken once.
>You don't even say "expect" in the theorem, only the proof.  Without
>the idea of probability you can't assume all the remaining output
>codes are equally likely.

 So the point of these comments was that I should change "likely"--
 which may have an unintended meaning--to "expected"?  Fine.

>: >:  4.8  DEFINITION:  AVALANCHE is a statistical property of a discrete
>: >:  function in which any change whatsoever on the input is expected to
>: >:  produce a change in about half the bits in the output value.
>: >
>: >This one is going to be hard to fix.
>:  It's a *definition*: there is nothing to fix.
>It's a bad definition.  What discrete functions have this property ?

 All block ciphers.

>: >For any permutation on n-bit
>: >strings (n>0) there exists some input change which will flip just one
>: >output bit.  Proof: for permutation P use the change:
>: >            P ; flip-first-bit ; inverse-P.
>:  Yes, I would say this is known.  For a complete 8-bit substitution,
>:  there are in fact eight.  See 2.8:
>: > 2.8  EXAMPLE:  The number of 8-bit binary codes which differ in m
>: > bits is:
>: >
>: >      distance     count
>: >            0         1
>: >            1         8
>:                        ^--------- see!
>: >            2        28
>: >            3        56
>Well, here's another:
>        P; if first bit is one, flip-second-bit,
>           otherwise flip-third-bit; inverse-P.
>Did you count that one among your 8 ?

 Are you trying to be cute?  The 256-element set of an 8-bit code
 is almost hand-enumerable.  It is easily checked exhaustively by
 the simplest computer.  Do *you* think there are more than 8 code
 values which differ in one bit?  If so, let's see one.  Do you
 dispute the truth of 2.7 and 2.9?  Or are you just trying to
 confuse the issue?

>(Hmm, given a permutation P(x) on (n-bit) codewords, how many
>derangements D(x) of the codewords have the property that for all
>codewords x, P(x) differs from P(D(x)) in exactly one of the n bit
>positions ? )
>Maybe you better tell us exactly what is in the set of any changes.

 The set of changes is the set of all possible code values less
 the current code value.

>More to the point, if there is always some change induces a one-bit change
>in the output of P, then no P on codewords of more than 2 bits can fulfill
>your definition of having the avalanche property.

 Oh, they fulfill *my* definition.  Perhaps I have not communicated
 that definition to you, or perhaps you would rather not see it.

 Avalanche is necessarily defined over all possible input changes,
 for any possible original value, and all possible results.

>You admit that 4.7 is talking about the average over the set of all
>permutations of n-bit codewords.  You can't apply it to an arbitrary

 Actually, the 2**n - 1 possible *changes*.  Which is why I use

 Probably the way to formalize this is to prove the distribution
 for the changes instead of all possibilities, or show that the
 difference is on the order of 1/2**n.  This should not be too
 hard.  That is, the distribution of changes is all 2**n possible
 code values less a single code value which is origin of those
 changes.  Every code value but one is a change from any
 particular code value.  Over all possible origin code values,
 each resulting code value occurs the same number of times.

>Well, if you want to know how much information you need to determine
>one permutation on the set of n-bit codewords, given that all such
>permutations are equally likely, it's approximately:
>                n * 2**n  bits.

 No.  I want to state that in order to define even one element of
 a substitution one must have some information which correlates
 input with output.  This is actually an interpretation of the
 definition, but is one basis for an implication of "strength."
 In the case of Fenced DES, if we assume that the internal block
 cipher is "strong," we can then conclude that there will never
 be information linking input and output values, so even small,
 simple permutations cannot be developed except by exhaustion.

>Don't take the large size of this number as good news.  It means that
>when we design ciphers, we have to deal with that very small subset of
>permutations which can be specified in a reasonable amount of space.
>Numbers we get from averaging over all permutations may not apply to

 I do in fact deal with the set of all 256-element permutations
 which can be developed by shuffling using a keyed cryptographic
 random number generator.  True, the size of that RNG is only 992
 bits, 2**992 instead of 256!**32 (for the 32 substitutions in
 4x Fenced DES).  If you were a cryptanalyst, would you take this
 as good news?  I can use a larger RNG . . . .

 It is necessary, of course, that substitutions not be related for
 the purpose of cryptanalysis.  Accordingly, the first action of
 the shuffling system is to shuffle a list of substitutions, and
 then shuffle the substitutions in that order.  This is, by itself,
 a 32! or 117-bit keyspace, before we get to an exploitation of any
 relation between actual substitutions.

>: >:  5.2  THEOREM:  An invertible substitution is a bit-mixer.
>: >
>: >May or may not be.
>:   >5.1  DEFINITION:  A BIT-MIXER combines multiple input bits such
>:   >that each output value is defined by each and every input bit.
>:  OK, you might like "function of" or a more explicit rendering.
>:  Still, the point is clear.  The output value from a substitution
>:  is "dependent upon" or "a function of" each and every input bit.

< deleted by Bryan; re-introduced by Terry; notation by Terry >
>[:] However, upon reflection, I think the definition is insufficient
>[:] to capture my real intent, so this is something I will have to
>[:] work on.  Note that the entire purpose for this line of reasoning
>[:] is reflected in the comment of 12.2:
>[:]>      (Comment:  DES with a known key is an example of a block
>[:]>      mixing transform with absolutely no strength at all by itself,
>[:]>      which nevertheless adds strength through bit mixing.)
>[:] which is significant because of previous questions of whether a
>[:] mixer without any "strength" can have any cryptographic advantage.
>[:] This development also justifies the examination of Block Mixing
>[:] Transforms which have no "strength" but nevertheless mix.

 In other words, these particular results, while interesting or
 even significant, have very little affect on the Fenced DES
 conclusions.  They may affect how one sees the design of block
 ciphers, however.

>Are you saying that ALL invertable permutations are bit mixers ?


>That there exists some invertable permutation which is a bit mixer ?


>That most invertable permutations are bit mixers ?


 I think I need to work on the definition to make it clearer what
 bit-mixing does.  But, over all possible input values, the simple
 change of one input bit position will produce avalanche output.
 Moreover, over all possible input values, for any possible
 invertible substitution, each input bit position is balanced,
 producing the same number of changes in each result bit.

 It is reasonable to compare this property to exclusive-OR, or half
 of a Block Mixing Transform.  Maybe there is a generalization of
 the mixing property.

>:  My principle assumption is that an invertible substitution is the
>:  ideal block cipher, and this is consistent with the usual analysis.
>:  If an ideal block cipher is an invertible substitution, it must
>:  behave like an invertible substitution, and have the same bit-change
>:  distribution.  And, to the extent that the real block cipher
>:  approaches the ideal, it must behave in the same way.
>Perhaps most of the invertable substitutions on n-bit codewords for a
>given blocksize n (say, greater than 64) are good block ciphers in the
>sense that they are secure, but most are terrible because you can't
>write the program that computes them in any reasonable amount of

 Which is exactly the point.  I claim that Fenced DES is a design
 for producing efficient mechanisms (e.g., writing programs) which
 model a very large, invertible, key-selected substitution.  I claim
 that such a substitution is the ideal model of any possible block
 cipher.  I also claim that a mechanism based on the Fenced DES
 design can compute enough substitutions to have a large-enough
 keyspace to be cryptographically effective.

 Terry Ritter