1024-bit RSA keys in danger of compromise

[Damien Miller]

On Sat, 23 Mar 2002, Lucky Green wrote:

> Although the full implications of the proposal were not necessarily
> immediately apparent in the first few days following Bernstein's
> publication, the incremental improvements to parts of NFS outlined in
> the proposal turn out to carry significant practical security
> implications impacting the overwhelming majority of deployed systems
> utilizing RSA or DH as the public key algorithms.

What incremental improvements? Bernstein is the first to point out that
his improvement is asymptotic to key length. Can you offer evidence to the
contrary?

> Coincidentally, the day before the panel, Nicko van Someren announced at
> the FC02 rump session that his team had built software which can factor
> 512-bit RSA keys in 6 weeks using only hardware they already had in the
> office.

DES-56 can be cracked in less than a day, which does little to 
diminish 3DES' standing as a good, conservative cipher. 

> The panel, consisting of Ian Goldberg and Nicko van Someren, put forth
> the following rough first estimates:
> 
> While the interconnections required by Bernstein's proposed architecture
> add a non-trivial level of complexity, as Bruce Schneier correctly
> pointed out in his latest CRYPTOGRAM newsletter, a 1024-bit RSA
> factoring device can likely be built using only commercially available
> technology for a price range of several hundred million dollars to about
> 1 billion dollars.

Can you offer any analysis to back up this hyperbole?

Furthermore, your paragraph could easily be misinterpreted to read that 
Schneier was stating that a 1024 bit RSA cracker is feasible. In fact,
he states pretty much the opposite - that Bernstein's result has little
effect on keysizes in regular use.

[snip]

> -----BEGIN PGP PUBLIC KEY BLOCK-----
> Version: PGP 7.1
> Comment: Problems decrypting this email? Upgrade from PGP 1.x/2.x!

...

Please don't abuse our mailing list to distribute your new key.

-d