1993-09-10 - Re: Crack DES in 3.5 hours for only $1,500,000!

Header Data

From: smb@research.att.com
To: gnu@toad.com (John Gilmore)
Message Hash: 28be1d3451a0bfe274a25a6a1bf7e9accbc9de5adb1d281f2a6c3e38b8011323
Message ID: <9309101339.AA26739@toad.com>
Reply To: N/A
UTC Datetime: 1993-09-10 13:42:43 UTC
Raw Date: Fri, 10 Sep 93 06:42:43 PDT

Raw message

From: smb@research.att.com
Date: Fri, 10 Sep 93 06:42:43 PDT
To: gnu@toad.com (John Gilmore)
Subject: Re: Crack DES in 3.5 hours for only $1,500,000!
Message-ID: <9309101339.AA26739@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


	 Oho!  I now suspect why RC2 and RC4 must remain trade-secret...NSA
	 doesn't want people to know what particular internal algorithm
	 features their brute-force chips are capable of handling!  I recall
	 the discussion of how RC2/4 were invented; NSA told the designer
	 (since identified as Ron Rivest): "No, this is too big; weaken this
	 over here; do fewer rounds here; etc..."  What resulted was suitable
	 for NSA brute-force using chips they had readily available.  It's
	 possible that simple changes to the algorithm would render it much
	 less penetrable by NSA's current hardware.  Ron even knows *which*
	 changes, and I encourage him to tell us.

I'll let Rivest speak for himself about NSA's influence -- but I've
spoken to cryptographers who've seen the algorithm (under
non-disclosure agreements), and they say that RC2 and RC4 are quite
strong *if* you use a long enough key.  They're algorithms with
variable-length keys, and their strength -- and not just their
resistance to exhaustive search -- is related to the key size used.
The gotcha is that only the 40-bit version is exportable.  But we don't
need stories about weakened algorithms to know that NSA can crack
40-bit RC2/4; they'd never have granted a license otherwise.  (And what
does that tell us about 512-bit RSA?)

One more point -- it's been claimed that RC2 and RC4 have an
inherently- slow key setup mechanism.  That can slow down brute-force
attacks tremendously, since it then takes a long time to try each
case.  But it's fine for point-to-point encryptions, where you can
amortize that overhead over many messages.


		--Steve Bellovin





Thread