IP: RSA's FAQ on Bernstein's paper

[Dave Farber <dave () farber net>]

------ Forwarded Message
From: "Kaliski, Burt" <BKaliski () rsasecurity com>
Date: Thu, 11 Apr 2002 16:07:22 -0400
To: "'dave () farber net'" <dave () farber net>
Cc: "'Vin McLellan'" <vin () shore net>
Subject: RSA's FAQ on Bernstein's paper

Dear Mr. Farber,

A couple weeks ago you posted an article by Vin McLellan about Dan
Bernstein's new research on factoring.

RSA Laboratories has just published a FAQ on the subject at
http://www.rsasecurity.com/rsalabs/, which I've also attached below.

-- Burt

Has the RSA algorithm been compromised as a result of Bernstein's Paper?

April 8, 2002


Q. Some recent articles have suggested that 1024-bit RSA keys are no longer
secure. What's going on?

A. In a recent research paper [1], Daniel Bernstein, a mathematics professor
at University of Illinois, observed that the cost of breaking an RSA key -
the product of the amount of hardware needed and the running time - might
not be as great for very large key sizes as previously thought.

Although Bernstein did not himself draw any conclusions about the security
of practical RSA key sizes, such as 1024 bits (and has been careful to
discourage early conclusions), newsgroup messages led to several articles
speculating that 1024-bit RSA keys might be at risk [2][3][5][6][9].

Q. Are 1024-bit RSA keys at risk?

A. They're no more at risk now than before Bernstein's paper appeared.

First, while Bernstein's paper suggests some very clever methods for
reducing the amount of memory required to break very large RSA keys, his
methods are all implementation techniques for the Number Field Sieve,
currently the best method for factoring large numbers. The basic number of
operations required by the Number Field Sieve, however, is not reduced.
Since previous security estimates for 1024-bit RSA keys are based on the
number of operations required by the Number Field Sieve, they still apply.

Second, while the methods introduced in the paper may reduce the cost of
breaking very large RSA keys (the amount of hardware times the running
time), RSA Laboratories finds that practical key sizes such as 1024 bits are
not impacted by the new methods.

Finally, the recent concern [2] [3] [9] about the security of 1024-bit RSA
keys is based in part on a misreading of Bernstein's paper. These references
quote an estimate that for about $1 billion, a national agency could build a
factoring machine based on Bernstein's design that could break a 1024-bit
RSA key in a matter of "seconds to minutes". However, a factor of 10 billion
or more was inadvertently left out of the running time in the preliminary
analysis --- which means that the actual running time, assuming the machine
could be built, would be measured in decades (see Note 1). Moreover,
Bernstein himself is quoted [5] as saying "This is a theoretical advance. I
have no idea and ...nobody else has any idea how practical it might be."

The security of 1024-bit RSA keys is clearly not in jeopardy as a result of
Bernstein's paper. 

Q. How hard is it to break a 1024-bit RSA key?

A. Arjen Lenstra and Eric Verheul [4] posit that by the year 2009, a machine
that could break a 1024-bit RSA key in about a day would cost at least $250
million. This assumes that processor performance continues to double every
18 months, following Moore's Law, and that factoring algorithms improve as
well. Such a machine would probably cost about $160 billion today, which is
consistent with a roughly 80-bit symmetric key size equivalent. (Note 2)

Robert Silverman gives a much higher estimate than Lenstra and Verheul,
considering the amount of memory required by current implementations of the
Number Field Sieve [8]. He estimates that a $10 million machine, using 2000
computer technology, would take about 3,000,000 years to break a 1024-bit
RSA key. This gives a cost-based equivalent of about a 96-bit symmetric key,
providing an additional margin of security. Not all researchers accept that
memory cost will be an issue, however, and this margin will likely diminish
over time as memory costs decrease.

RSA Security continues to actively promote and support these discussions on
the cryptanalysis of the RSA algorithm. It is only through peer review that
we can continue to ensure the strength of the RSA algorithm. The research of
Bernstein and others is tremendously important to the field of cryptography
and should be encouraged.

