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