VSBC Newsgroup Discussion

Variable Size Block Ciphers discussed in sci.crypt.

The goal is a block-cipher architecture which can have an essentially arbitrary and dynamically-variable block size. It is necessary that good diffusion be produced from all plaintext input bits to all ciphertext output bits. It is desirable that a fixed number of processing layers evenly diffuse blocks of any size, or else there would be a strong motive to use small blocks.

Contents

• The Original Announcement
• Announcing Realized Prototypes

The Original Announcement

• 1995-08-20 Terry Ritter: The original announcement.
• 1995-08-21 Ross Anderson: "Two such ciphers appeared in 1993 - WAKE by David Wheeler and a proposal from Burt Kaliski and Matt Robshaw. They are both in `Fast Software Encryption', Springer LNCS 809"
• 1995-08-23 Terry Ritter responds to Ross: "While Kaliski-Robshaw does handle large 1 KB blocks [...] this is a particular design for a particular (fixed) size block. WAKE is an autokey stream cipher. In a stream cipher, diffusion can occur only to that part of the stream following a particular datum."
• 1995-08-24 Ralf Brown: "And I proposed another approach to variable-size blocks, namely using a Feistel network and "sliding" it along the input, back in April."
• 1995-04-02 Ralf Brown. Ralf's previous message. (Note the absolute lack of any concept of dynamically variable size, such as size parameterization or the like.)
• 1995-08-25 Terry Ritter responds to Ralf: The mentioned ciphers differ from "Variable Size Block Ciphers" as defined.
• 1995-08-25 David Wagner: "No go: this is easily cryptanalyzed by differential cryptanalysis." (This posted response mistook the design as using but a single table in each row, but later private e-mail did show how the real design could be attacked.)
• 1995-08-25 John Kelsey: "...it seems odd to me that you don't need more rounds to handle larger blocks." Also detailed questions and comments.
• 1995-08-26 Paul Rubin: "Isn't RC5 a variable width block cipher, sort of?"
• 1995-08-26 Terry Ritter responds to David: "each substitution is intended to be a separate keyed (shuffled) table. [...] Currently, I am less interested in strength than overall diffusion. My point is that it seems amazing -- wondrous -- that an overall bit-level diffusion effect can be generated for an essentially arbitrary block width by a fixed-depth structure."
• 1995-08-27 Ralf Brown responds to Terry: "I wasn't thinking of the above, but an extension thereof which I posted to sci.crypt.research at the end of April [...]"
• 1995-05-01 Ralf Brown: Ralf's other previous message. (This message does say "effectively unlimited block size", but there is absolutely no discussion of a dynamically variable block size. This design also does not diffuse evenly over the whole block -- the first and last elements get less diffusion -- and needs more layers to process larger blocks.)
• 1995-08-27 Ralf Brown responds to Paul: "Parameterized. You can set various sizes beforehand, to get a different variation of the cipher."
• 1995-08-27 Terry Ritter responds to John's detailed questions and comments.

The technical criticism to these brand-new structures comes from David Wagner, and his "No go" response certainly sounds ominous. It took me a long time to understand this criticism and place it in context, even with several other messages from David by private e-mail.

As I understand it, David comments that if we change adjacent input bytes, we can match values in the top-level substitutions, and when this is repeated, it essentially solves that confusion layer. Although I was aware of the first part of this, I did not see how it would lead to success. Thanks David!

Thus, what I had seen as a worst-case block cipher test (the single-bit-change avalanche results) ignores the important possibility of correlations in multi-bit changes. (I expect that we could pick this up by trying all 64K values of two adjacent bytes over multiple keyings.)

But David himself comments that we can correct the problem in the cipher simply by adding another right-going diffusion layer to the original structure. So the "No go" response is not a blanket indictment of the technology, but is instead a good insight about ways in which these structures can be weak. We have every motive to reduce the number of layers, but we can easily go too far. Don't do that.

Announcing Realized Prototypes

• 1996-02-11 Terry Ritter: Five realized prototypes and comparative speed measures. (13K)

Last updated: 1996-02-15