Large Block DES

An on-line development project in cryptography.

The goal is a block cipher stronger than DES, and faster than Triple-DES. Ideally, it would also have a block size much larger than DES.

Contents

• Background
• NxM DES
• Ladder DES
• Large Block DES Newsletter
• Balanced Block Mixers
• Fenced DES
• Toward Axiomatic Fenced DES
• The Context of the Fenced DES Design
• Announcing Realized Prototypes
• Huge Block Size Discussion on sci.crypt

Background

The project began in the weakness of DES, and the horror of systems people contemplating the widespread use of Triple-DES. The goal was a block cipher stronger than DES and substantially faster than Triple-DES. A design was constructed and the NxM DES article prepared.

Alas, NxM DES was found to be weak after publication. This left the problem unsolved, and the failure (in itself, not all that unusual) embarrassingly exposed. Thus began the open development process.

A series of approaches and articles were prepared, culminating in the introduction of Balanced Block Mixers and the resulting Fenced DES cipher. While Fenced DES is a new approach, and so not easily accepted, it does appear to solve the problem.

NxM DES

The original article in the series, and the desirable Nx2 form is eventually shown weak.

• 1994-02-02 Terry Ritter: NxM DES
• 1994-02-02 Stewart Strait: "analogous in some sense to Playfair"
• 1994-02-03 John Taber responds to Stewart: "I'm not sure I understand all this. The DES itself is a simple substitution cipher on an "alphabet" consisting of 2^64 characters."
• 1994-02-07 Eli Biham responds to the original proposal through Bruce Schneier: "I claim that the cryptosystem described in your email is not stronger than a single DES, when it uses only two passes -- i.e., Mx2 DES.
• 1994-02-10 Terry Ritter: "before I open mouth wide and insert foot, I would like to be able to understand the attack that Biham describes."
• 1994-02-12 Terry Ritter: Nx2 DES Found Weak: the end of the line for Nx2 DES.

Isolated Double DES

• 1994-02-17 Terry Ritter: Isolated Double DES
• 1994-02-20 Dave Sparks
• 1994-02-21 John Payson

Ladder DES

A higher-level "Feistel Cipher" using DES as the nonlinear function.

(NCSA Mosaic has been known to destroy the ASCII flow-diagrams in this article, because they accidentally include the HTML "comment" sequence. Netscape has no such problem, but if your browser does, it may help to view the document "source." I want to avoid changing anything within the documents.)

• 1994-02-22 Terry Ritter: Ladder DES
• 1994-02-23 Mark R: "Another, already somewhat widely used alternative is RSA Data Security's "DESX" "
• 1994-02-23 David Barber: "why don't we want to use IDEA to replace DES?"
• 1994-02-23 Mark Henderson responds to David: "For one, there is the issue of the patent on IDEA."
• 1994-02-23 Owen Lewis responds to David: "1. The massive investment already made in DES technology and equipment makes people reluctant to change. 2. For the US market, the NIH (Not Invented Here) syndrome."
• 1994-02-25 Terry Ritter responds to David: "I have trouble believing that IDEA is strong."
• 1994-02-25 Terry Ritter responds to Mark: " Where was this design published openly for comment? What were the comments?"
• 1994-03-01 Andrew Haley comments: "These schemes have been the subject of much research in recent years. The classic paper is [1], in which it is shown that three rounds in the structure above are sufficient to prove perfectness (polynomial time indistinguishability from a truly random permutation), provided that the random functions are themselves perfect."
• 1994-03-01 Mark Riordan: DESX definition: "DESX is an encryption algorithm that extends the famous DES (Data Encryption Standard) algorithm to a keysize of 120 bits."
• 1994-03-01 Terry Ritter: DESX overview: "Presumably the salient issue is that the outside XOR's are intended to protect the internal DES from exhaustive search."

Q: Am I the only one to find something odd about theoretical results which "prove" strength provided that the base functions are strong? If we had anything reasonable with provable strength, we wouldn't be going through this!

Large Block DES Newsletter

A summary of the never-ending project.

• 1994-03-02 Terry Ritter: Large-Block DES Newsletter

Balanced Block Mixers (originally called Block Mixing Transformations)

Simple, weak, fast and expandable mechanisms for mixing two input blocks into two output blocks. While many cryptographic mechanisms have do not have actual property proofs, this mechanism does.

Among other things, a Balanced Block Mixer construct provably guarantees to propagate a value change in one input block to both output blocks. This property can be used to produce provable overall diffusion or avalanche in a block cipher. While overall diffusion does not necessarily imply strength, overall diffusion is required in a good block cipher.

