Re: Crack DES in 3.5 hours for only $1,500,000!

[smb@research.att.com]

	 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