12 ms·
2048 Bit RSA and the Year 2030
- roomey 3y agoI think the point is as computers get faster there is less trade off in having longer bit lengths, rather than focusing on the potential to crack sad keys. That is, if it costs very little to have larger keys, why not have larger keys? It is essentially hedging your bets as even if quantum computing key factorisation works, key lengths will still have an impact on the difficulty of factorisation, and it may make a difference in terms of practicality.
- nailer 3y agoThey cover that in the article: > Quantum computing of the sort intended to break RSA involves a breakthrough in both computing and algorithms. Normally some sort of new computing technology is invented and then algorithms are designed to enable that technology to do something useful. The quantum computing threat to RSA is different. We now have the algorithm (Shor's) but the computer to run it on only exists in our imagination. > If someone were to invent such a computer then RSA 2048 would be immediately and trivially breakable. RSA 3072 would also be trivially breakable. The same applies to RSA 4096 and 8192.
- roomey 3y agoThey can't know that however, they may say it but they can't know it. Hence why not choose key lengths by looking at encoding and decoding resource usage instead of crackability. By costs nothing I mean as CPUs get faster there is less performance impact on lenghtening keys
- nailer 3y agoThey already are, hence everyone moving to ED25519 (which uses less CPU for the equivalent key strength) instead of RSA.
- hujun 3y ago`That is, if it costs very little to have larger keys, why not have larger keys?` it is often very expensive/difficult to change length of a RSA key is part of existing platform/infrastructure, like key in TPM/HSM/CA infrastructure, regardless how fast computer CPU is
- zokier 3y agoBut RSA has been long time going out, and short-keyed RSA doubly so. I would estimate that since maybe 2015ish deploying stuff that is coupled to 2048bit RSA would have been mistake. That gives generous 15ish year transition period. Anyone who cares even the slightest should succeed transition in that sort of timeframe.
- tptacek 3y agoWhy would deploying 2048 bit RSA be a mistake? If you believe 2048 is threatened in a meaningful time frame, when 1024 hasn't even been broken (thus sort of implying that the collapse of 2048 will occur in a much shorter time frame than the one separating 512 and 1024), is there any realistic RSA key size that should make you comfortable?
- adgjlsfhk1 3y ago3 reasons 1. it's reasonable to assume the NSA is a decade ahead and has more computers than academia. 2. you want your secrets to last a decade (or longer) 3. the total amount of data you're encrypting per client is only 256 bits anyway (the size of a symmetric key) so the absolute performance impact is relatively minimal
- bawolff 3y ago> even if quantum computing key factorisation works, key lengths will still have an impact on the difficulty of factorisation, and it may make a difference in terms of practicality. I mean, the whole thing with quantum computer factoring is it scales well. Getting to 2048 rsa seems really really difficult. But if we ever get there, getting to 4096 is probably just a tiny extra step.
- alphager 3y agoThe current state of quantum computing suggests that there is an exponential effort to increase the available qbits. Going from RSA 2048 to RSA 4096 would not just double the effort required on the quantum side.
- upofadown 3y agoWouldn't that effectively prevent a threat to 2048 bit RSA in the first place?
- ihattendorf 3y agoAlmost like there's no free lunch. I don't see quantum computing ever really taking off without a fundamental breakthrough in our understanding of physics. Would love to be proven wrong though if my understanding is incorrect and there's actually a feasible path towards quantum computing at scale.
- bawolff 3y agoI dont think there is any fundamental physics reasons preventing quantum computers. My understanding is it is an engineering problem. A hard one no doubt, but not a fundamental physics one. Anyways, my point was that getting a quantum computer at a decent scale is really difficult. If we manage to overcome that burden somehow, the difference between 2048 bit rsa abd 4096 bit is peanuts.
- roomey 3y agoWell, we can't know. Maybe it would be trivial, maybe it could keep your data safe for 5ore years. Maybe it could double the cost to crack. No one can know at the moment, hence the trade off, if it costs very little to do a longer key, why not do a longer key?
- slater 3y agoServer appears to be hugged, web archive link: https://web.archive.org/web/20230710195916/https://articles.59.ca/doku.php?id=em:20482030 https://web.archive.org/web/20230710195916/https://articles....
- ignoramous 3y agohttps://archive.is/VaLO8 https://archive.is/VaLO8
- capableweb 3y agoUnless you're worried about storing and/or transmitting a huge amount of keys (in the order of "at least 100/second") and/or using one key "at least 100 times/second", why not just go for 4096 by default?
- upofadown 3y agoIf you accept the current assumptions, then you would have to accept that 4096 bit RSA will be obsolete by 2060.
- thewataccount 3y agoThat's a significant amount of time if we're talking about long-term file storage. I've had my dropbox account for over 10 years now. Being concerned about a timescale of 20 to 30 years seems reasonable for things like long term file storage IMO. Backblaze, dropbox, google drive, onedrive, AWS are all over a decade old.
- ignoramous 3y ago> That's a significant amount of time Depends on the threat model. I mean, WireGuard and Signal rotate derived keys every 2mins!
- denton-scratch 3y ago> I've had my dropbox account for over 10 years now. Being concerned about a timescale of 20 to 30 years seems reasonable for things like long term file storage IMO. But you're relying on your chosen cloud-provider staying around for 30 years. The number of tech companies that have died in the last 30 years easily exceeds the number still standing [citation needed].
- thewataccount 3y ago> But you're relying on your chosen cloud-provider staying around for 30 years. Yes, and I recognize that the company existing, or at least that product existing for that long isn't incredibly likely. But I think the fact that there's 3 products from massive companies like Amazon, Google, Microsoft, and 2 from smaller ones, dropbox/backblaze that lasted 10 years means that at the very minimum ~20 years should be considered as realistically possible. And honestly, if we're willing to assume whatever we're storing isn't worth them storing for longer (let's say against your will) - then you should just rekey it anyway yourself. But I'm lazy, and again we're getting to near 15 years for some of those services now. > The number of tech companies that have died in the last 30 years easily exceeds the number still standing [citation needed]. I don't disagree with your premise that the company/product you pick isn't likely to last for 30 years - however I don't think this specific statistic is the correct one to evaluate this with, given the wide range of tech companies with differing products, markets, financial situations, regulations, the many startups that are effectively designed to be acquired, etc. At the very least, I don't think it's fair to compare Google/Microsoft/AWS to "insert latest crypto based file storage startup" in terms of long-term viability.
- nailer 3y agoIs there a quantum algorithm for cracking ECDSA like Shor's for RSA? I was hoping they'd mention it in the article.
- frutiger 3y agoYes. See https://crypto.stackexchange.com/questions/53425/quantum-algorithm-for-elliptic-curves-private-keys https://crypto.stackexchange.com/questions/53425/quantum-alg....
- bawolff 3y agoI was under the impression that shor's algorithm worked for ecdsa just as well as rsa.
- gary_0 3y agoShor's algorithm can also break elliptic curve encryption: https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography
- mjevans 3y agoPart of the issue as a prospective cryptographic user/consumer is that not only do I not know which algorithm(s) should be used, the most likely library https://github.com/open-quantum-safe/liboqs https://github.com/open-quantum-safe/liboqs also explicitly states that it shouldn't be used in production. Hybrid deployment (E.G. with ECC using a curve like 25519) is a great recommendation and probably obvious, far more so than picking a winner among the available post quantum possibly safe algorithms.
- tptacek 3y agoIt is more or less universally assumed in practice that PQ key agreement algorithms will be paired with classical (RSA/ECC) cryptography. There's not much need to discuss or standardize it; it's a given.
- 3y ago
- gregw2 3y agoIs factoring something that GPU /CUDA parallelism helps with?
- upofadown 3y agoNot for the sort of technology we have today using the best known algorithm. The approach relies on the idea of sieving. Sieving takes a lot of memory. As an example, the most recent 829 bit factoring record used multi GB for each processor during the parallel phase and 1.5 TB for the final matrix reduction phase. Neither phase would really get much out of a bunch of processors attached to just a few GB.
- klabb3 3y agoI’m not a cryptographer, but I can see many more pressing reasons for migrating off RSA before 2030. Is there any reason to pick RSA for greenfield today? RSA, to my knowledge, is vulnerable to side channels and poor parameter choices. Implementation simplicity is an underrated security parameter. The fewer feet you have, the fewer of them you can shoot. The NSA data centers don’t want to waste time on your RSA key anyway, much less your run-of-the-mill Russian black hat groups. What bites us in practice are 0-days of something stupid like heartbleed or rowhammer that can be automated, and takes a long time to patch.
- forgotmypw17 3y agoTop reason to use RSA for me, as with most tech I use, is its longevity. Lindy Effect has been the best predictor of what will still work in five years.
- withinboredom 3y agoThe fact that the sun rose today, has no effect on whether the sun will rise tomorrow.
- Strom 3y agoAnd yet I doubt you would be willing to bet against the sun rising tomorrow. Our understanding is based on imperfect models, sure. That doesn't matter most of the time. It wouldn't matter in this bet. So much of what any lifeform does is based on past experience, even though that experience isn't the direct driver of future effects. Turns out that bets based on experience work really well.
- withinboredom 3y agoOf course I’d bet the sun would rise tomorrow, because if it doesn’t, I’m either dead or money will be worthless… The same applies here, would you bet on a horse that is flagging (RSA won’t work forever)? We have the ability to take in new information, and throw away past information because it is no longer relevant. If you choose to ignore the new information, just because “it’s always been that way”, that doesn’t seem rational.
- bsder 3y agoOne of the other problems about RSA cracking progress is that not a lot of people care anymore. RSA is so slow that a lot of people have switched to Elliptic Curve. That's going to dent progress as the smart people are all working on ECC instead of RSA.
- bawolff 3y agoIts not totally implausible that a factoring breakthrough in ECC could have implications for RSA.
- woodruffw 3y agoCould you say more? ECC's trapdoor function isn't prime factoring; it's a variant of the discrete log problem.
- ori_b 3y agohttps://arxiv.org/abs/quant-ph/0301141 https://arxiv.org/abs/quant-ph/0301141
- woodruffw 3y agoYes, I know that DLP and prime factorization are similar problems. I was trying to understand if the GP's comment was about improvements to prime factorization specifically having implications for DLP (since "factoring breakthrough in ECC" is an unusual phrasing to me.)
- deleted 3y ago[deleted]
- throw0101a 3y agoRecommendations from various organizations can be found at: * https://www.keylength.com https://www.keylength.com Anything recent (≥2016) seems to say 3072 for RSA.
- q845712 3y agoI have no specialist knowledge in this subfield, but after reading the article's arguments that basically if you could sic the entire bitcoin network on 2048 RSA it would take 700+ years, I have to wonder about perverse incentives. Another thing that's missing is the lifetime expectancy, e.g. "for how many years does something encrypted in 2030 need to be unbreakable?" The author doesn't seem to be a big authority, so has little to lose by staking their reputation on "you don't need it to be that good," whereas by the very nature of their authority, anyone in the resource you link is going to be motivated to never be wrong under any circumstances. So if someone with some reputation/authority/power to lose think there's a 0.001% chance that some new incremental improvements will allow for fast-enough breaking of 2048 bit encryption created in 2030 within a window where that would be unacceptable, then they're motivated to guess high. The authority in this case doesn't directly bear the costs of too high of a guess, whereas it could be very bad for, i dunno, some country's government, and by extension the org or people that made that country's standards recommendations, if some classified information became public 15 or 50 years earlier than intended just because it could be decrypted.
- traceddd 3y agoI assume you’re aware, but for clarity: it’s not possible to sic the bitcoin network on anything, even cracking sha256, which it uses internally, due to hard-coded ASICs that incorporate specific quirks of the proof-of-work.
- paulnpace 3y agoIt seemed like the reason to use the Bitcoin network in the discussion was to form what a theoretical nation-state actor might possibly be hiding based on the traits of some thing in the physically-existent universe (instead of discussing things completely in imaginary-land).
- sansseriff 3y agoWe can expect a quantum computer with 20 million noisy qubits to break RSA 2048 [1] I can't speak to coherence time or circuit depth concerns, but qubit counts are doubling roughly every year. Current chips have thousands of qubits, so the exponential scaling implies we'd have 20 million qubits by 2035-2040. edit: And from the paper, the required quantum volume ("megaqubitdays") scales bewteen O(n^3) and O(n^4) with RSA key length. So a few years after breaking RSA 2048, you'd have a computer five times larger that could break RSA 3072. [1] https://quantum-journal.org/papers/q-2021-04-15-433/ https://quantum-journal.org/papers/q-2021-04-15-433/
- tptacek 3y agoMore detail on progress towards quantum factoring of RSA (among other things): https://sam-jaques.appspot.com/quantum_landscape https://sam-jaques.appspot.com/quantum_landscape I'm not super concerned. Cynically: one big driver of research into PQ cryptography is that it's a full employment program for academic cryptographers. Not that there's anything wrong with that! I like a Richelot isogeny as much as the next guy, or I would if I understood what they were.
- mirekrusin 3y ago> Current chips have thousands of qubits, really? I thought we have 70 max?
- cwillu 3y agoI suspect d-wave nonsense was involved in the confusion.
- MattPalmer1086 3y agoIBM released a processor with 433 qubits last year, and they say they are on track to deliver a 1121 qubit processor this year. https://www.ibm.com/quantum/roadmap https://www.ibm.com/quantum/roadmap
- mirekrusin 3y ago
- thomashabets2 3y agoI use gpg plus kyber (quantum resistant). RSA may break, and kyber might suck. But I'm hoping not both. https://github.com/ThomasHabets/kybertest https://github.com/ThomasHabets/kybertest
- mmaunder 3y agoThat AI will accelerate algorithmic improvements is a new factor that has not previously been taken into account. This may be too optimistic.
- Conscat 3y agoThere's practically no reason to think that AI will greatly accelerate the development of new algorithms.
- zone411 3y agoWhy? Because we're nearing the theoretical limits or because AI will be too dumb to help or for other reasons?
- I_am_uncreative 3y agoFor the same reason that there's no reason to think AI will continue to advance exponentially. The idea of the singularity is fun, but it's unrealistic. Nothing lasts exponentially forever.
- zone411 3y agoEven if the exponential improvements, which have been happening in both hardware and AI algorithms, were to slow down to sub-exponential, this still assumes that exponential advancements are necessary for AI to reach a level where it can assist in algorithm design. And only now we're seeing big jumps in AI investments, which could serve as another source of improvements. You could even argue that we're seeing the first signs of recursive improvements, with Copilot making programmers ~20% more productive.
- jaza 3y agoI have yet to see an AI bot produce anything that's truly intelligent and/or original (all I see is ever more powerful hardware and ever bigger quantities of training data being thrown at essentially the same statistical probability algorithms), and I don't predict that changing in the foreseeable future - at least, not without the same kind of fundamental breakthrough that would be required for quantum computing to become a practical reality.
- Aardwolf 3y agoFor Symmetric encryption, it says: 'Current key size: 112 bits' However the 3 linked examples, AES, ChaCha20 and Camellia all use a key size of at least 128 bits, with 192 or 256 bits also listed as options. What does this current NIST key size recommendation (effective as of 2019) of 112 mean then? Does anyone use this size?
- jbarrs 3y agoI find it amusing that the table published a conservative cutoff year and an optimistic cutoff year. Based on the trends I've seen, most non-critical software would probably have made the switch in time for the conservative year, whereas anything security-critical like a bank would probably use the optimistic year.
- upofadown 3y agoThe author of the paper had a problem. His elliptic curve method seemed like it might overtake the best known algorithm at the time for factoring. So the conservative estimate takes that into account. The elliptic curve method never managed supremacy so the optimistic estimate is actually more relevant. That means that the actual prediction is 2040 but it seems the various national cybersecurity entities might of missed that point.
- smaudet 3y agoOne thing this paper ignores is side channel attacks. Those may involve hardware or software vulnerabilities, or they may be inherent to the process itself. So the real bogeyman is not whether we have figured out how to factor large numbers yet (aside from Shor and the as of now mythical quantum computer), but how much information you might leak by using your key. One (generally) overlooked idea might be, some sort of vulnerability between they key and the data being used. E.g., by multiplying many, many smaller numbers with the private key, is it possible to increase the efficiency of the sieve. Then it might be the case that commonly used keys are more vulnerable and keys used less are less vulnerable. Another idea would be a rainbow table of keys. It might not matter so much that you can arbitrarily factor a large number, if generating keys is fast. Especially when you mount attacks on the random number generators involved, you can reduce the search spaces. Forcing the key itself is not so much the concern, this doesn't make me think "oh we are fine". Historically we only have to look back to e.g. Heartbleed to be reminded that we broke ssl not by factoring primes, but by exploiting the many flaws in the protocol itself.
- capableweb 3y ago> One thing this paper ignores is side channel attacks. I mean, that's fair right? The article doesn't talk about encryption in general but tries to answer "How secure is RSA?" or rather "When is/will N bit RSA be considered insecure?", so scoping it to only talk about that seems fair. Of course, one could only focus their attention on so many things. Misuse, misconfiguration, side channel attacks and etc become unrelated to the topic at hand in this case.
- smaudet 3y agoPossibly? My point was essentially that key-length could have unintended side-effects. E.g. if you were to have some rainbow table approach, e.g. in theory larger key size would mean more possible key combinations, meaning more expensive space complexity, and harder-to-crack keys. Factoring a key is not necessary if you already know the factors, a hashtable has O(log(N)) complexity. If you implement some custom FPGA hardware and a nice database its not too difficult to imagine some specialized operation storing off generated public keys to their corresponding private key pairs, and the power costs are rather low. Of course due to combinatorics the size of this output space is rather large, despite the fact that the distribution of primes shrinks as they grow larger, but the argument is about factoring a single number, not about efficiently computing primes and their common multiples. Counter to the article, it completely obviates the need to hide your power bill, as you can cache every single computation from the past 30+ years... To bring it back to what I was saying, the difficulty of brute-forcing RSA (or other schemes) is potentially irrelevant to the cost of obtaining a solution, and higher bit-length key-pairs offer some hedge against that possibility. It seems pretty relevant to the question "how secure is RSA" to me.
- userbinator 3y agoMy MITM proxy that sits on the LAN and acts as a filtering gateway to the Internet still uses a 1kbit RSA key, only because it's the smallest size my devices will accept. It's somewhat amusing that, despite widespread "knowledge" that 1024-bit RSA is "insecure", this is still roughly 2^100 times more difficult to factor than the current latest record of 829 bits.
- Tempest1981 3y agoNo concern about "store now, decrypt later"? https://en.wikipedia.org/wiki/Harvest_now,_decrypt_later https://en.wikipedia.org/wiki/Harvest_now,_decrypt_later
- I_am_tiberius 3y agoI always thought discussions about encryption forget about this topic. Encrypted data today is only hidden today, not in the future. So any darknet criminal should consider that files he/she sends are being intercepted and readable in 30 years.
- cat_plus_plus 3y agoThis ignores potential current unpublished advances by entities like NSA and potential unforeseen future algorithmic and computing power advances. Logically speaking, larger keys could help and are unlikely to hurt with both. Even if larger key still ends up breakable, adversaries may still go for low hanging fruit. Other than that, it depends on secrecy timeline and cost/performance sensitivity. An average credit card transaction is unlikely to be targeted by NSA or archived in hopes of cracking it 30 years later, and on the other hand volume is very high and latency is important. So use whatever is thought to not be breakable now and upgrade keys if and when technology progresses. On the other hand, list of American spies in Russia would not take more than a few minutes to decrypt even with enormous key sizes and on the other hand disclosure could cause real damage even decades later. Might as well overshoot even if there is no known reason as of yet.
- unnouinceput 3y agoQuote: "There seems to be no rational reason to increase RSA key sizes past 2048 starting in the year 2030. We don't have any reason to increase RSA key sizes at any time based on our current understanding." Yeahhhh, nice try NSA. If they say this, I'd say go to 8192 right now.
- DeathArrow 3y ago> The assumptions that the 2030 date for increasing RSA key length were based on turned out to be invalid. A check of current capability confirms this. There seems to be no rational reason to increase RSA key sizes past 2048 starting in the year 2030. We don't have any reason to increase RSA key sizes at any time based on our current understanding. Great to know my porn collection will be safe with 2048 bit RSA. :)
- paulnpace 3y agoI realize I'm rather far out of my depth here, but when discussing asymmetric encryption, doesn't this typically imply the discussion is about authentication? Is there a way to derive the ephemeral keys? My understanding is that these are not directly shared, but it's exactly where I am weakest on the basic concepts of the handshake and related stuffs.