Path: illuminati.io.com!uunet!ulowell!ulowell!europa.eng.gtefsd.com!news.umbc.ed
u!olson
From: olson@umbc.edu (Bryan G. Olson; CMSC (G))
Newsgroups: sci.crypt
Subject: Re: Toward Axiomatic Fenced DES (long!)
Date: 7 Jun 1994 19:14:20 GMT
Organization: University of Maryland, Baltimore County
Lines: 215
Message-ID: <2t2guc$l89@news.umbc.edu>
References: <199406060606.BAA10833@indial1.io.com>
NNTP-Posting-Host: umbc7.umbc.edu
X-Newsreader: TIN [version 1.2 PL2]
Terry Ritter (ritter@indial1.io.com) wrote:
: In <2stndb$9ae@news.umbc.edu> olson@umbc.edu (Bryan G. Olson; CMSC (G))
: writes:
: >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
: optimal.
Perhaps you misunderstood what I was asking. In most Usenet threads,
material is identifiable by the number of annotation marks. When you
re-included your writing (a perfectly reasonable thing to do) your
editor gave it a single '>', which is exactly how quotes from my post
were denoted.
: 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
: distribution.
: It may be that, at some point, it will be necessary to introduce
: random selection. I wish to postpone that as long as possible.
Fine. Phrase your assertions as the average of all elements in a
given set.
: >[...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.
: >: >: 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.
: >[Bryan:]
: >: >
: >: >This one is going to be hard to fix.
: >
: >[Terry:]
: >: It's a *definition*: there is nothing to fix.
: >
: >It's a bad definition. What discrete functions have this property ?
: All block ciphers.
More on that later.
: >[Bryan:]
: >: >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.
: >
: >[Terry:]
: >: 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?
I'm trying to clarify the issue. Note what I asked:
: >(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.
A derangement is how I would model a change. In your definition you
didn't say what your set of changes included.
: 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.
I was talking about what you wrote, not necessarily what you meant.
: 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
: >one.
: Actually, the 2**n - 1 possible *changes*. Which is why I use
: "about."
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.
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)
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.
[...]
: >Are you saying that ALL invertible permutations are bit mixers ?
: Yes.
So the identity function is a bit mixer.
[...]
: 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.
: >[...Terry:]
: >: 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 invertible 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
: >space.
: 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.
Unfortunately, your definitions and theorems don't establish this. 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. You present no reason to believe that either fenced DES
or your substitution boxes will have properties which are approximately
average for invertible substitutions.
--Bryan