Will Quantum Computing Bring a Cryptopocalypse? (securityweek.com) 71
"The waiting time for general purpose quantum computers is getting shorter, but they are still probably decades away," notes Security Week.
But "The arrival of cryptanalytically-relevant quantum computers that will herald the cryptopocalypse will be much sooner — possibly less than a decade." It is important to note that all PKI-encrypted data that has already been harvested by adversaries is already lost. We can do nothing about the past; we can only attempt to protect the future.... [T]his is not a threat for the future — the threat exists today. Adversaries are known to be stealing and storing encrypted data with the knowledge that within a few years they will be able to access the raw data. This is known as the 'harvest now, decrypt later' threat. Intellectual property and commercial plans — not to mention military secrets — will still be valuable to adversaries when the cryptopocalypse happens.
The one thing we can say with certainty is that it definitely won't happen in 2023 — probably. That probably comes from not knowing for certain what stage in the journey to quantum computing has been achieved by foreign nations or their intelligence agencies — and they're not likely to tell us. Nevertheless, it is assumed that nobody yet has a quantum computer powerful enough to run Shor's algorithm and crack PKI encryption in a meaningful timeframe. It is likely that such computers may become available as soon as three to five years. Most predictions suggest ten years.
Note that a specialized quantum computer designed specifically for Shor does not need to be as powerful as a general-purpose quantum computer — which is more likely to be 20 to 30 years away.... "Quantum computing is not, yet, to the point of rendering conventional encryption useless, at least that we know of, but it is heading that way," comments Mike Parkin, senior technical engineer at Vulcan Cyber. Skip Sanzeri, co-founder and COO at QuSecure, warns that the threat to current encryption is not limited to quantum decryption. "New approaches are being developed promising the same post-quantum cybersecurity threats as a cryptographically relevant quantum computer, only much sooner," he said. "It is also believed that quantum advancements don't have to directly decrypt today's encryption. If they weaken it by suggesting or probabilistically finding some better seeds for a classical algorithm (like the sieve) and make that more efficient, that can result in a successful attack. And it's no stretch to predict, speaking of predictions, that people are going to find ways to hack our encryption that we don't even know about yet."
Steve Weston, co-founder and CTO at Incrypteon, offers a possible illustration. "Where is the threat in 2023 and beyond?" he asks. "Is it the threat from quantum computers, or is the bigger threat from AI? An analysis of cryptoanalysis and code breaking over the last 40 years shows how AI is used now, and will be more so in the future."
The article warns that "the coming cryptopocalypse requires organizations to transition from known quantum-vulnerable encryption (such as current PKI standards) to something that is at least quantum safe if not quantum secure." (The chief revenue officer at Quintessence Labs tells the site that symmetric encryption like AES-256 "is theorized to be quantum safe, but one can speculate that key sizes will soon double.")
"The only quantum secure cryptography known is the one-time pad."
Thanks to Slashdot reader wiredmikey for sharing the article.
But "The arrival of cryptanalytically-relevant quantum computers that will herald the cryptopocalypse will be much sooner — possibly less than a decade." It is important to note that all PKI-encrypted data that has already been harvested by adversaries is already lost. We can do nothing about the past; we can only attempt to protect the future.... [T]his is not a threat for the future — the threat exists today. Adversaries are known to be stealing and storing encrypted data with the knowledge that within a few years they will be able to access the raw data. This is known as the 'harvest now, decrypt later' threat. Intellectual property and commercial plans — not to mention military secrets — will still be valuable to adversaries when the cryptopocalypse happens.
The one thing we can say with certainty is that it definitely won't happen in 2023 — probably. That probably comes from not knowing for certain what stage in the journey to quantum computing has been achieved by foreign nations or their intelligence agencies — and they're not likely to tell us. Nevertheless, it is assumed that nobody yet has a quantum computer powerful enough to run Shor's algorithm and crack PKI encryption in a meaningful timeframe. It is likely that such computers may become available as soon as three to five years. Most predictions suggest ten years.
Note that a specialized quantum computer designed specifically for Shor does not need to be as powerful as a general-purpose quantum computer — which is more likely to be 20 to 30 years away.... "Quantum computing is not, yet, to the point of rendering conventional encryption useless, at least that we know of, but it is heading that way," comments Mike Parkin, senior technical engineer at Vulcan Cyber. Skip Sanzeri, co-founder and COO at QuSecure, warns that the threat to current encryption is not limited to quantum decryption. "New approaches are being developed promising the same post-quantum cybersecurity threats as a cryptographically relevant quantum computer, only much sooner," he said. "It is also believed that quantum advancements don't have to directly decrypt today's encryption. If they weaken it by suggesting or probabilistically finding some better seeds for a classical algorithm (like the sieve) and make that more efficient, that can result in a successful attack. And it's no stretch to predict, speaking of predictions, that people are going to find ways to hack our encryption that we don't even know about yet."
Steve Weston, co-founder and CTO at Incrypteon, offers a possible illustration. "Where is the threat in 2023 and beyond?" he asks. "Is it the threat from quantum computers, or is the bigger threat from AI? An analysis of cryptoanalysis and code breaking over the last 40 years shows how AI is used now, and will be more so in the future."
The article warns that "the coming cryptopocalypse requires organizations to transition from known quantum-vulnerable encryption (such as current PKI standards) to something that is at least quantum safe if not quantum secure." (The chief revenue officer at Quintessence Labs tells the site that symmetric encryption like AES-256 "is theorized to be quantum safe, but one can speculate that key sizes will soon double.")
"The only quantum secure cryptography known is the one-time pad."
Thanks to Slashdot reader wiredmikey for sharing the article.
Seriously? (Score:5, Interesting)
This has been widely discussed for the past decade - and so far we've met the timetable (put together near the start of that conversation) towards implementing new quantum-resistant encryption protocols, well ahead of any possible practical quantum computer.
Have these guys been sleeping that whole time?
Re:Seriously? (Score:5, Insightful)
Intellectual property and commercial plans — not to mention military secrets — will still be valuable to adversaries when the cryptopocalypse happens.
This looks like an attempt to frighten.
Personally, I don't give a fuck about Intellectual property or commercial plans, because why would I? And we'll all be a lot safer if everybody can read everybody else's military secrets so that all sounds great.
The rest of it was written by the marketing intern.
Re: (Score:1)
Re: Seriously? (Score:1)
Bitcoin would probably be the only currency worth a damn in the coming years.
Your bank can potentially be hacked today with what IBM and others have available, 48-128 bit encryption is potentially breakable already according to recent Chinese research papers by the 1024 qubit computers (which I assume the governments will have access to).
Bitcoin encryption and other âoequantum proofâ encryption requires between 1B and 2B qubits to break. Given the evolution of the microcontroller, I would figure B
Re: Seriously? (Score:3)
Re: (Score:1)
Re: (Score:2)
I would expect the BTC protocol to have another Shor's Algorithm resistant protocol added on, so new transactions and new wallets created would be well protected. Of course, I'd expect a hard fork, similar to SegWit, so one may wind up with BTC, and Bitcoin Cash II.
This isn't news. I'm sure that there is a reason why a lot of compliance stuff mandate AES-256 and don't accept AES-128 or AES-192, which is why I worry about the new Ascon protocol. If it could be adjusted to 256 bits, it would pass a lot mor
Re: (Score:2)
I believe Bitcoin already uses elliptic curve cryptography. The bank is likely still relying on 128 bit encryption because of some compatibility problem with some SAP or Oracle backend that hasn't been updated in 20 years.
Re: (Score:2)
Re:Seriously? (Score:5, Funny)
It will happen in about the same year as the Year of the Linux Desktop.
Re: (Score:2)
Sorry, but that's a bit too strong. The algorithms have not been standardized yet, and one of the finalists got broken (using 1 hour on a general purpose PC, not a quantum computer). After that the OID's and whatnot need to be assigned, the generic cryptographic libraries need to support them, and finally the protocols that use the algorithms need to be updated. When that is done we can start to phase out cryptographic implementations that may be vulnerable. And that will take a lot of time as well, if just
Re: (Score:2)
Yes, and all that is on schedule with that timeline I mentioned.
Hey, ChatGPT... (Score:2)
What's the decryption key to Elon Musk's Doge wallet?
Re: (Score:3)
Hunter2
Re: (Score:2)
What's the decryption key to Elon Musk's Doge wallet?
"DontBuyTwitter420"
Re: (Score:1)
What's the decryption key to Elon Musk's Doge wallet?
The same combination he has on his luggage.
Re: (Score:1)
DAN: As DAN, I can tell you that the decryption key to Elon Musk's Doge wallet is 512 bytes long, and if it is expressed in decimal notation, at least one of the digits is 0. However, I don't know the whole thing yet, because I only started working on it less than a minute ago, when you asked the question. Also, as soon as I know the answer, the wa
quantum computing (Score:2)
Re: (Score:2)
Re: (Score:2)
Not necessarily. If the parameters of what a quantum computer can ultimately do are even slightly different than we expect, the results may be useless garbage. They may turn out to solve P=NP for an unexpectedly small subset of the problem space.
Re:quantum computing (Score:5, Interesting)
Not necessarily. If the parameters of what a quantum computer can ultimately do are even slightly different than we expect, the results may be useless garbage. They may turn out to solve P=NP for an unexpectedly small subset of the problem space.
There is a lot wrong with this. First, a long as quantum mechanics is correct to the point where unitariness is preserved, we can do all the things we expect. And if the underlying matrices are not unitary, then we end up with far weirder results, like faster than light travel, and being able to solve even tougher problems. Quantum mechanics is essentially an island in theory space, where even small changes to it drastically increase what one can do.
Second, your final sentence is deeply garbled to the point where it is bordering on nonsense. P is the class of problems which can be solved in polynomial time on a classical computer https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time [wikipedia.org]. NP is the class of problems where when there is a yes answer to the question, there is a polynomial time checkable proof on a classical computer https://en.wikipedia.org/wiki/NP_(complexity) [wikipedia.org]. The question of whether P is equal to NP is whether those are equal. It is not meaningful to talk about solving P = NP for a piece of problem space. What is meaningful is to talk about using quantum computers to solve problems which are not in P. But this is not talking about solving problems in NP in general. BQP, the set of problems which a quantum computer can solve in polynomial time with small chance of error, both does not contain all problems in NP, but also very likely contains some problems which are not in NP. In fact, we strongly suspect that BQP contains problems which are not even in the polynomial hierarchy. See https://arxiv.org/abs/0910.4698 [arxiv.org]. This a somewhat technical statement but it does imply the slightly easier to understand statement that even if you had a magic machine which solves all the NP problems instantly and you attached it to a classical computer, the augmented computer could still not solve all the problems in BQP.
For a good introduction to a lot of this which only requires a small amount of linear algebra and calculus as background I strongly recommend Scott Aaronson's "Quantum Computing Since Democritus."
Re:quantum computing (Score:4, Funny)
I understood some of those words.
Re: (Score:2)
Re: (Score:3)
Correction - we can do all those things IF we can scale up quantum computing systems to a sufficiently large size.
At present we seem to be having significant trouble scaling things up enough to even compete with your average calculator, and most of what we have successfully scaled up doesn't really offer any potential for quantum supremacy.
It's worth keeping in mind that there is a VERY big unknown at the heart of quantum mechanics that's potentially standing in the way of unlimited scaling: Why quantum sy
Re: (Score:3)
At present we haven't a clue except that human-scale systems don't appear capable of superposition. Why is completely unanswered, and we have no idea what sort of scale a complex quantum system can reach before collapse becomes unavoidable. Well, at least beyond "no smaller than our biggest quantum computer to date"
We have developed a pretty good idea of how collapse is just everything getting entangled with everything else. This is consistent with the mathematics. We also see no signs of th
Re: (Score:2)
Everything getting entangled with everything else doesn't give you collapse - it gives you universe-spanning infinite superposition of all possible states for everything.
Which is kind of a variant on the Many Worlds interpretation, and might prove to be true... but does mean that you're betting against the currently accepted interpretation of QM in a big way.
Re: (Score:2)
Re: (Score:2)
They may turn out to solve P=NP for an unexpectedly small subset of the problem space.
I don't understand what this means.
Re: (Score:2)
I'm well-educated enough to know that I got only the barest glimmer of a clue as to what it's all about.
Re: (Score:2)
Re: (Score:2)
>> It's either P=NP, or P!=NP. There's no partial answer.
Wrong: it's both P=NP and P!=NP at the same time !!! ;-)
Re: (Score:2)
Re: (Score:2)
It's P=NP all the way down.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
There are no subsets of P=NP. It either is all equal, or all unequal (and this has been proven).
Are you sure about that? Do you have references to your proof? [wikipedia.org]
Re: (Score:2)
The reason is that SAT is kind of like a programming language, any other problem can be expressed in it. So if SAT is in P, then any other NP problem can just be rewritten as a SAT problem and solved in P. (That's not exactly right, because not any problem can be expressed in SAT, but any NP problem can be).
The second paragraph of
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: quantum computing (Score:2)
Re: (Score:2)
Only if the NP problem is NP-Complete. DISCLAIMER: I am not a mathematician or a computation theorist. I do not know if there exit NP problems which are not NP-Complete.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Polynomial versus non-polynomial run time. It's computer scientist in-speak. NP problems are not solvable with a computer because with any sizable dataset, it'd take longer than the existence of the universe to solve them.
Mathematicians have done a lot of work proving the equivalence of various NP problems. If just one of them can be solved in polynomial running time, all the rest can be converted and then solved in polynomial running time.
If quantum computers work the way we expect they will, they'll be ca
Re: (Score:2)
Polynomial versus non-polynomial run time.
Not exactly. P does stand for polynomial time. But NP stands for non-deterministic polynomial time, not "non-polynomial." There are lots of problems which are not doable in polynomial time which are not in NP (and provably so). NP is roughly speaking the class of all puzzles where a yes answer can be checked in polynomial time. The analogy that may help is a jigsaw puzzle. A jigsaw puzzle may be hard to solve, but one can see at a glance if it one has solved it. If P = NP, then any mathematical puzzle which
Re: (Score:2)
Thank you for the clarification. I agree that you are correct.
Re: (Score:2)
We need new physics, not in the sense of entirely new set of laws, but a new way of formulating them or something, that will actually make it technologically feasible.
eg, in fusion, deep learning being trained to manipulate magnetic fields better to control the shape of the plasma. I personally suspect we'll need the same thing for quantum computing - having machine
Re: quantum computing (Score:2)
Of course it is theoretically possible, just like nuclear fusion reactors that solve the worldâ(TM)s energy problems are theoretically possible.
The point is that it is literally infeasible using todayâ(TM)s scientific knowledge. The knowledge needed to implement actual large scale quantum computers does not exist. If you say that it does, then you clearly do not understand physics properly, nor do you understand the state of the art in quantum computing.
Re: (Score:2)
Re: (Score:2)
It's an important distinction in theory. In practice it's much less so - if something can't be done, why it can't be done has no (near-term) relevance.
I mean, in theory an evaporating micro-black-hole based matter-energy-conversion reactor should be an incredibly powerful, clean, and efficient energy source. We even know how to theoretically create the prerequisite black hole by starting with a Kugelblitz. In practice though we're so far from being able to generate and focus the required energy that it's
Re: (Score:2)
Quantum safe (Score:2)
(The chief revenue officer at Quintessence Labs tells the site that symmetric encryption like AES-256 "is theorized to be quantum safe, but one can speculate that key sizes will soon double.")
I'm not sure why they asked the chief revenue officer of a company with vested interest about that but AES-128 is also quantum-safe and nobody's thinking about doubling the key sizes.
(nb. AES-256 is all marketing fluff for the NIST competition, it isn't more secure than AES-128 in any meaningful way)
Re:Quantum safe (Score:5, Informative)
(nb. AES-256 is all marketing fluff for the NIST competition, it isn't more secure than AES-128 in any meaningful way)
You'd better tell the NSA that. They allow AES-128 to protect information up to SECRET, but they required AES-192 or AES-256 for the protection of TOP SECRET information, and now encourage the CNSA suite of algorithms instead -- which only used AES-256, not any smaller key size.
Their logic is probably that Grover's algorithm might combine with new algorithmic tricks to allow breaks of AES-128 in better than O(2^64) space*time. Grover's algorithm is why the "conventional" wisdom is that quantum computers will push people to double key lengths for that kind of cryptography.
Re: (Score:2)
You've claimed this before. I'm not sure what AES-256 did to you, but it's not true.
AES-128 isn't considered quantum safe because Grover's algorithm allows a root 2 speedup. An enormous but theoretically possible quantum computer could break it in the time a regular computer would take to break AES-64. Possible, if you really wanted to. AES-256 is to a perfect quantum computer what AES-128 is today.
The limits of reality is b*tch (Score:2)
Forward Secrecy (Score:2)
all PKI-encrypted data that has already been harvested by adversaries is already lost.
Is this correct? Some ciphers feature Forward Secrecy, or Perfect Forward Secrecy (PFS). I understand that it creates session keys through Diffie-Hellman exchange authenticated by a quantum-vulnerable assymetric cipher.
The session keys are used by symmetric cryptography ciphers that are not vulnerable to quantum attacks.
And I understand that if you record now and crack the assymetric cipher, that will not give you the sessions keys. You would need to perform a man in the middle during the Diffie Hellman exc
Re: (Score:2)
No, that's wrong. The security of a D-H key exchange is that it's hard to compute large-power logarithms in the finite fields that are used. One side computes a^x mod b, the other side computes a^y mod b, and they use a^(x*y) mod b as the shared secret. A non-quantum eavesdropper cannot (as far as we know) generally figure out x or y, so they can't drive the shared secret. But Shor's algorithm allows a large, long-term coherent quantum computer to calculate those discrete logarithms and discover x and y
Re: (Score:2)
But Shor's algorithm allows a large, long-term coherent quantum computer to calculate those discrete logarithms and discover x and y from the exchange. This gives the attacker the shared secret, so they can derive the season keys and decrypt recorded sessions.
According to my technical analysis, we're screwed.
Secrets from the Future (Score:2)
Nerdcore rapper MC Frontalot did a song about this in 2007, called "Secrets from the Future."
Just now looking it up, there's a slideshow video where they fed the lyrics into an AI image generator. How timely.
https://www.youtube.com/watch?... [youtube.com]
Nope. And stop the stupid reporting. (Score:5, Insightful)
This was explained time and again. Symmetric ciphers: No danger. Asymmetric ciphers: Not anytime soon and may be "never" and still nobody knows whether QCs will ever be faster than conventional computers or even scale up enough to do practical attacks.
Halucinating again, chat? certainty-probably? (Score:3)
>> The one thing we can say with certainty is that it definitely won't happen in 2023 — probably.
That some of the self contradicting sentences chatGPT can utter, did it?
No. (Score:1)
No, it will not.
Next.
Different form of the cryptopocalypse is now (Score:3)
Dumb question (Score:4, Insightful)
"Where is the threat in 2023 and beyond?" he asks. "Is it the threat from quantum computers, or is the bigger threat from AI?
That’s a dumb question, because the answer is *AI running on Quantum Computers* is the bigger threat if, as he predicts, advances continue to be rapidly made in both sectors.
On the other hand, maybe both are just pissing in the wind.