Newsgroups: sci.crypt
Path: cactus.org!cs.utexas.edu!uunet!mnemosyne.cs.du.edu!nyx10!colin
From: colin@nyx10.cs.du.edu (Colin Plumb)

Subject: Re: Block Mixing Transformations
Message-ID: <1994Mar16.010710.4943@mnemosyne.cs.du.edu>
X-Disclaimer: Nyx is a public access Unix system run by the University
+             of Denver for the Denver community.  The University has neither
+             control over nor responsibility for the opinions of users.
Keywords: DES replacement, Large blocks
Sender: usenet@mnemosyne.cs.du.edu (netnews admin account)
Organization: Nyx, Public Access Unix at U. of Denver Math/CS dept.
References: <1994Mar13.051515.27175@cactus.org> <1994Mar15.124011.
+           19463@mnemosyne.cs.du.edu> <1994Mar15.194249.28915@cactus.org>
Date: Wed, 16 Mar 94 01:07:10 GMT
Lines: 140

In article <1994Mar15.194249.28915@cactus.org>,
Terry Ritter  wrote:
>
> In <1994Mar15.124011.19463@mnemosyne.cs.du.edu> colin@nyx10.cs.du.edu
> (Colin Plumb) writes:
>
>
>>T is A^B, which is the same as X^Y.  The high bit is
>>highly visible.
>
> Yup.  I had not seen it.

Okay, time to comme clean: I get a bit annoyed when I see a fancily-formatted
"report" that might fool some people when such glaring points as this are
wide open.  It seems enormously pretensious and makes me think poorly
about the author.  Sorry if it's unkind, but it's true that a part of
my mind is saying "I wish Terry would quit posting his `clever' ideas
until he learns thing one about cryptanalysis."

>>My observation about the extremely high degree of linearity in the
>>operation was that anything made up only of these mixing operations
>>is weak.  I'm not sure the above is more trustworthy than the
>>substitutions.
>
> Fine by me.  96 8-bit substitutions means 256!^96 keys.

Yes, it's called polyalphabetic substitution and ciphertext-only attacks
are trivial.  (Remember that the 26! = 403291461126605635594000000
possible keys to a basic momoalphabetic substitution is more than 88
bits; larger than the Skipjack key size.  And yet newspapers routinely
print short stretches of ciphertext for people to solve for amusement.)

Now, the mixing probably makes it harder, but I'm not convinced it's
that much harder.

> (Obviously we initialize this state by shuffling with a
> cryptographic RNG, but we can make that RNG just as large as we
> want and seed it with all the key material we want.)
>
> Just the 32 substitutions in the middle would be more than secure,
> *provided* all the stuff around them spread their effects and
> prevented them from being attacked separately.
>
> All we need the mixings to do is to mix.  Essentially, we want to
> end up with the effect of a bit change in any particular position
> being spread among the entire output (statistically), after a set
> of mixings.  If this can be accomplished, we can use small,
> practical substitutions to make a large-block cipher.

There are two desirable properties in a mixing: non-linearity (see all
the papers on bent functions, which are functions a maximum Hamming
distance from any affine function) and the Strict Avalanche Criterion.
Which means that, over all possible values of the other n-1 bits, changing
one inut bit has a 50% probability of changing each output bit.
(Higher-order SAC constraints require this to hold for subsets of the
set of excluded input bits. E.g. 2nd order requires that if any one
of the n-1 other inputs is fixed, the probability is still 50% over
all combinations of the remaining n-2 bits.)

Now, let's see what your proposed mixing function does.  Changing bit k
of A will change bit k of Y and bit k+1 of both X and Y.  Unless k=n-1,
in which case it will change the bits corresponding to the bits set in
the polynomial p.  But in most cases, toggling one input bit toggles three
output bits.  In all cases, there is no dependency on any other input
bits; the function is completely linear.

You might want to look at the following papers from Eurocrypt '93.
The proceedings have now been published by Springer-Verlag, in their
Lecture Notes on Computer Science series.  Tor Helleseth (Ed.).  The
full title is "Advanced in Cryptology - Eurocrypt '93" and the ISBN number
is 3-540-57600-2 and 0-387-57600-2.

Anyway, the papers:
Differentially uniform mappings for cryptography, K. Nyberg
On almost perfect nonlinear permutations, T. Beth, C. Ding
Two new classes of bent functions, C. Carlet
Boolean functions satisfying a higher order strict avalanche criterion
	T.W. Cusick
On constructions and nonlinearity of correlation immune functions
	J. Seberry, X.-M. Zhang, Y. Zheng

These talk about useful properties for mixing functions.

Another thing about your proposed mixing function is that the bits that
get modified are close to each other.  Modifying a bit and the bit
next to it produces the following pattern of differentials:

        1
       11
      101
     1111
    10001
   110011
  1010101
 11111111
100000001

This is immediately recognizable as Pascal's triangle, but serves to
illustrate the fact that a 1-bit change in the input is slow to propagate.
Because you only hav three levels of S-boxes, I suspect the whole thing
can be reduced to a system of simultaneous equations of reasonable size
and solved with a bunch of known plaintext that is basically the size
of the unicity distance.

Cryptanalysis is difficult.  I am not any good at it, to speak of.
(My general rule is that anything I can find a chink in, someone good
can probably find a hole in you could drive a Mack truck through.)
If you look at papers proposing ciphers, you'll see that the onus is
on the proposer to show that a number of known methods of cryptanalysis
are ineffective.  "Show" does not mean "I couldn't do it", but "Here
is a proof that nobody can do it."  The requirement for proof can be
weakened to an argument, but Xuejia Lai's PhD Thesis gives a good
example to try to emulate.  More work on the subject can be seen in the
Eurocrypt '93 paper

Markov ciphers and alternating groups, G. Hornauer, W. Stephan, R. Wernsdorf.

Cryptography is harder than cryptanalysis.  Cryptanalysis (of modern ciphers)
is extremely difficult.  I'm not qualified to do either, although I'm
slowly working my way through the cryptanalytic literature in an attempt
to develop a modicum of skill.

One cipher that might be worth exploring is one based on an FFT-like mixing
pattern (all butterflies the same size), with S-boxes after each round of the
FFT.  But if you were to stick to 8-bit mixing, you could merge the mixing
function with the previous S-box by having each of the two input S-boxes
to the mixer emit 16 bits, which are XORed and the two halves used as outputs.
And that would permit much more complex mixing functions with no increase
in cost.

Even then, I'm not sure if one pass through the FFT network would be enough.
Each input byte has only one chance to affect each output byte; that
could make solutions comparatively simple.  I'd prefer at least two
rounds.

But remember, these are all off-the-cuff ideas; if I were to start work
now and not find any holes after 6 months of effort, it might be worth
considering using them to protect data.
-- 
	-Colin