+     net!!not-for-mail
From: (Terry Ritter)
Newsgroups: sci.crypt

Subject: Re: Variable-size block ciphers
Date: 27 Aug 1995 15:11:59 -0500
Organization: UTexas Mail-to-News Gateway
Lines: 296
Message-ID: <>

 In  John Kelsey 

>- From what I've seen of this construction, it seems odd to me that
>you don't need more rounds to handle larger blocks.  (Intuitively,
>getting full diffusion through a 256-bit block should take more
>work than getting full difusion through a 64-bit block.)

 Apparently there is "diffusion," and then there is "diffusion."

 It is certainly clear that a substitution table will conduct any
 input bit-change to an output bit change.  It is also clear that
 an exclusive-OR chain *must* conduct any of those bit changes to
 all subsequent elements.  Given shuffled substitution tables at
 the next level, it is clear that this will produce a randomized
 result (in the subsequent elements).

 My point is that experiments show that multiple layers of this
 structure test very much like a "true" overall diffusion.  To avoid
 particular attacks, it may be that at least two layers must go in
 each direction, leading to five confusion layers.  But, once we
 have full nonlinear diffusion, one more confusion layer should
 provide "strength."

>Unfortunately, I don't have access to a web browser that will let
>me view images, so I'm stuck with ASCII diagrams--so I may be
>missing something.

 Ah, now I see the problem.  I assumed that I was the last person
 in the known universe to have webbing capabilities.

 Although I have used ASCII diagrams in the past, I was never
 satisfied with the diagrams I made for these VSBC things.  The
 .GIF's turned out *so* much better that I didn't bother putting
 ASCII diagrams in the HTML document on the web page.  I didn't
 (and don't) really intend to post the design document to the

 I believe that it is academically important to have webbing
 available, at least occasionally.  To do this, one first needs an
 Internet Service Provider which handles SLIP or PPP (preferred)
 logons.  Next, one needs a 386/486/P5 PC, typically one running
 Microsoft Windows.  Then, one needs protocol "middleware" like
 Trumpet Winsock (shareware), which the ISP may provide.  Last, one
 needs a browser, typically Netscape, which is free for individuals.
 That's pretty much it, and if you know somebody with a similar
 set-up, you can probably get up in an hour or so.  It *is* worth
 the effort.

>>    1. There will be some applications in which data-expansion can
>>       be eliminated.
>This is do-able with any fixed-length block cipher, if you're
>willing to do some extra work in encryption and decryption.  If you
>eliminated data expansion by changing the block size of the last
>block, it seems like you'd be saving yourself little work.

 Define "do-able":  Typically this is done by switching to stream-
 cipher mode for the last block.  But if this were really acceptable,
 it would be used for the whole message:  Normal stream-cipher mode
 has no data diffusion at all, compared to the full diffusion we
 expect and demand in a block cipher.

 So, we save having two modes, potentially additional hardware for
 one, and the complexity of switching between them.  There is some
 advantage; just how much depends on the individual case.

 These advantages are cumulative: a new cipher need not be the
 best in every possible category.  Nor do the VSBC designs need to
 better every known cipher in every way.  In certain important
 applications, for example database ciphering, they could be a
 significant improvement over anything now available.  In other
 applications, they could be at least competitive.

>>    2. There will be other applications which can avoid buffering
>>       by directly ciphering application-dependent field sizes.
>>    3. There may be a few applications (perhaps database ciphering,
>>       or voice CODEC's) which actually can use a cipher of
>>       dynamically-variable size.
>>    4. A single design can handle all of the above, as well as
>>       64-bit blocks, 256-Byte blocks and 1 KB blocks.  Thus, a
>>       single cipher can handle database ciphering, disk sector
>>       ciphering, and communications.
>>    5. Tiny versions of the same cipher can be exhaustively studied,
>>       and this can be done by parameterizing production-capable
>>       code.  (Validating results between this and the actual
>>       production code then validates the high-efficiency
>>       realization.)
>All four of these depend on the idea that it's possible to come up
>with equally-secure versions of your block cipher for any given

 These are advantages relating to variable size, which is in fact
 the issue I have addressed in these designs.

>I really would like to see some explanation of why you are
>convinced that this is the case.

 "Convinced" is not a word I would use.  I guess that I currently
 accept (as a reasonable basis for action) that a full, nonlinear
 balanced, bit-level diffusion implies overall "strength" in just
 one more confusion layer.  I can measure diffusion experimentally.
 I don't know how to measure "strength," and neither does anybody
 else who is talking.  It is consequently difficult to build a
 cipher with measurable "strength."

>It's easy to create variants of
>Blowfish, SAFER, and many other ciphers with different block sizes,
>but it looks like changing the block size changes the security
>properties of these ciphers, perhaps requiring more rounds to be

 In which case, "creating variants" does not seem all that "easy."

 Indeed, most Feistel-style block ciphers will have power-of-2
 block sizes.  One *can* use smaller mixings, of course, but that
 seems contrary to the usual practice of a broad half-block mixing.

 It is *NOT* easy to diddle with existing block ciphers to provide
 a god block cipher for data of different sizes.  One can, of
 course, always use a stream cipher, but then one gets into the
 "re-origination" issue (which I addressed in my Penknife commercial
 stream cipher for e-mail).

 "Re-origination" refers to the a cipher starting in the same state
 multiple times.  This sort of thing is necessary when we want to
 provide for messages being ciphered in some unknown sequence (like
 network packets).  With a stream cipher working on bytes, this
 immediately leads to an attack in which The Opponent can collect
 many messages which start out in the same way.  We can think to
 include other data (essentially keying data) with each "message,"
 but this may not always be possible.  On the other hand, if we
 have the ability to cipher blocks of variable size, most of
 which are very large (20..1500 Bytes), a similar attack is
 difficult or impossible.

>> There are other advantages to VSBC technology:
>>    1. These ciphers can closely approach the ideal of "overall
>>       diffusion," in which a change to *any* input *bit* changes
>>       *every* output *bit* with probability 0.5.  This is what
>>       we should expect and demand from a quality block cipher.
>Here, you're just saying that you have full diffusion, right?

 The word "just" in this sentence implies a fact not in evidence.

 It is not trivial or easy to get full diffusion.  Admittedly,
 diffusion appears as a side-effect in Feistel-type iterated block
 ciphers, so one might conclude that it just "happens" as a side-
 effect of a strong cipher.  But diffusion is *necessary*, and it is
 difficult to discuss diffusion in the context of Feistel ciphers
 *because* in these ciphers diffusion is only a side effect.

>is a necessary but not sufficient condition for block cipher
>security, since without full diffusion, it's possible to perform
>various divide-and-conquer attacks on the block cipher.

 Right.  My point exactly.

 But I would further say that, once one has a non-linear, balanced,
 full diffusion, then one more confusion layer (e.g., a layer of
 keyed fencing substitutions) should be sufficient for strength.
 At least that seems to me to be a reasonable position given the
 current evidence.

>>    4. Additional independent strength is easily added with new
>>       layers, without disturbing the rest of the design.  In
>>       contrast, simply increasing the number of rounds which do
>>       the same old algorithmic thing may not improve strength at
>>       all.  (Is a 32-round DES stronger than 16-round DES?)
>Can you explain this a bit more clearly?  I'm not too sure I
>understand how you can be more certain that adding layers in your
>design adds strength, than you can be that adding rounds to DES
>adds strength.

 Triple-DES is not just DES with more rounds, it is DES with more
 rounds and also more *keys*.  Simply adding rounds to DES is not
 the way to improve strength.

 On the other hand, if we add new diffusion and confusion layers to
 an existing VSBC design, we typically add a new layer of keyed
 substitution operations.  This is additional state which The
 Opponent must confront.

 It would be difficult to deny that, if four layers have strength
 x, then five layers must have strength x+delta or x*delta or
 x**delta or some such.  The real issue is whether the delta is
 low or the advantage weak, for then we may need to add too many
 layers to be practical.  I can only say that my bit-diffusion
 experiments indicate good diffusion (in *some* designs; a
 surprising number did not) with as few as three one-way diffusion
 layers.  I take full diffusion as a precursor to strength.

>>    5. VSBC technology produces a clear, regular, understandable
>>       structure in which the role of each element can be addressed
>>       mathematically.  In contrast, irregular and ad hoc designs
>>       depend on the mysterious strength of complex manipulations.
>>       While such manipulations may be "mathematical," they often
>>       do not carry any useful analytical properties.  Absent a
>>       comprehensive theory of design, such ciphers can only be
>>       analyzed individually, which is one of the major problems
>>       that cryptography has today.
>I would say that a number of block cipher designs fit this
>description, such as balanced Feistel networks with subkeys applied
>outside the f() functions, block cipher designs based on cellular
>automata, etc.

 Fine.  Let's just test this, shall we?  Given the well-known
 definition for DES, please provide a formula to describe the number
 of rounds needed for "full diffusion."  Also provide formulas or
 other reasoning showing that the resulting diffusion is "balanced"
 in each bit.  Now extend these formulas for arbitrary functions f().

 Given *any* keyed (randomized) substitutions, I suggest that we
 can make a good argument that at least three one-way diffusion
 layers (in two directions) and four confusion layers will produce
 something approaching experimental "full diffusion."  (I have so
 far approached the issue experimentally.)

 Another such set of layers would then protect against "fix
 in-the-middle" attacks, but these are already impractical in the
 context of a huge block size and huge keyspace.  Indeed, the
 ability to have and easily use a large keyspace is another
 advantage of the VSBC design over Feistel designs.  (My
 experimental versions all use a 992-bit keyspace and a huge
 Jitterized RNG like that in my Cloak2 commercial design to
 shuffle the tables.)

 One of the main problems with analyzing Feistel designs is that
 their structure supports arbitrary non-invertible f() functions.
 This is a problem because such functions do *not* guarantee that
 diffusion will *necessarily* be propagated in each mixing.
 This makes it difficult to make strong statements about diffusion
 without restricting f() to functions of some particular form.
 Presumably there are multiple such forms which support such
 reasoning, but we have not been given the Feistel design handbook.

 With respect to Cellular Automata, it seems to me that the bloom
 has faded from the CA rose.  CA designs were often touted as great
 stream-cipher RNG's which could never be analyzed, but they turned
 out to be just as analyzable as most other state-machine RNG's.

>> SAFER K-64 does not use "fencing" layers (arrays of keyed
>> substitutions), and does use iterative "rounds" which my ciphers
>> do not.  Still, if somebody has a problem with weak mixing (as a
>> lot of people did on sci.crypt last year), I encourage them to
>> take it up with Massey.  :-)
>Actually, you could go back to the earliest work on SP networks--
>fixed bit permutations are weak mixing layers, but nobody seems to
>doubt that they're useful in designing strong ciphers.

 Well, I doubt that anybody really denies that permutations can
 be useful.  In this particular case, I was looking for mixing
 transformations which would guarantee to propagate diffusion
 (element diffusion) across a large block.  Then these element
 values were *confused*, either by DES or by keyed substitutions.

 The fast, scalable, invertible, balanced transformations which I
 found were linear (although I subsequently have used an order-256
 randomized Latin square which is of course exceedingly nonlinear
 but also non-scalable).  The argument was made that the mixing
 transformations *obviously* did not contribute to strength
 *because* they were linear.  This argument was specious, because
 the transformations were not *intended* to provide primary strength
 per se, but were intended mainly to provide *provably* balanced
 diffusion *as a precursor* to strength.  This result was then fed
 into keyed substitutions which I believe *do* provide strength
 *under those proven conditions*.

 This is a completely different design strategy, one which separates
 confusion and diffusion.  The advantage is that we *can* generate
 *provable* and understandable small confusions.  We can also
 generate *provable* and understandable diffusion of various kinds.
 Then we can combine these things.  The one-way chain-style
 diffusion used in the VSBC designs follows that same path.

 Terry Ritter