Q. What key size should I be using?

A. NIST offered a table of proposed key sizes for discussion at its key
management workshop in November 2001 [7]. For data that needs to be
protected no later than the year 2015, the table indicates that the RSA key
size should be at least 1024 bits. For data that needs to be protected
longer, the key size should be at least 2048 bits.

RSA Laboratories considers these to be reasonable general guidelines,
although the sensitivity of the data protected by the key must also be taken
into account. In particular, root keys and other high-value organization
keys should be at least 2048 bits, and users who are particularly cautious
may wish to employ keys larger than 1024 bits sooner.

Q. Do I need to revoke my 1024-bit RSA key?

A. The recent paper by Bernstein and the ensuing discussions don't reveal
any new threats to 1024-bit RSA keys. You may, of course, decide that the
security provided by a 1024-bit RSA key is less than you want for your
(presumably long-term) application, and upgrade to a longer key. But you
needn't do so just because of the recent discussion.

Notes

1. An informal panel was convened at the Financial Cryptography conference
in March 2002 to discuss Bernstein's paper. At the panel, Nicko van Someren
gave a rough estimate of the actual cost of breaking a 1024-bit RSA key
using the ideas in Bernstein's paper. He suggested that the machine could be
built for $1 billion and break a key in "seconds to minutes". These figures
were quoted in a BugTraq posting [3] but the "seconds to minutes" figure was
based on a small misreading of Bernstein's paper. RSA Laboratories'
calculations indicate that the estimate omitted a factor of at least 10
billion, which suggests that without any other optimizations, and assuming
the design is otherwise correct, the running time should be measured in
decades. Assuming other optimizations, van Someren has subsequently stated
that the machine would take "weeks". For a precise estimate, further
research as well as implementation experience is needed.

2. Lenstra and Verheul's Table 1 indicates that with 2002 technology, a
768-bit RSA key is comparable to a 72-bit symmetric key in terms machine
cost (see also Sec. 4.5 of [4]). The estimated cost with 2002 technology is
about $160 million. A 1024-bit RSA key involves about 1000 times as many
operations as a 768-bit RSA key with current methods, so is comparable to an
82-bit symmetric key in terms of machine cost (or even higher, if the
additional memory cost is considered per [8]).


References

[1] D.J. Bernstein. Circuits for Integer Factorization: A Proposal.
Manuscript, November 2001. http://cr.yp.to/papers.html#nfscircuit.

[2] Dennis Fisher. Experts debate risks to crypto. e-Week, March 27, 2002.
http://www.eweek.com/article/0,3658,s=712&a=24663,00.asp.

[3] News Group Discussion. 1024-bit RSA Keys in Danger of Compromise.
BugTraq archive, March 24, 2002.
http://online.securityfocus.com/archive/1/263924.

[4] Arjen K. Lenstra and Eric R. Verheul. Selecting cryptographic key sizes.
Journal of Cryptology, to appear. http://www.cryptosavvy.com/.

[5] Vin McLellan. Factoring friction. Information Security, April 2002.
http://www.infosecuritymag.com/2002/apr/news.shtml#factoringfriction.

[6] James Middleton. 1024-bit encryption is 'compromised'. Vnunet.com,
March, 26, 2002. http://www.vnunet.com/News/1130451.

[7] NIST. Key Management Guideline - Workshop Document. Draft, October 2001.
http://csrc.nist.gov/encryption/kms/key-management-guideline-(workshop).pdf.

[8] Robert D. Silverman. A Cost-Based Security Analysis of Symmetric and
Asymmetric Key Lengths. RSA Laboratories Bulletin #13, April 2000.
http://www.rsasecurity.com/rsalabs/bulletins/.

[9] Kevin Townsend. Bernstein's bombshell. Internet World, March 2002.
http://www.internetworld.co.uk/IW/vRoot/articles/article.cfm?objectid=8A55E6
82-CDD4-4CB0-903C6093FE34E390.


------ End of Forwarded Message

For archives see:
http://www.interesting-people.org/archives/interesting-people/