2048 Bit RSA and the Year 2030
articles.59.ca
articles.59.ca
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.
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.
really? I thought we have 70 max?
The only results I've seen is this [0] from April which is 70 qbit and it's all about fighting with noise.
It looks like overcoming noise is exponentially harder with more qubits and this whole quantum thing may never work for practical problems after all?
So a QC can factor a 5 bit number with Shor's algorithm in 2023 (with some cheating). That record has not changed for 10+ years.
I publicly bet 8 years ago that nobody would factor the number 35 by 2030. I hope I'm proved wrong.
Right now no one knows how to build a scalable quantum computer. But as soon as we find out the equivalent of lithography for building quantum chips, the progress will come, and it will come quickly and suddenly.
Not too different from how we had to use vacuum lamps while we figure out how solid state systems can work... Or spinning hard drives before we figured out SDDs.
Or maybe none of this would work out and the whole field would be a bust... but you know Clarke's laws https://en.wikipedia.org/wiki/Clarke%27s_three_laws
It got slightly faster on the last few years, I don't know if inherently so or just due to random fluctuation. Yet people keep repeating that claim that the growth is exponential, based on no evidence at all.
While it is too early to call it exponential, it is wildly faster than 4 qubits/year. Same can be said about other hardware systems too (trapped ions, neutral atoms, and with some caveats photonics and color centers too).
Besides, it has 2 "real" datapoints, and both are completely different from the sizes everybody else were achieving in well-public and well-reviewed computers.
If you restrict your data to devices other people were allowed to touch, a lot of those huge numbers just disappear.
https://arxiv.org/abs/2009.05045
As far as I can tell, this website suggests that two-qubit gate infidelity has continued to improve exponentially, although it's hard to tell if these are reliable datapoints.
Because there's typically an engineering tension between qubit count and gate quality, what you want to track is something like quantum volume, which looks to be on trend
but it's notable that Google achieved quantum supremacy without having amazing quantum volume numbers, so it's not a perfect metric
https://spectrum.ieee.org/quantum-computing-google-sycamore
Worth noting that once you cross the fault tolerant threshold you will probably see a big shift in how engineering effort is distributed: many researchers think it will be harder to improve gate quality than just increase increase qubit counts to make up for it, so you may see gate quality stall and extrapolation become even less reliable.
If we cross the threshold. Until then, adding a qubit requires halving the noise floor, so the Moore's law equivalent to exponential scaling is basically adding a fixed number of qubits per year.
Are you suggesting that gates surpassing the fault tolerant threshold will never be achieved? The vast majority of experts disagree with this.
Without fault tolerance, you have a hard wall on circuit depth because errors grow exponentially with depth. You can't make up for this by adding any number of qubits. "Halving the noise floor" means...what, improving gate fidelity?
Until then, the best we can do is if you half the noise floor (or double the fidelity) you can add roughly one ideal qubit.
The most obvious reason to suppose the fault tolerance threshold will be crossed is that simple extrapolation of progress predicts it will.
On the other hand I can make a nod in the direction of the decades of expertise any one can build in a chamber of vapor ware with the hope that it will distill into something useful.
As critical as I am, I of course congratulate anyone on taking on such difficult innovation. Nonetheless, there is no physical evidence it will amount to anything thus far. It is purely hypothetical, and the only thing theoretical in justification is the fictitious proof of its use through mathematical modeling which is not physical reality and thus closer to building a virtualized computer in a MMO that mimics Earth saying you get to play as a martian using some weird technology while it runs on classical computing.
All new tech starts as purely hypothetical. (Not to mention concrete milestones like quantum supremacy, gate infidelity trends, etc.)
(Likewise, the earliest "demonstrations" of quantum computing where they factored two-digit numbers were ridiculous for several reasons, not least of which was that you could do it in a microsecond using a classical computer. Then later, when quantum supremacy calculations were done by Google, the mathematical problem chosen was completely useless for any practical application.)
It was not until 2013, 46 years after Braginsky theorized the basic principles, that a squeezed probe was used for something other than a proof-of-concept: measuring gravitational waves at LIGO. This enabled LIGO to detect ultra weak gravitational waves that would otherwise be invisible to it: https://www.nature.com/articles/nphoton.2013.177
Needless to say, it will take even longer before these techniques are used for economically relevant applications.
In terms of computing, we have seen many new paradigms materialize within decades, even centuries, of their conception. Babbage conceived of the Analytical Engine in the 1800s, but we saw programmable computers by the mid-1900s. The transition from electromechanical to electronic computing occurred within a few decades. Every instance of these examples are real physical examples that were able to be used and demonstrated as a physical device providing utility. We can even go back to the early computation devices of the loom or even analog computing calendar/clock systems.
Quantum computing is an ambitious concept, and while I respect the academic rigor that goes into its development, the lack of concrete, physical outcomes, even in a rudimentary sense, after four decades is notable. Theoretical advancements are important, but the inability to materialize them in some substantial form, especially when juxtaposed against the timeline of prior computing paradigms, can warrant skepticism.
Don't get me wrong, I value innovation and the pursuit of new technological frontiers, but I also believe in questioning, and when the physical evidence is wanting, I'll voice my concerns. This is not to discredit the work being done but rather to keep the discussion grounded and accountable.
For a "real physical quantum computer" to exist by this definition, it should be able to carry out such operations using quantum phenomena, without any reliance on classical computing architecture for function, error correction, or result verification.
What we currently have in the field of quantum computing doesn't fit this bill. The quantum systems we have today are not independent "computers" but rather more like "classical computers conducting quantum experiments." They're akin to people playing an MMO and running an imaginary computational architecture that only exists within the confines of the game rules. In this sense, they're creating and operating within an entirely simulated environment.
This isn't to diminish the value of the research being conducted or the strides that are being made. But I would argue that the statement "real physical quantum computers exist" is, at this stage, a significant overreach. We may have precursors or tools that can manipulate quantum phenomena in interesting ways, but we're still a considerable distance from having an operational, standalone quantum computer in the full sense of the term.
Nope, wrong. Plans for quantum computers have always included assistance from classical computers. This is like saying for a nuclear weapon to exist, it must have no conventional explosives, but in fact all nuclear weapons contain conventional explosives to initiate the nuclear reactions.
You've made a number of incorrect claims here without admitting error, so I won't continue the conversation.
You could, but the premise is wildly false; tenured professors can get fired for cause (and tend to have some process protections alongside that), and tenured professors aren’t the only workers with contracts or legal protection that restrict firing to “for cause” (pretty much all high level employees with individual contracts like—but not limited to—executives have that, maybe with a high-priced buyout option, though without or with limited process protections), and most unionized workers and most (even if not unionized) public workers have both limitations to firing (or other adverse actions) for-cause and strong due process protections.
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.
Depends on the threat model. I mean, WireGuard and Signal rotate derived keys every 2mins!
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].
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.
Hypothetically if you are a journalist working with communications from a source in an authoritarian country (or a country that could become authoritarian in the next 4 decades; and name one that couldn’t, right?) it would be no good if you got some elderly person killed in the future.
Or just like bank account details I guess?
And we’re talking about thousands of bits, we spend way more than that on stupid things like making UI slightly prettier. I’m streaming music at, I guess, ~200kbps, why not spend a couple seconds worth of music on keys? (Who knows, maybe it will protect some famous journalist somehow and we’ll end up ahead when it spares us a whole moment of silence).
Edit: TBH I’m not really sure this is a useful way to look at things, but the music bandwidth/moment of silence parallel was too convenient to pass up.
The point of cryptography isn't to keep secrets forever, it's to keep secrets for long enough that by the time those secrets are revealed, they are worthless.
Whilst this has historically been true, it's very plausible that AES-256 means that (for this limited problem, symmetric encryption) we're done.
The "obvious" attack (some type of brute force) on AES-256, even assuming you have a quantum computer (which we don't) and it's actually more affordable than our current computers (which it won't be) is not practical in our universe.
But if you only want any given secret to stay save for 20 years, you can still use 4096 bit RSA for another 17 years. Which sounds like a good tradeoff: enough of time for better algorithms to get established, but little risk of a breach you will care about.
RSA is also not typically described as robust, for those reasons.
Do NOT switch to ECC if your threat model includes a quantum computer arriving.
Either use larger RSA keys or more appropriately a hybrid signature scheme combining one of NIST's PQC signatures and a traditional algorithm.
https://csrc.nist.gov/Projects/post-quantum-cryptography/sel...
https://web.archive.org/web/20230710195916/https://articles....
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.
> 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.
By costs nothing I mean as CPUs get faster there is less performance impact on lenghtening keys
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
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.
Would love to be proven wrong though if my understanding is incorrect and there's actually a feasible path towards quantum computing at scale.
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.
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?
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.
Lindy Effect has been the best predictor of what will still work in five years.
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.
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.
I've been to places where the sun doesn't rise for months on end...
> So it might be just RSA and discrete logs today but a requirement for pointlessly long EC keys will be along soon.
It wouldn’t be pointless if computers can crack those sizes. It’d only be pointless if cryptanalysis can exploit structure to reduce the effective entropy, no?
https://www.ams.org/notices/199612/pomerance.pdf has a great writeup on the history of the work around this. Essentially when you see improvements in complexity of the form
Old best: Quadratic Sieve: exp(c(log n)^1/2(log log n)^1/2)
New best: General Number field sieve: exp(c(log n)^1/3(log log n)^2/3)
I can't help but feel that's an exponent there that we've moved to 1/3 that could be moved further. Sure we don't know how and we've been stuck here on the current best for just over 25 years but i just feel that if you give me two methods and one moves a term like that there's a good chance there's a way to reduce that term further. It'd be weird for that complexity statement to stay as is. That's telling me "the universe doesn't allow factorization any faster than a term that's raised to a power of 1/3rd" and i'm asking "why is 1/3 so special?". So i'm not convinced that there's not more here. I don't have a clue how of course. But the history of RSA going "256bits is secure" to 512bits to 1024bits to 2048bits being needed has me worried about the safety of prime factorization.
Sure, if we were implementing cryptographic algorithms from scratch that would be a proper strong consideration. However, 99% of programmers should just link to an established library/framework and use its cryptographic implementation. These established libraries already paid the price of implementation, and are very battle-tested. There's therefore very good reason to believe their RSA implementation is secure.
Choosing an algorithm should be done on other considerations then. A lower keysize would point to ECC. But maybe we don't want a single algorithm for all encryption - a mixed global ecosystem with RSA and ECC projects would be more robust.
Yes absolutely. I’m not saying users should pick the one that’s easier to implement.
Simplicity is good for implementers. It allows for more participants, eg std libs to provide their own. Also, even the security geeks are humans and make mistakes. Heartbleed is a perfect example of where even simple things can go catastrophically wrong.
As a second order effect, users benefit from simplicity in the long run, because less complex systems have fewer bugs, and thus fewer security bugs.
Many of these established libraries have fallen in battle, some several times. There's always a new up and coming library that works on platform X, in language Y, or has a better license Z, or is integrated into an init system, and while some of them learn from the experience of others, many learn by making the same mistakes others did.
Pushing towards simpler constructions gives hope that those new implementations make fewer mistakes.
* The only type of person who should be writing a cryptographic implementation in the first place.
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?
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.
Anything recent (≥2016) seems to say 3072 for RSA.
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.
in the space of cve or malware detection, the user wants a safe/secure computing experience with minimal overhead, but the antivirus / cve-scan vendor wants to claim that they're _keeping_ the you safe. so they're motivated to tell you all about the things they scanned and possible attacks / vectors they found. You probably would've been safe responding to only a subset of those alerts, but they have no incentive to minimize the things they show you, because if they ever missed one you would change vendors.
in the space of cryptography, the user wants secure communications that are unbreakable but with minimum hassle and overhead, but the advisory boards etc. are incentivized to act like they have important advice to give. So from the user perspective maybe it makes sense to use 2048 bit encryption for a few more decades, but from the "talking head" authority figure perspective, they can't afford to ever be wrong and it's good if they have something new to recommend every so often, so the easiest for them to do is to keep upping the number of bits used to encrypt, even if there's 99.99% odds that a smaller/shorter/simpler encryption would've been equally as secure.
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.
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.
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.
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.
Great to know my porn collection will be safe with 2048 bit RSA. :)
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.
The idea of the singularity is fun, but it's unrealistic. Nothing lasts exponentially forever.
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.
Later
(Leaving this comment here in perpetuity as evidence that I didn't think about your question as hard as David Adrian did. The message still holds, and that message is: "big ol' shrug".)
Think of Tunneling or layers or nesting dolls. The order doesn't particularly matter from a security perspective. Though today I'd wrap with the conventional algorithm on the OUTSIDE layer, since it takes less computational time to check / validate. The inner layer would then be one or more of the post-quantum algorithms; a particularly paranoid application might use more than one if something absolutely must remain a secret.
So you’re encrypting with an asymmetric post quantum algorithm then using that as a payload with regular ED25519 or similar?
What value does the pre quantum wrapper add?
Post-quantum algorithms are, as yet, young and very possibly poorly understood. They may even offer no security at all (due to presently unseen flaws); therefore as a hedge against that include at least another currently in use and current best practice algorithm so that at least _that_ level of security is retained.
Plus, as I pointed out several replies ago, if the current (and fast since reasonable key size Elliptic Curve based) algorithm is the outer layer it can be validated quickly which is a better guard against denial of service attacks and other poor fakes.
Edit: reference https://mailarchive.ietf.org/arch/msg/spasm/McksDhejGgJJ6xG6...
Unless there is an unexpected leap in the viability of quantum cryptanalysis, you should expect that all commercial/standard cryptography with PQ capabilities will run in a hybrid configuration.
I'm only commenting here because there's a pervasive belief that this is controversial in cryptography engineering circles, or that NIST is trying somehow to prevent hybrid schemes from happening, which is simply not the case --- though they may not bother to standardize any particular mechanism of combining ECC/RSA with PQ exchanges (but: they don't standardize stuff like TLS ciphersuites, either).
A conservative but reasonable risk assumption is to act as if all internet traffic prior to the year 2023 was transmitted in the clear. This includes Signal, PGP, and Tor.
Yeahhhh, nice try NSA. If they say this, I'd say go to 8192 right now.