Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!sundc!pitstop!sun!amdcad!ames!ucbcad!ucbvax!ulysses!smb
From: smb@ulysses.homer.nj.att.com (Steven Bellovin)
Newsgroups: sci.crypt
Subject: Re: Double Des
Message-ID: <3123@ulysses.homer.nj.att.com>
Date: Tue, 27-Oct-87 20:57:09 EST
Article-I.D.: ulysses.3123
Posted: Tue Oct 27 20:57:09 1987
Date-Received: Sat, 31-Oct-87 00:56:38 EST
References: <1290007@hpcvlo.HP.COM>
Organization: AT&T Bell Laboratories, Murray Hill
Lines: 21

Let me suggest that folks interested in multiple encryption consult
"On the Security of Multiple Encryption", by Merkle and Hellman, in the
July 1981 CACM.  I won't run through their proofs; their conclusions
are fairly simple. First, a doubly-encrypted text can be cracked by
a ``meet-in-the-middle'' attack in o(2**56) operations, but at a cost
of o(2**56) words of memory, using a known-plaintext attack.  Second,
triple encryption using three independent keys would require o(2**112)
operations, and hence is immune to any brute-force scheme.  A variant --
encrypting with K1, decrypting with K2, then re-encrypting with K1 --
requires the same effort and space as simple double encryption, but
would require a chosen-plaintext attack.

An interesting sidelight is that the meet-in-the-middle attacks will
yield a number of false matches, about 2**48.  Having 64 additional bits
of known plaintext will reduce the error rate to 2**-16.

They conclude that multiple encryption does offer advantages (enough
6250 bpi tapes to hold the 2**56 words of storage would cost ~$80e9
at $20 per tape, and hence is presumably beyond NSA's reach, especially
since you have to sort the tpaes....).  However, a 112 bit key would
still be much stronger.