• 1994-03-13 Terry Ritter: Announcement (26K)
• 1994-03-14 Colin Plumb: "Basically, this operation is far too linear."
• 1994-03-15 Terry Ritter responds to Colin: " My intent in defining such constructs was to try and separate the concepts of "strength" from the "mixing" property. This means that we do not have to define what "strength" means in such a construct, but can instead rely on more classical forms, such as DES or substitution."
• 1994-03-15 Colin Plumb responds to Terry: "I see your idea now. Changing the widths like that will require a bit more thinking. The preservation of Z^B still applies, but the substitutions make it rather more complex."
• 1994-03-15 Terry Ritter responds to Colin: " 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."
• 1994-03-16 Colin Plumb responds to Terry: "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." "
• 1994-03-16 Terry Ritter responds to Colin: " 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."
• 1994-03-16 Paul Crowley jumps in to aid Colin: "I'm with Colin on this one. Since sci.crypt isn't a refereed publication, don't try to make your articles look like "reports" when they have such clear defects."
• 1994-03-16 Prof. Dr. Klaus Pommerening: " I've learned some useful things from Terry Ritter's recent postings."
• 1994-03-16 Brian Olson jumps in to aid Colin: "Colin is one of sci.crypt's best posters. "The rest of us" already take notice, and couldn't help but notice that he fed you your technical lunch. Sorry Terry, but you deserved the slam."
• 1994-03-16 Colin Plumb responds to Terry: "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?"
• 1994-03-16 Terry Ritter: responds to Brian: " And exactly where is this "lunch"? All I see is one-liners and concerted giggling. I'm not sure anyone ever "deserves" a slam. Interesting that someone would think so, however."
• 1994-03-16 Terry Ritter responds to Paul: " I'm with me on this one. Since sci.crypt isn't a refereed publication, I'll format my reports however I like."
• 1994-03-17 Terry Ritter responds to Colin: " 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."
• 1994-03-17 Paul Crowley responds to Terry: "I have usually found free software as widely available as PGP to be more reliable and solid than commercial products..."
• 1994-03-18 John Kelsey: " Are you familiar with Merkle's Khufu and Wood's REDOC cryptosystems? Both of these use a scheme that could be used for cheap, fast mixing of blocks. The basic idea: To mix two 64-bit blocks, you first do some pre-processing, to generate a key table (Wood's term) of 256 64-bit entries."

I note in passing that the mixing that John proposes cannot be a balanced form of mixing. It also combines both "strength" and "mixing," and I'm not sure we know how to evaluate the result. Will strength make up for an unbalanced mixing? How much strength do we need? How much does it have?

As this thread trails off, nobody has been convinced that a weak mixing mechanism can have an advantage in a cryptographic design. Ironically, we now know that about three months earlier, related mixing mechanisms were included in a serious block cipher: In December 1993 the well known and respected cryptographer James Massey presented his design for the SAFER K-64 block at the fast software ciphering conference. SAFER K-64 uses "PHT's" or "Pseudo-Hadamard Transforms" which are similarly weak but are not balanced block mixers.

From a design point of view, one of the most important aspects of Balanced Block Mixing is the provability of change propagation. This is addressed in detail in the Fenced DES design.

Fenced DES

The intent was to find a structure provably stronger than DES, which itself used DES as a component. The design goal was to find some sort of structure which used multiple DES operations to encipher a wider block. This provides much greater strength, with almost single-DES speed.

• 1994-04-29 Terry Ritter: Fenced DES (25K)

Toward Axiomatic Fenced DES

A preliminary attempt to formalize the concept of block mixing, and demonstrate that the mixing structure is inherently strong.

• 1994-05-26 Terry Ritter: Toward Axiomatic Fenced DES (43K)
• 1994-06-02 Bryan Olson: "Please don't call them theorems and proofs if they are not."
• 1994-06-02 Bryan Olson: "Oops."
• 1994-06-05 Terry Ritter responds to Bryan: " Please don't nit-pick new work to death. Few of these statements are actually false; in some cases the wording needs to be refined. Of course, some are defined so poorly that -- upon reflection -- they are probably not worth having.
  The concept of mathematical "proof" is subjective; we don't have a global automatic theorem-checker. We can't just toss this stuff in a machine and have it decide yes or no and where the weakness lies. If I had such a thing, my proofs would pass it.
  I obviously get complaints, but what, no complements? No comments on my proofs of the example Block Mixing Transforms? No complements for finding provable properties which can be used to expand the width of block ciphers as components? If you have been following this process, you know it has involved a serious amount of effort, trial-and-error, and public failure. Success was by no means assured. When it occurs it should be uplifting to all of us."
• 1994-06-05 Bryan Olson responds to Terry: "Thanks for reading my comments. You and I still disagree about the value of your results."
• 1994-06-06 Terry Ritter responds to Bryan: "I claim that Fenced DES is a design for producing efficient mechanisms (e.g., writing programs) which model a very large, invertible, key-selected substitution. I claim that such a substitution is the ideal model of any possible block cipher. I also claim that a mechanism based on the Fenced DES design can compute enough substitutions to have a large-enough keyspace to be cryptographically effective."
• 1994-06-07 Bryan Olson responds to Terry: "Unfortunately, your definitions and theorems don't establish this. If the identity function is an invertible substitution, then it is not the case that being an invertible substitution makes a function a good block cipher. You present no reason to believe that either fenced DES or your substitution boxes will have properties which are approximately average for invertible substitutions."
• 1994-06-09 Terry Ritter responds to Bryan: "It is standard practice to model a strong block cipher as a large invertible substitution. The keyed part of this is the selection of one substitution out of all possible substitutions. If we cared about the structure of a particular substitution, there would be better and worse keys, which would not be encouraging.
  This is a different situation than the small, fixed and known tables inside DES.
  Given this amount of confusion, I have obviously failed to provide a proper context for this exercise."
  

The Context of the Fenced DES Design

An overview of Fenced DES with some proofs and strength discussions.

• 1994-07-01 Terry Ritter: The Context of the Fenced DES Design (42K)

Announcing Realized Prototypes

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

Huge Block Size Discussion

Discussion from the sci.crypt newsgroup.

• 1996-08-23 (150K): It is proposed that huge blocks would be appropriate for block cipher design.
• 1996-09-02 (65K): An attack on Fenced DES is handwaved, but turns out (after a great deal of arduous extraction of facts) to be very incomplete. This is not a successful attack.

Last updated: 1998-01-20