Cringely Gives KnowNow Some Unbelievable Free Press... (fwd)

bear bear at sonic.net
Mon Feb 25 14:49:26 EST 2002


[Moderator's inquiry: Any third parties care to comment on this? --Perry]

On Thu, 21 Feb 2002, Phillip H. Zakas wrote:

>> >On Tue, 5 Feb 2002, Eugene Leitl wrote:

>> >But at Crypto last August, Dan Bernstein announced a new design for a
>> >machine dedicated to NFS using asymptotically fast algorithms and
>> >optimising memory, CPU power and amount of parallelism to minimize
>>
> Bear Responds:
>> I really want to read this paper; if we don't get to see the
>> actual mathematics, claims like this look incredibly like
>> someone is spreading FUD. Is it available anywhere?
>>
>
>The paper is located here: http://cr.yp.to/papers.html
>I've not evaluated yet but I'm interested in hearing if he received his
>grant to try it out.

Holy shit.  The math works.  Bernstein has found ways of
using additional hardware to eliminate redundancies and
inefficiencies which appear in any linear implementation of the
Number Field Sieve.  We just never noticed that they were
inefficiencies and redundancies because we kept thinking in
terms of linear implementations.  This is probably the biggest
news in crypto in the last decade.  I'm astonished that it
hasn't been louder.

Note that there have been rumors of an RSA cracker built by a
three-letter agency in custom silicon before this, but until
analyzing Bernstein's paper I had always dismissed them as
ridiculous paranoid fantasies.  Now it looks like such a device
is entirely feasible and, in fact, likely.

This work demonstrates a lack of security in a bunch of PGP Keys.
All previous estimations of security level as a function of bit
length, should be applied as though the bit length were one-third
of its actual length.  This means that effectively all PGP RSA
keys shorter than 2k bits are insecure, and the 2kbit keys are
not nearly as secure as we thought they were.

I remember there was one version of PGP that allowed RSA keys
longer than 2kbits - I don't remember what version it was right
now, but someone is sure to remind us now that I've said so. :-)
Anyway, probably very few people are using 4kbit or 8kbit PGP
RSA keys anyhow, due to lack of cross-version compatibility.

The "secure forever" level of difficulty that we used to believe
we got from 2kbit keys in RSA is apparently a property of 6kbit
keys and higher, barring further highly-unexpected discoveries.

Recommendation to all implementors:  Future applications should
not offer to create RSA keys shorter than 2048 bits, and should
allow users to specify keys of up to *at least* 8 kbits in length.
Remember, backward compatibility is inappropriate where it
compromises security.

Recommendation to all crypto users: discontinue use of RSA keys
shorter than 2048 bits, NOW.  Issue a revocation if the software
you use allows it.  If the software you use is restricted to
RSA keys shorter than 2048 bits, get rid of it and find something
better.

I predict that Elliptic-Curve systems are about to become more
popular.

				Bear



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com



More information about the cryptography mailing list