1024-bit RSA keys in danger of compromise

[Lucky Green]

Damien wrote:
> 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?

Are you disputing that Bernstein's paper offered improvements to the
state-of-the-art in NFS-based factoring or are you disputing that the
improvements are incremental? Either way, you would be wrong:

- Improvements over the previously known state-of-the art: as you point
out, Bernstein states that he found improvements to NFS that
*asymptotically* may go as high as a factor of 3. If you knew about this
improvement prior to Bernstein's publication, you are to be
congratulated. Too bad you failed to publish. As for the remainder of
the cryptographic community, I have not met a single person that had
known about these improvements prior to Bernstein pointing them out.

- Why the improvements are incremental, rather than revolutionary to the
prior state-of-the-art in factoring: Bernstein did not propose a new
approach to factoring, such as the move from the Quadratic Sieve to the
General Number Field Sieve. Hence the improvements are incremental.

> > 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. 

You point being? All that the paragraph you are quoting stated was that
I had been unaware that 512-bit RSA keys can be factored using the
hardware found in an office, with the most "specialized box", btw, being
an Itanium with 1GB of RAM. Not exactly special-purpose equipment that's
hard to come by. If you were attempting to imply that the paragraph was
meant as supporting evidence for the 1024-bit factoring issues mentioned
later in my post, I would encourage you to look up the word
"coincidentally" in a dictionary.

> > 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?

Hyperbole. Hmm, we are moving on to big words now. Are you sure you are
ready to use such words when you don't even know what coincidentally
means?

My post made it clear to those versed in the English language that I was
simply reporting on the analyses presented by a panel that I happened to
moderate. Which, in case the reader is unfamiliar with what the word
moderate means, equates to ensuring that the panelists all get chance to
speak and don't stray too far off topic. The results reported are not
the results of my research. I therefore will leave it to the researchers
to post the details of the analysis once they are written up in the
customary form. (Which is not to say that such details had not been
provided, I simply don't believe it is my role or right to publish the
details of others' research).

> 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.

English language hint #3: note the two commas used in the sentence to
which you are referring. Then find a book on elementary English grammar
to determine what their purpose might have been.

As a general note, you might find that future comments directed at me
and others stand a good chance of leading to more fruitful discussion
that in turn will be more pleasing to you if your inquiries were to take
a less a hostile and accusatory tone.

--Lucky