This was just reposted to the isp-security mailing list. I know there are
some crypto-heads on this list; anyone have more information?
-Original Message-
From: Lucky Green [mailto:[EMAIL PROTECTED]]
Sent: Saturday, March 23, 2002 8:38 PM
To: [EMAIL PROTECTED]
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
