Newsgroups: sci.crypt
Path: cactus.org!ritter
From: ritter@cactus.org (Terry Ritter)

Subject: Re: Block Mixing Transformations
Message-ID: <1994Mar17.045627.13639@cactus.org>
Keywords: DES replacement, Large blocks
Organization: Capital Area Central Texas UNIX Society, Austin, Tx
References: <1994Mar13.051515.27175@cactus.org> <1994Mar16.205036.
+           1806@mnemosyne.cs.du.edu>
Date: Thu, 17 Mar 1994 04:56:27 GMT


 In <1994Mar16.205036.1806@mnemosyne.cs.du.edu> colin@nyx10.cs.du.edu
 (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."

>I didn't mean to be insulting.  I was feeling a little bit frustrated and
>trying to express it without being vicious.  I read my words again and
>I still think I hedged them enough that it's not a personal attack.
>Am I wrong?

 In my opinion, it was an attack, yes.  It was also substantially
 misleading with respect to the quality of the article.

 It is appropriate to criticize the material.  It is not appropriate
 to imply expertise so that your opinions alone will discredit a
 substantially-valid argument which you do not understand.

 If you really don't want to see my ideas, just hit "n" or put my
 name in your kill file.  That's what it's for.  That's freedom on
 the net.


>I was just pointing out that key size is NOT a good measure of cipher
>strength.  128 bits is enough for a good many years.

 I agree, and have said so many times in my many Large-Block DES
 papers.  I am looking for an effective keysize of twice DES,
 perhaps at single-DES rates, suitable for a couple of decades.


>Key size in excess of this is a waste of storage space.

 Well, yes and no.  At this level (say, 8x the key space) store
 is not really an issue per se.  But if necessary, the key material
 could be expanded with a cryptographic hash of some sort anyway.


>Ciphers with much larger key sizes can be easy to break.

 Yup.


>my basic idea was that an 8-bit S-box can be represented
>as a system of boolean equations of degree 8.  The mixing network
>is linear.  So three stages of S boxes makes for a degree-24 system
>of equations.  Big and awkward, to be sure, and I wish I knew more
>about how much work that is to solve, but it doesn't seem ridiculous.

 I'm not sure.  Maybe it will turn out that no mixer can possibly
 be a good mixer unless it is nonlinear.  I think we are some ways
 away from that as a conclusion, however.


>in any case,
>it's the number of *levels* of mixing that is relevant to thoroughness.)

 Sure, but all the substitutions have to be represented.  I had
 thought of saying 9 levels, but then thought that might have
 implied 9 large mixings, which still might be OK, but that was
 not what I meant.


>>>Cryptography is harder than cryptanalysis.
>>
>> Not in my experience.
>
>A good code is one that is resistant to cryptanalysis.  If we define
>cryptography to be the design of good codes (I agree that any boy scout
>can construct a bad one), then it is defined in terms of cryptanalysis.
>You can't do it without understanding cryptanalysis.

 It is the cryptanalysis which makes the cryptography relatively
 simple.  I see no disagreement here, but I think the phrasing is
 strange.

 Cryptography depends upon cryptanalysis.  It is sad, however,
 that we have no real *science* of cryptanalysis, apart from
 various particular attacks.  And always an individual must
 interpret and manipulate the attacks and so could miss something.
 (The attacks are approaches, not algorithms.)  The fact is that
 we have no scientific way of assuring customers or anyone else
 that a particular scheme is absolutely secure.  This is a very
 weak position.

 On the other hand, with some effort we can come to some opinion
 about the apparent complexity of the scheme.  Then we can look
 to the application and see whether the customer really has
 physical security to match.  Attacking ciphertext is likely to
 be the absolute last way to acquire secret information.


>When I say I'm not qualified to do cryptanalysis, I mean that if you
>want a cipher attacked, I'm not a good person to ask; I can only
>break the most trivial of ciphers.  However, if I can break it,
>you can be assured it's a bad cipher.

 Providing you "break" what the real cipher is.  Your "assurance"
 implies an understanding which may not exist.


>> 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.
>
>And I observed that your proposed structures are not worth much.
>Those are the "clever" ideas I take objection to.  Your block
>mixer achieves its stated goals and I think is a useful contribution.
>However, your attempts to use it in a block cipher suggested to me
>that you didn't understand its limitations.

 I accept the suggestion that I don't understand the limitations
 of the mixing was.  But I don't think *you* understand those
 limitations--or whether they are necessarily relevant--either.
 Worse, I don't think there is any handbook--or any particular
 paper--which directly addresses the issue.

 That is the main problem with our present system of paper after
 paper after paper.  We get the trees, not the forest.  (Eventually
 the forest gets turned into paper, however. :-)


>> 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.
>
>You're right; my criticisms were directed towards your block cipher
>suggestions and not your mixer per se.  My criticisms of the mixer
>were based on "if you want to use it in that structure, you need
>a stronger mixer."  I sort of got the issue turned on its head.

 If you would simply say that, you would give no offense.

 However, I don't think you have the evidence to support that
 statement.


>So many things here offer no opportunity for learning, because the
>success or failure of a proposed cipher is never evaluated.  I don't
>think "hey, this is rubbish, and here's why" is a bad thing.  I
>did think most of my observations were obvious enough that you could
>have spotted them yourself before announcing the ideas to the world.

 Maybe not.  I'm a different person.  I come at things a different
 way than you do.  I can miss things that you see.  That is OK.
 I would not be surprised to find things that you have missed.
 (Of course, that would make you an inferior, so you would lose face
 and then I would have no choice but to demean you in public. :-)

 On the other hand, since your observations were only tangential
 to the point of the article, I do think your response was, shall
 we say, a tad overblown.


>Pardon me if I misunderstood, but I thought that is a mixing operation
>did not enhance the strength of a cipher, it should be omitted.  (Like
>DES's initial and final permitations.)

 The critical phrase is "enhance the strength."  Strength must be
 seen in the context of the whole mechanism.

 If we already knew--really *knew*--that the approach was silly,
 I would have no problem going on to something else.  I do expect
 a little more than "everybody with any intelligence knows that
 can't work, you moron."

 As Howard Armstrong supposedly said: "It ain't ignorance that causes
 all the trouble in this world, it's the things that people know that
 ain't so."  I don't think we *know* that simple mixers necessarily
 *imply* a weak cipher, especially since we can afford to use them so
 much more freely.


>Separating nonlinearity, maybe.  Separating (non-linear) substitution
>and (linear) permutation is very common.  Your mixing is a variant
>on the permutation theme.  But that need only be for analysis purposes.
>In a software implementation, they can be combined for efficiency.
>I was pointing out that given a certain implementation choice, there
>are a large number of equally efficient permutation functions.

 If you were, indeed, just pointing out that the functions I found
 were part of a large known set of others, or that there were ones
 which would meet the stated goals of the article better, I would
 have had no problem with that.

 I do have a problem with you forming your own goals and then
 carrying your name and reputation into a criticism of the article
 because those goals were not met.


>Maybe his opinion has changed now, but last year Eli Biham was nervous
>about IDEA because it only had 8 rounds; he would prefer 12 or 16.

 *I'm* nervous about IDEA (PES, IPES, ...) because the internal
 mixings are *so* close to linear functions, and the *entire*
 strength of the system depends upon them.  No S-boxes at all.
 It seems to me that we could effectively write the bit-level
 equations for each operation, and then proceed to solve the
 equations, given enough data.  By not working at the value level,
 we do not need to be mislead by claims of linearity at that level.
 And, even if the full system is not solvable, it may be that the
 number of undefined states can be greatly reduced.

 I have previously reported working on the PKZIP cipher, and solving
 the complete linear system in this way (although not the nonlinear
 output).  (If those reading think this is easy, I would agree:  Let
 me know how long it takes you.)

 But I am not actively working on attacking IPES.


>I have yet to see a convincing
>argument, except for efficiency, for using larger block sizes.

 Sure you have.  You don't use 8-bit substitution (alone) as
 a cipher.  You have thus accepted the argument that a small
 block size is too weak.  Why?  (After all, you could use it
 with CBC.)

 Nope, even with CBC an 8-bit substitution is too small, so you
 accept a 64-bit substitution, a larger block size.

 But the data going into such a system often has a very small
 information content.  If PKZIP can reduce text by 60%, we are
 looking at 26 bits of information being ciphered, at most, on
 average.  It is not clear how one could use this understanding,
 but that need not be clear in order to take steps to prevent
 an attack which uses it.

 I would like to see the normal block cipher be 256 bits wide
 at least.


>And
>I haven't seen a cipher that didn't sacrifice either efficiency or
>security when going to a larger block size.)

 Well, that's part of the issue, isn't it?

 I interpret the paucity of example systems as meaning that the
 issue has yet to be decided, and not that there is no possible
 solution.


 ---
 Terry Ritter   ritter@io.com
                ritter@rts.com