Large Block DES Newsletter Vol. I, No. 1 Feb. 28, 1994 Terry Ritter, Ed. Current Standings for the Large-Block DES Proposals: I. NxM DES: A B v v k1 -> DES1 k2 -> DES2 v v C D Exchange Right 4 Bytes E F v v k3 -> DES3 k4 -> DES4 v v G H Falls to meet-in-the-middle like double-DES. Falls to a practical attack by Biham, now called "fix-in-the-middle." II. NxM DES Found Weak Announcement of above. III. Isolated Double-DES 2x construct found weak in original article. The 1x construct: A v k1 -> DES1 v B v km -> XOR v C v k2 -> DES2 v D was found weak by Chris Dodd <dodd@csl.sri.com> who pointed out that two different blocks of known-plaintext (A,D) and (A',D') will allow matching (B XOR B') and (C xor X'). (This is similar to Biham's "fix-in-the-middle.") Good going Chris! Also found by Stefan Lucks <lucks@namu01.gwdg.de>. IV. Ladder-DES A B | k1 | v v | XOR <- DES1-----| | | | k2 | | v v |---- DES2 -> XOR | | | k3 | v v | XOR <- DES3 ----| | | | k4 | | v v |---- DES4 -> XOR | | v v C D Joseph C. Konczal <jkonczal@nist.gov> points out that the construct is indeed vulnerable to meet-in-the-middle. I agree, but note that this seems to imply a 112-bit search. Since we don't need more than 112 or 120 bits of strength, I don't see it as a problem. (Indeed, if we could get more strength, we might want to trade it for speed anyway.) 112 bits (or so) is the design goal, which should be enough for a couple of decades. In a normal cipher design, I would expect each key bit to contribute toward strength, but these are hardly normal cipher designs. Especially when we try to expand block size, extra keys may simply provide another small block with the same strength as a previous small block. Keys will be delivered electronically, so the relatively rare delivery of 2x or 4x or even 8x the expected key material should not pose a serious problem. However, Biham reports: "ladder DES is not more secure than 2**88 steps and 2**64 chosen plaintexts." Now, 2^88 cipherings is 2^32 times as strong as the 2^56 currently in DES (and larger than Skipjack), but hardly the 2^112 intended. For the current design the current options are: 1) live with the 2^88 strength (so far!), 2) design the rest of the system to prevent chosen plaintexts, or 3) prevent more than, say, 2^32 block cipherings under a single key. Actually, we need to know exactly what the problem is, and the limits of it, before we can propose a fix, or decide whether the ladder-DES scheme is unfixable. Summary Three substantially different constructs proposed; of these, two fall, and one is wounded. To review, the intent is to find some relatively-simple construct which builds on the assumed strength of DES to deliver wide blocks and something like 112 bits of strength, with less processing than triple-DES. (I see no need for super-strength, unless it is free.) We still do not know whether or not this is possible.