<nettime> 1024-bit RSA keys in danger of compromise

[t byfield <tbyfield@panix.com>]

the 'idealism' of the cyppherpunkish crowd has been suffering from
death by a thousand cuts over the past some years: high-profile ar-
rests (e.g., jim bell), the attenuated orphaning of PGP (by acquis-
ition and non-adoption), the forking of the list(s), the tenacious
and hydra-headed attacks by the USG and private industry ('trusted
hardware' approaches of entertainment corps), and, last but not at
all least, the 'internal' difficulty of getting rabid libertarians
to organize. but this is news: those keys that supposedly took ump-
teen billion years to crack may take only minutes. but the biggest
casualty by far is the cascading fissure in the web of trust. that
was the cpunks' weakest link because, technology aside, it was cul-
tural--and cpunks of course reach for their gun when they hear the i
word 'culture.' 

cheers,
t

----- Forwarded 

http://www.mail-archive.com/cryptography%40wasabisystems.com/msg01950.html

From: "Lucky Green" <shamrock@cypherpunks.to>
Subject: 1024-bit RSA keys in danger of compromise
Date: Sat, 23 Mar 2002 17:38:02 -0800

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

----- Backwarded

#  distributed via <nettime>: no commercial use without permission
#  <nettime> is a moderated mailing list for net criticism,
#  collaborative text filtering and cultural politics of the nets
#  more info: majordomo@bbs.thing.net and "info nettime-l" in the msg body
#  archive: http://www.nettime.org contact: nettime@bbs.thing.net