Ouch! From BugTraq in case you haven't already seen it. Tony Wasson ----- Original Message ----- From: "Lucky Green" To: 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 , 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 (Cut PGP keys, if you need Lucky's PGP keys, email him)