Fw: 1024-bit RSA keys in danger of compromise

[Tony Wasson]

Ouch! From BugTraq in case you haven't already seen it.

Tony Wasson

----- Original Message ----- 
From: "Lucky Green" <shamrock@cypherpunks.to>
To: <cypherpunks@lne.com>
Sent: Saturday, March 23, 2002 6:38 PM
Subject: 1024-bit RSA keys in danger of compromise


> As those of you who have discussed RSA keys size requirements with me
> over the years will attest to, I always held that 1024-bit RSA keys
> could not be factored by anyone, including the NSA, unless the opponent
> had devised novel improvements to the theory of factoring large
> composites unknown in the open literature. I considered this to be
> possible, but highly unlikely. In short, I believed that users' desires
> for keys larger than 1024-bits were mostly driven by a vague feeling
> that "larger must be better" in some cases, and by downright paranoia in
> other cases. I was mistaken.
> 
> Based upon requests voiced by a number of attendees to this year's
> Financial Cryptography conference <http:/www.fc02.ai>, I assembled and
> moderated a panel titled "RSA Factoring: Do We Need Larger Keys?". The
> panel explored the implications of Bernstein's widely discussed
> "Circuits for Integer Factorization: a Proposal".
> http://cr.yp.to/papers.html#nfscircuit
> 
> 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.
> 
> 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.
> 
> A very interesting result, indeed. (While 512-bit keys had been broken
> before, the feasibility of factoring 512-bit keys on just the computers
> sitting around an office was news at least to me).
> 
> 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. Costs may well drop lower if one has the use of a
> chip fab. It is a matter of public record that the NSA as well as the
> Chinese, Russian, French, and many other intelligence agencies all
> operate their own fabs.
> 
> Some may consider a price tag potentially reaching $1B prohibitive. One
> should keep in mind that the NRO regularly launches SIGINT satellites
> costing close to $2B each. Would the NSA have built a device at less
> than half the cost of one of their satellites to be able to decipher the
> interception data obtained via many such satellites? The NSA would have
> to be derelict of duty to not have done so.
> 
> Bernstein's machine, once built, will have power requirements in the MW
> to operate, but in return will be able to break a 1024-bit RSA or DH key
> in seconds to minutes. Even under the most optimistic estimates for
> present-day PKI adoption, the inescapable conclusion is that the NSA,
> its major foreign intelligence counterparts, and any foreign commercial
> competitors provided with commercial intelligence by their national
> intelligence services have the ability to break on demand any and all
> 1024-bit public keys.
> 
> The security implications of a practical breakability of 1024-bit RSA
> and DH keys are staggering, since of the following systems as currently
> deployed tend to utilize keys larger than 1024-bits:
> 
> - HTTPS
> - SSH
> - IPSec
> - S/MIME
> - PGP
> 
> An opponent capable of breaking all of the above will have access to
> virtually any corporate or private communications and services that are
> connected to the Internet.
> 
> The most sensible recommendation in response to these findings at this
> time is to upgraded your security infrastructure to utilize 2048-bit
> user keys at the next convenient opportunity. Certificate Authorities
> may wish to investigate larger keys as appropriate. Some CA's, such as
> those used to protect digital satellite content in Europe, have already
> moved to 4096-bit root keys.
> 
> Undoubtedly, many vendors and their captive security consultants will
> rush to publish countless "reasons" why nobody is able to build such a
> device, would ever want to build such a device, could never obtain a
> sufficient number of chips for such a device, or simply should use that
> vendor's "unbreakable virtual onetime pad" technology instead.
> 
> While the latter doesn't warrant comment, one question to ask
> spokespersons pitching the former is "what key size is the majority of
> your customers using with your security product"? Having worked in this
> industry for over a decade, I can state without qualification that
> anybody other than perhaps some of the HSM vendors would be misinformed
> if they claimed that the majority - or even a sizable minority - of
> their customers have deployed key sizes larger than 1024-bits through
> their organization. Which is not surprising, since many vendor offerings
> fail to support larger keys.
> 
> In light of the above, I reluctantly revoked all my personal 1024-bit
> PGP keys and the large web-of-trust that these keys have acquired over
> time. The keys should be considered compromised. The revoked keys and my
> new keys are attached below.
> 
> --Lucky Green

<SNIP> (Cut PGP keys, if you need Lucky's PGP keys, email him)