From: smb@research.att.com
Date: Wed, 11 Aug 93 12:52:22 PDT
To: pmetzger@lehman.com
Subject: Re: How long would it take?
Message-ID: <9308111952.AA11810@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


	 Its generally unwise to make the assumption that the only possible
	 attack on your conventional scheme is a brute force attack. Certainly
	 the attacks used on many previous generations of cryptosystems were
	 never brute force -- and certainly every generation of naive
	 cryptographer has said "well, using brute force it would take N years
	 to break my cypher". A simple vingenere cypher with a 12 letter key
	 would seem to be very strong indeed (stronger than DES), and yet we
	 know you can break one in a few moments because there are better
	 attacks than brute force.

	 We have suprisingly little in the way of general theory on what would
	 or would not make a conventional cryptosystem strong.  Certainly
	 differential cryptanalysis will not be the last thing people come up
	 with. Until we know everything the NSA knows, I will be hesitant to
	 say "unless something better comes up" and more comfortable saying
	 "until something better comes up."

Indeed.  The key length is a worst-case analysis for the cryptanalyst;
they can do no worse than that.  We can be confident that NSA has cracked
DES because an exhaustive search engine is within their means, but we
don't know how much better they can do.

A while back, Shamir gave a talk on differential cryptanalysis here at
Murray Hill.  He mentioned Coppersmith's letter, which said that IBM
knew about differential cryptanalysis back when they built DES, and they
designed it to resist the attack.  That's obviously the case -- so Shamir
said that he asked Coppersmith to state that in the intervening 18 years,
IBM had not come up with a stronger attack on DES.  Coppersmith was
silent, from which you can draw any conclusions you wish.