Path: illuminati.io.com!uunet!europa.eng.gtefsd.com!news.umbc.edu!olson
From: olson@umbc.edu (Bryan G. Olson; CMSC (G))
Newsgroups: sci.crypt
Subject: Re: Toward Axiomatic Fenced DES (long!)
Date: 2 Jun 1994 03:27:44 GMT
Organization: University of Maryland, Baltimore County
Lines: 148
Message-ID: <2sjjjg$he0@news.umbc.edu>
References: <199405261829.NAA24225@indial1.io.com>
NNTP-Posting-Host: umbc7.umbc.edu
X-Newsreader: TIN [version 1.2 PL2]
Terry Ritter (ritter@indial1.io.com) wrote:
[...]
: The system of definitions, proofs and arguments which takes up the
: major part of this article is by no means finished, and is known
: to be casual and inconsistent in places. (Some of these problems
: could be fixed by expanding the mathematical base, which I avoid
: for now.)
The problems are pretty big. If you make the early theorems
precise and correct, they will no longer support the results
you need.
[...]
: The Proofs
Please don't call them theorems and proofs if they are not.
[...]
: 2.9 THEOREM: (Average distance and distribution.) The expected
: number of elements which differ between two n-position code values
: is n * (1 - 1/|S|), and the distribution is binomial.
You need to state the distribution of code value pairs in order for
the expected value you talk about to be defined. Also, the proof
needs work. First justify the binomial distribution, then show
this implies your result.
[...]
: 3.2 DEFINITION: A RANDOM discrete function allows each output
: code value to be selected independently for each possible input
: condition.
Bad definition. A function fixes the output value for each input
value, so there is nothing to allow. A random function is one chosen
at random from some distribution of possible functions. When no
distribution is given, we generally assume the uniform distribution.
[...]
: 3.3 THEOREM: (Number of random functions.) There are 2**2n
: possible random functions with an n-bit binary input code and an
: n-bit binary output code.
: (Proof: An n-bit binary code can make 2**n possible
: selections, each of which can be 2**n possible values,
: and (2**n)*(2**n) = 2**2n.)
Given a function there is no way to tell if it is random (under your
definition or mine). A uniformly distributed random function from
n-bit strings to n-bit strings is equally likely to take any of
(2**n)**(2**n) different values.
[...]
: 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. For example:
THEOREM: Given n-bit strings a and b with a <> b, if P(x) is chosen
(independently of (x,y) ) from a uniform distribution of all
permutations of the set of n-bit strings, then the expected Hamming
weight of P(a) xor P(b) is:
2**(n-1) / (2**n -1)
(The Hamming weight of the xor is the number of different bits.)
[...]
: 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. 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.
[...]
: 4.9 THEOREM: (Avalanche is automatic.) Avalanche is an inherent
: property of complete invertible substitution.
: (Proof: See 4.5, 4.7, and 2.9.)
Unfortunately 4.7 is incorrect, and the definition of avalanche is
nonsense.
4.10 and 4.11 again need to be defined for a probability distribution.
[...]
: 4.12 THEOREM: (Not a random function.) An invertible substitution
: cannot be a random function.
: (Proof: Suppose a value is selected for placement somewhere
: in a substitution. Since an invertible substitution cannot
: allow another occurrence of that same value, other values
: cannot be selected independently.)
Nope. As much as it's defined it's incorrect.
If a function f(x) is chosen from a uniform distribution of all
functions from n-bit strings to n-bit strings, the probability that
f(x) is an invertible substitution (permutation) is:
(2**n)! / (2**n)**(2**n).
If a permutation P(x) is chosen from a uniform distribution of all
permutations of the set of n-bit strings, the chance P(x) is a
function is:
1.
[...]
: 4.14 THEOREM: (Reconstruction requires information linking output
: values to input values.) An unknown invertible substitution cannot
: be resolved without simultaneous information about both the input
: value or position and the output value.
: (Proof: To the extent that a particular substitution can
: be said to have an identity, that identity is the relation
: between substitute values and their position. This relation
: is both necessary and sufficient to define the substitution.)
Say what?
[...]
: 5.2 THEOREM: An invertible substitution is a bit-mixer.
May or may not be.
You need to be much more careful in your definitions and proofs. I'm
afraid if you clean up the early stuff, it won't be strong enough to
prove the later stuff. You can show bit-change probabilities for
random permutations, but then you can't apply them your block
operations without making unproven assumptions.
--Bryan