From: smb@research.att.com
Date: Fri, 10 Sep 93 08:27:45 PDT
To: "David LANDGREN, PUB " <David.D.L.LANDGREN@PUB.oecd.fr>
Subject: Re: ... long live DES (sic)
Message-ID: <9309101526.AA28428@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


	 It's all very well to be able to crack DES in 3.5 hours, but I
	 don't know of too many people who obligingly send out the
	 plaintext and cyphertext of a message together, or in some
	 other way combinable.  If U can get the plaintext of a
	 DES-encrypted msg then U don't need to dick around with DES
	 anyway.  No-one ever said it was bulletproof; a direct
	 consequence is that DES users change their keys awful
	 frequently.

It's not that simple; Wiener's design is indeed a major breakthrough
(for the open literature, of course).

First of all, one can often guess probable plaintext for some of the
message.  Here's the first line of your note as it (apparently) left
your machine:

	Date: 10 Sep 93 10:30:12 GMT

If I've ever received mail from you, and hence know that format, I know
at least the first 6 bytes, and the format of the next two.  If I know
the date of the intercept, I have even more.  Poof -- a crib.

I can do even better.  Look at the $10,000,000 machine -- the one with
a 21-minute solution.  I can afford to try several guesses for where
the string `Date: ' occurs.  It doesn't take that much more complex a
chip to look for obvious variants, such as that string occuring shifted
over one or two bytes in either direction.  You may get some false
positives, but a second-order search machine can then apply more complex
heuristics to possible keys returned by Wiener's design.

And historically, enemies have been able to get probable plaintext --
or even some chosen plaintext -- for at least a few messages.  Read
``The Codebreakers'' or ``Seizing the Enigma'' for many such examples.

There's one more step here, described in detail in Garon and Outerbridge's
``DES Watch'' paper.  If the DES session key is transmitted encrypted
by DES using a 56-bit master key, you're dead meat.  I can crunch for
weeks to recover one session key, using many possibilities for the plaintext
and its location in the ciphertext.  But once I recover that long-gone
session key, I can use it as the known plaintext to recover your master
key.  And after that, the jig is up.

No, there should be no mistake about it.  Single DES is *dead*, for any
application where recovery of a single session key is bad.  If you want
to stick with single DES, you need to change session keys very often
(every few seconds against an enemy who can build a $10M machine), and
you need to distribute session keys by some other mechanism (i.e., RSA,
Diffie-Hellman, triple DES).


		--Steve Bellovin