Re: 2048-bit RSA keys
It's worth a quote from the paper at CRYPTO '10 on factorization of a 768-bit number: A good paper by top academics. Another conclusion from our work is that we can confidently say that if we restrict ourselves to an open community, academic effort such as ours and unless something dramatic happens in factoring, we will not be able to factor a 1024-bit RSA modulus within the next five years [27]. After that, all bets are off. The 768-bit team started crunching in early 2007 and completed three years later in December 2009. They used fewer than a thousand commercially available unspecialized computers, connected by commercially available interconnects. Their intermediate results fit on less than a dozen $150 2TB disk drives. And one of their results is that it's better to scale up the part of the process that scales linearly with minimal communication (sieving), to reduce the complexity of the nonlinear parts. (Given their prediction that they won't be done with a 1024-bit number within 5 years, but they will be done well within the next decade, which 1024-bit number are they starting to factor now? I hope it's a major key that certifies big chunks of the Internet for https today, rather than one of those silly challenge keys.) Their reported time and difficulty results are great lower bounds on the capabilities of the covert or criminal -- but don't mistake them for upper bounds! No open-community academic has ever designed, built and deployed special-purpose hardware for factoring numbers of this size. Yet they have published designs that claim order-of-magnitude speedups or better on time-consuming parts of the process. EFF read similar published paper designs for DES cracking. When a few years later we built the actual device, we discovered that the basic structure of the academics' designs really did work. There are good reasons to believe that the covert community *has* built RSA cracking hardware as good or better than what's been publicly designed. And in some places covert agencies and organized crime are partners, thus merely stealing large amounts of money, as opposed to military objectives, might motivate a covert key crack. Here is Europe's consensus report on recommended key sizes, also co-authored by Lenstra: ECRYPT2 Yearly Report on Algorithms and Keysizes (2010). http://www.ecrypt.eu.org/documents/D.SPA.13.pdf For RSA, we recommend |N| = 1024 for legacy systems and |N| = 2432 for new systems. A more accessible table of ECRYPT2-2010 recommendations: http://www.keylength.com/en/3/ RSA Bits Security level -- 1008: Short-term protection against medium organizations, medium-term protection against small organizations 1248: Very short-term protection against agencies, long-term protection against small organizations Smallest general-purpose level, 1776: Legacy standard level 2432: Medium-term protection 3248: Long-term protection Generic application-independent recommendation, protection from 2009 to 2040 15424: Foreseeable future Good protection against quantum computers, unless Shor's algorithm applies John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 2048-bit RSA keys
On Aug 17, 2010, at 10:25 PM, John Gilmore wrote: (Given their prediction that they won't be done with a 1024-bit number within 5 years, but they will be done well within the next decade, which 1024-bit number are they starting to factor now? I hope it's a major key that certifies big chunks of the Internet for https today, rather than one of those silly challenge keys.) If they announced which key they were working on, I would completely expect someone to demand a very amusing injunction against the performing of arithmetical operations. When mathematics is outlawed ... - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 2048-bit RSA keys
Bill Stewart bill.stew...@pobox.com writes: Basically, 2048's safe with current hardware until we get some radical breakthrough like P==NP or useful quantum computers, and if we develop hardware radical enough to use a significant fraction of the solar output, we'll probably find it much easier to eavesdrop on the computers we're trying to attack than to crack the crypto. Another breakthrough in integer factoring could be sufficient for an attack on RSA-2048. Given the number of increasingly efficient integer factorization algorithms that have been discovered throughout history, another breakthrough here seems more natural than unlikely to me. /Simon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 2048-bit RSA keys
On Tue, 17 Aug 2010 22:32:52 +0200 Simon Josefsson si...@josefsson.org wrote: Bill Stewart bill.stew...@pobox.com writes: Basically, 2048's safe with current hardware until we get some radical breakthrough like P==NP or useful quantum computers, and if we develop hardware radical enough to use a significant fraction of the solar output, we'll probably find it much easier to eavesdrop on the computers we're trying to attack than to crack the crypto. Another breakthrough in integer factoring could be sufficient for an attack on RSA-2048. Given the number of increasingly efficient integer factorization algorithms that have been discovered throughout history, another breakthrough here seems more natural than unlikely to me. A breakthrough could also render 10kbit keys broken, or might never happen at all. A breakthrough could make short ECC keys vulnerable. A breakthrough could make AES vulnerable. One can't operate on this basis -- it makes it impossible to use anything other than one-time pads. -- Perry E. Metzgerpe...@piermont.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 2048-bit RSA keys
On 17-08-2010 21:42, Perry E. Metzger wrote: On Tue, 17 Aug 2010 22:32:52 +0200 Simon Josefsson si...@josefsson.org wrote: Bill Stewart bill.stew...@pobox.com writes: Basically, 2048's safe with current hardware until we get some radical breakthrough like P==NP or useful quantum computers, and if we develop hardware radical enough to use a significant fraction of the solar output, we'll probably find it much easier to eavesdrop on the computers we're trying to attack than to crack the crypto. Another breakthrough in integer factoring could be sufficient for an attack on RSA-2048. Given the number of increasingly efficient integer factorization algorithms that have been discovered throughout history, another breakthrough here seems more natural than unlikely to me. A breakthrough could also render 10kbit keys broken, or might never happen at all. A breakthrough could make short ECC keys vulnerable. A breakthrough could make AES vulnerable. One can't operate on this basis -- it makes it impossible to use anything other than one-time pads. A breakthrough is a rather strong term. But it's not unreasonable to believe that the number field sieve's complexity could be lowered on the near future by an *incremental* improvement --- it would only require lowering the complexity from L[1/3, ~1.92] to L[1/3, ~1.2] to make 2048 bit factorization roughly as easy as 768 bits today. Coppersmith's variant of the number field sieve proposed a tradeoff that dramatically lowered the exponent, if one wanted to break many keys of roughly the same size. The idea was to fix m, the 'base' of the number field polynomial, and precompute many many pairs (a,b) such that a - bm was smooth. With this precomputation, the NFS runs in L[1/3, ~1.639], which is dramatically faster (and quite worth it for a large organization --- they're bound to want to break multiple keys). It is not unreasonable to think that a small(ish) improvement to the number field sieve could significantly lower the strength of current keys. It *looks* more likely to happen than a significant improvement on the speed of ECDLP breaking (I'll make no bets on AES, though). Best regards, Samuel Neves - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 2048-bit RSA keys
On Aug 17, 2010, at 5:19 10PM, Samuel Neves wrote: On 17-08-2010 21:42, Perry E. Metzger wrote: On Tue, 17 Aug 2010 22:32:52 +0200 Simon Josefsson si...@josefsson.org wrote: Bill Stewart bill.stew...@pobox.com writes: Basically, 2048's safe with current hardware until we get some radical breakthrough like P==NP or useful quantum computers, and if we develop hardware radical enough to use a significant fraction of the solar output, we'll probably find it much easier to eavesdrop on the computers we're trying to attack than to crack the crypto. Another breakthrough in integer factoring could be sufficient for an attack on RSA-2048. Given the number of increasingly efficient integer factorization algorithms that have been discovered throughout history, another breakthrough here seems more natural than unlikely to me. A breakthrough could also render 10kbit keys broken, or might never happen at all. A breakthrough could make short ECC keys vulnerable. A breakthrough could make AES vulnerable. One can't operate on this basis -- it makes it impossible to use anything other than one-time pads. A breakthrough is a rather strong term. But it's not unreasonable to believe that the number field sieve's complexity could be lowered on the near future by an *incremental* improvement --- it would only require lowering the complexity from L[1/3, ~1.92] to L[1/3, ~1.2] to make 2048 bit factorization roughly as easy as 768 bits today. It's worth quote from the paper at CRYPTO '10 on factorization of a 768-bit number: The new NFS record required the following effort. We spent half a year on 80 processors on polynomial selection. This was about 3% of the main task, the sieving, which took almost two years on many hundreds of machines. On a single core 2.2 GHz AMD Opteron processor with 2 GB RAM, sieving would have taken about fifteen hundred years. We did about twice the sieving strictly necessary, to make the most cumbersome step, the matrix step, more manageable. Preparing the sieving data for the matrix step took a couple of weeks on a few processors. The final step after the matrix step took less than half a day of computing. They conclude with at this point factoring a 1024-bit RSA modulus looks more than five times easier than a 768-bit RSA modulus looked back in 1999, when we achieved the first public factorization of a 512-bit RSA modulus. Nevertheless, a 1024-bit RSA modulus is still about a thousand times harder to factor than a 768-bit one. It may be possible to factor a 1024-bit RSA modulus within the next decade by means of an academic effort on the same scale as the effort presented here. Recent standards recommend phasing out such moduli by the end of the year 2010 [28]. See also [21]. Another conclusion from our work is that we can confidently say that if we restrict ourselves to an open community, academic effort such as ours and unless something dramatic happens in factoring, we will not be able to factor a 1024-bit RSA modulus within the next five years [27]. After that, all bets are off. They also suggest that a 3-4 year phase-out of 1024-bit moduli is the proper course. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 2048-bit RSA keys
Forwarded at Andrew's request. Original Message Subject: Re: 2048-bit RSA keys Date: Tue, 17 Aug 2010 19:11:55 -0500 (CDT) From: Andrew Odlyzko odly...@umn.edu To: Samuel Neves sne...@dei.uc.pt CC: cryptography@metzdowd.com It is not unreasonable to consider the possibility of algorithmic improvements. But that does not guarantee accuracy. My 1995 paper The future of integer factorization, http://www.dtc.umn.edu/~odlyzko/doc/future.of.factoring.pdf published in CryptoBytes (The technical newsletter of RSA Laboratories), vol. 1, no. 2, 1995, pp. 5-12, considered the historical record of integer factorizations up to that point, and took account both of the increasing computing power and the progress in algorithms (which over the preceding 20 years contributed about as much as the growth in the number of available cycles). It then projected when integers of various sizes might get factored, and even the most conservative projection had 768-bit integers getting factored by 2004 or so. In retrospect, the latest 768-bit factorization shows that over the preceding 15 years there has been practically no progress in algorithms, and even the computing power that is actually used for the experiments has fallen behind projections. Andrew On Tue, 17 Aug 2010, Samuel Neves wrote: On 17-08-2010 21:42, Perry E. Metzger wrote: On Tue, 17 Aug 2010 22:32:52 +0200 Simon Josefsson si...@josefsson.org wrote: Bill Stewart bill.stew...@pobox.com writes: Basically, 2048's safe with current hardware until we get some radical breakthrough like P==NP or useful quantum computers, and if we develop hardware radical enough to use a significant fraction of the solar output, we'll probably find it much easier to eavesdrop on the computers we're trying to attack than to crack the crypto. Another breakthrough in integer factoring could be sufficient for an attack on RSA-2048. Given the number of increasingly efficient integer factorization algorithms that have been discovered throughout history, another breakthrough here seems more natural than unlikely to me. A breakthrough could also render 10kbit keys broken, or might never happen at all. A breakthrough could make short ECC keys vulnerable. A breakthrough could make AES vulnerable. One can't operate on this basis -- it makes it impossible to use anything other than one-time pads. A breakthrough is a rather strong term. But it's not unreasonable to believe that the number field sieve's complexity could be lowered on the near future by an *incremental* improvement --- it would only require lowering the complexity from L[1/3, ~1.92] to L[1/3, ~1.2] to make 2048 bit factorization roughly as easy as 768 bits today. Coppersmith's variant of the number field sieve proposed a tradeoff that dramatically lowered the exponent, if one wanted to break many keys of roughly the same size. The idea was to fix m, the 'base' of the number field polynomial, and precompute many many pairs (a,b) such that a - bm was smooth. With this precomputation, the NFS runs in L[1/3, ~1.639], which is dramatically faster (and quite worth it for a large organization --- they're bound to want to break multiple keys). It is not unreasonable to think that a small(ish) improvement to the number field sieve could significantly lower the strength of current keys. It *looks* more likely to happen than a significant improvement on the speed of ECDLP breaking (I'll make no bets on AES, though). Best regards, Samuel Neves - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 2048-bit RSA keys
On Tue, 17 Aug 2010, Steven Bellovin wrote: They also suggest that a 3-4 year phase-out of 1024-bit moduli is the proper course. Note that this is because they take into consideration that secrets have to be unbreakable for decade(s), which is not the case for all uses of RSA. For example in DNSSEC, a key can be rolled in a matter of hours or days. Paul - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 2048-bit RSA keys
On 2010-08-17 3:46 PM, Jonathan Katz wrote: Many on the list may already know this, but I haven't seen it mentioned on this thread. The following paper (that will be presented at Crypto tomorrow!) is most relevant to this discussion: Factorization of a 768-bit RSA modulus, http://eprint.iacr.org/2010/006 Which tells us that ordinary hobbyist and academic efforts will not be able to factor a 1024 bit RSA modulus by brute force until around 2015 or so - but dedicated hardware and so forth might be able to do it now. What is the latest news on cracking by ECC by brute force? - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 2048-bit RSA keys
Paul Hoffman wrote: You are under the wrong impression, unless you are reading vastly different crypto literature than the rest of us are. RSA-1024 *might* be possible to break in public at some point in the next decade, and RSA-2048 is a few orders of magnitude harder than that. Just out of curiosity, assuming the optimal use of today's best of breed factoring algorithms - will there be enough energy in our solar system to factorize a 2048-bit RSA integer? - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 2048-bit RSA keys
At 11:35 AM +1000 8/16/10, Arash Partow wrote: Paul Hoffman wrote: You are under the wrong impression, unless you are reading vastly different crypto literature than the rest of us are. RSA-1024 *might* be possible to break in public at some point in the next decade, and RSA-2048 is a few orders of magnitude harder than that. Just out of curiosity, assuming the optimal use of today's best of breed factoring algorithms - will there be enough energy in our solar system to factorize a 2048-bit RSA integer? We have no idea. The methods used to factor number continue to slowly get better, and it has been quite a while since there was a single large improvement. That could mean that there are no more improvements to be made, or that some smart cryptographer who isn't focused on the SHA-3 competition is about to make another big improvement, or something in between. --Paul Hoffman, Director --VPN Consortium - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 2048-bit RSA keys
On Aug 15, 2010, at 8:35 PM, Arash Partow wrote: Just out of curiosity, assuming the optimal use of today's best of breed factoring algorithms - will there be enough energy in our solar system to factorize a 2048-bit RSA integer? Computation can be performed with arbitrarily small energy expenditure or entropy increase. http://en.wikipedia.org/wiki/Reversible_computing Not by the architectures we use, of course. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 2048-bit RSA keys
On Mon, 16 Aug 2010 12:42:41 -0700 Paul Hoffman paul.hoff...@vpnc.org wrote: At 11:35 AM +1000 8/16/10, Arash Partow wrote: Just out of curiosity, assuming the optimal use of today's best of breed factoring algorithms - will there be enough energy in our solar system to factorize a 2048-bit RSA integer? We have no idea. The methods used to factor number continue to slowly get better,[...] He asked about today's best of breed algorithms, not future ones. In that context, and assuming today's most energy efficient processors rather than theoretical future processors, the question has a concrete answer. Perry -- Perry E. Metzgerpe...@piermont.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 2048-bit RSA keys
At 01:54 PM 8/16/2010, Perry E. Metzger wrote: On Mon, 16 Aug 2010 12:42:41 -0700 Paul Hoffman paul.hoff...@vpnc.org wrote: At 11:35 AM +1000 8/16/10, Arash Partow wrote: Just out of curiosity, assuming the optimal use of today's best of breed factoring algorithms - will there be enough energy in our solar system to factorize a 2048-bit RSA integer? We have no idea. The methods used to factor number continue to slowly get better,[...] He asked about today's best of breed algorithms, not future ones. In that context, and assuming today's most energy efficient processors rather than theoretical future processors, the question has a concrete answer. With today's best-of-breed algorithms and hardware designs, there isn't enough money in the economy to build a machine that comes close to making a scratch in the surface of that kind of energy consumption, whether for factoring or for simple destruction. Basically, 2048's safe with current hardware until we get some radical breakthrough like P==NP or useful quantum computers, and if we develop hardware radical enough to use a significant fraction of the solar output, we'll probably find it much easier to eavesdrop on the computers we're trying to attack than to crack the crypto. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
