Newsgroups: sci.crypt
From: (Terry Ritter)

Subject: Re: Block Mixing Transformations
Message-ID: <>
Keywords: DES replacement, Large blocks
Organization: Capital Area Central Texas UNIX Society, Austin, Tx
References: <> <1994Mar16.010710.
+ >
Date: Wed, 16 Mar 1994 09:30:35 GMT

 In <>
 (Colin Plumb) writes:

>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."

 Frankly, I think this says more about Colin Plumb than Terry Ritter.

 When Plumb publishes a practical cryptosystem which he can *prove*
 secure, then I'm sure the rest of us will take some notice.  Until
 then, we all must learn to deal with--and depend upon--not only
 proposals, but actual fielded systems of unknown strength.

 Frankly, I think the *practice* of Science--and especially
 cryptography--is benefitted more from the exposure of reasonable
 wrong approaches than right ones.  Nobody comes up with only great
 ideas; to publish only after a great one is finally found and
 confirmed is to hide what the work of Science actually is.  The
 work is the process, not the result.  There will always be another

 And, sci.crypt is not a refereed publication.  I do not expect
 to treat it like one.

>Yes, it's called polyalphabetic substitution and ciphertext-only attacks
>are trivial.

 Well, the term "polyalphabetic substitution" is normally applied
 to stream ciphers instead of block ciphers.  To apply it here,
 we must already have come to the conclusion that the mixing is
 so ineffective that individual characters are enciphered--through
 the entire cipher--by independent substitutions.  This seems
 unlikely, but in any case it has not been shown.  Thus, the
 term is inappropriate.

 Perhaps, after some study, Plumb would recognize that substitution
 is "weak" precisely to the extent that it can be separated and
 investigated.  Plumb might also want to look at the construction
 of DES for an example of the use of small, extremely-weak
 substitutions as major parts of a very respected cryptosystem.

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

 A critical comment made without benefit of analysis?  "It seems
 enormously pretensious and makes me think poorly about the author."

>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.

 1)  Keyed substitution is inherently non-linear.  (The probability
 of a linear randomized substitution is vanishingly small.)

 2)  It is easy to build weak ciphers which have good avalanche

 The whole point of my proposal is to separate the mixing from the
 strength.  A cipher with extremely fast, weak mixing may well be
 preferable to the slow form Plumb proposed, which turns out in fact
 to be 20-50 times slower. (!!!!)

 Think about it:  Using the fast mixing I proposed, one can afford
 to make a block cipher with perhaps 20 times as many stages--and 20
 times as many unique substitution tables--as one with Plumb's
 "improved" mixer.  I would say that there is at least a reasonable
 chance that the cipher with the fast mixer--having up to 20 times
 as many stages--would be a stronger cipher.  And if it could be
 better analyzed for strength, use fewer stages and operate faster
 as well, so much the better.

>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.

 One of the characteristics I mentioned for the fast mixing function
 was the fact that a single bit-change in *either* input block would
 produce at least (and probably) a bit change in *both* output
 blocks.  A modest propagation, true, but it rolls through 61 mixing
 operations per stage.  The reason for cascading the mixings is to
 spread the various changes throughout the field of substitution

 As soon as even one bit changes into a substitution, we get an
 inherent "avalanche" in the output from that substitution.  Thus,
 the role of the mixing is to get bit changes into (potentially)
 all the substitutions.

>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.

 Big talk.  Let's see it.

>Cryptography is harder than cryptanalysis.

 Not in my experience.

>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.

 Interesting, then, that Plumb feels so capable of judgement.

>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.

 If someone were to actually read my Block Mixing article, s/he
 would see that it was concerned with the existence of such
 structures, and with one fast structure in particular.

 That structure works.  It reversibly mixes without expansion.
 The article is not in error.  I did expect the mixing to be
 stronger than it turned out to be, but "strength" was specifically
 disclaimed as an issue.

 The article was not concerned with overall cryptosystems, other
 than to explain why one might want a Block Mixing structure in
 the first place, and to propose some cipher constructs which
 might be worth investigating.  It specifically stated:

    "These are new ciphering architectures.  Clearly, it is not
    known how strong these constructs would be."


    "Other opportunities exist when constructing completely new
    block ciphers.  These might, for example, be based on byte-wide
    key-permuted substitutions, thus avoiding differential attacks
    on fixed "optimal" tables."

 Since the article was specifically limited to detailed discussion
 of the *mixing*, it does seem a little odd that it would be
 criticized for not being a proven cipher.

>"Show" does not mean "I couldn't do it", but "Here
>is a proof that nobody can do it."

 Ah, then we must *have* practical cryptosystems which are proven
 secure.  Which ones would those be, exactly?

>The requirement for proof can be
>weakened to an argument, but Xuejia Lai's PhD Thesis gives a good
>example to try to emulate.

 While emulating someone else's thesis may be Plumb's highest goal,
 it certainly is not mine.

 Postings to sci.crypt are not, and should not be considered to be,
 scientific publications.  We need room to speculate, room to fail
 without career implications, and room to consider alternative
 approaches that your PhD advisor may not like.  One of these may
 lead to better solutions.  Or not.

 We have a lot of people laboring in secret because they are afraid
 to say anything and get the kind of response we see from Plumb.
 We are all poorer for it; those who read because we don't read the
 new ideas, and those who don't write, because it is through error
 that they learn more than they know.

>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.

 It would certainly be a different cipher.  But it would be moving in
 the opposite direction from my proposal, which specifically intends
 to separate the concepts of "strength" and "mixing" each into their
 own particular mechanism.

 One of the major problems with modern cipher design is the inability
 to *measure* "strength."  It is very easy to say "this mixer is
 nonlinear so it must be stronger."  It is easy to *say*, but not so
 easy to prove.  And very few academic papers even begin to approach
 the idea that "stronger" may not be worth the expense, if it takes
 20 times as long.

 I have proposed to finesse the issue of unknown mixing strength
 by placing the strength in particular simple components in a
 relatively simple structure.  If this approach is successful, we
 can avoid speculating about the "strength" of the mixing, since
 it is exactly this speculation which leads to the question of "How
 many rounds do we need."  Where is the formula which provides that

 If the approach is not successful, we know yet one more thing
 that does not work, and, hopefully, why.  And this knowledge must
 benefit the continued search.

>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.

 I certainly am not using any of the many schemes I suggested in
 the article to protect data.

 However, I have not seen a sufficient problem with it to prevent
 continued investigation in that direction.

 Until that succeeds, Plumb might consider using my Penknife email
 cipher for DOS.  Admittedly quite a stretch from the theories
 tossed around here, Penknife is an honest, fielded, commercial
 stream-cipher product which does not infringe anyone else's patent.
 It is based on my own patent for Dynamic Substitution, which was
 described in my (refereed) Cryptologia article of October 1990.
 Penknife also uses random-number techniques described in my
 Cryptologia article (59 pp., 213 refs) of April 1991.

 Terry Ritter  ( dies Friday)
        (perhaps temporarily)
        (perhaps temporarily)