The advance was incremental at best. So why did so many think it was a breakthrough?
There's little doubt that some of the most important pillars of modern cryptography will tumble spectacularly once quantum computing, now in its infancy, matures sufficiently. Some experts say that could be in the next couple decades. Others say it could take longer. No one knows.
The uncertainty leaves a giant vacuum that can be filled with alarmist pronouncements that the world is close to seeing the downfall of cryptography as we know it. The false pronouncements can take on a life of their own as they're repeated by marketers looking to peddle post-quantum cryptography snake oil and journalists tricked into thinking the findings are real. And a new episode of exaggerated research has been playing out for the past few weeks.
The last time the PQC—short for post-quantum cryptography—hype train gained this much traction was in early 2023, when scientists presented findings that claimed, at long last, to put the quantum-enabled cracking of the widely used RSA encryption scheme within reach. The claims were repeated over and over, just as claims about research released in September have for the past three weeks.
A few weeks after the 2023 paper came to light, a more mundane truth emerged that had escaped the notice of all those claiming the research represented the imminent demise of RSA—the research relied on Schnorr's algorithm (not to be confused with Shor's algorithm). The algorithm, based on 2021 analysis of cryptographer Peter Schnorr, had been widely debunked two years earlier. Specifically, critics said, there was no evidence supporting the authors' claims of Schnorr's algorithm achieving polynomial time, as opposed to the glacial pace of subexponential time achieved with classical algorithms.
Once it became well-known that the validity of the 2023 paper rested solely on Schnorr's algorithm, that research was also debunked.
Three weeks ago, panic erupted again when the South China Morning Post reported that scientists in that country had discovered a "breakthrough" in quantum computing attacks that posed a "real and substantial threat" to "military-grade encryption." The news outlet quoted paper co-author Wang Chao of Shanghai University as saying, "This is the first time that a real quantum computer has posed a real and substantial threat to multiple full-scale SPN [substitution–permutation networks] structured algorithms in use today."
Among the many problems with the article was its failure to link to the paper—reportedly published in September in the Chinese-language academic publication Chinese Journal of Computers—at all. Citing Wang, the paper said that the paper wasn't being published for the time being "due to the sensitivity of the topic." Since then, the South China Morning Post article has been quietly revised to remove the "military-grade encryption" reference.
With no original paper to reference, many news outlets searched the Chinese Journal of Computers for similar research and came up with this paper. It wasn't published in September, as the news article reported, but it was written by the same researchers and referenced the "D-Wave Advantage"—a type of quantum computer sold by Canada-based D-Wave Quantum Systems—in the title.
Some of the follow-on articles bought the misinformation hook, line, and sinker, repeating incorrectly that the fall of RSA was upon us. People got that idea because the May paper claimed to have used a D-Wave system to factor a 50-bit RSA integer. Other publications correctly debunked the claims in the South China Morning Post but mistakenly cited the May paper and noted the inconsistencies between what it claimed and what the news outlet reported.
Over the weekend, someone unearthed the correct paper, which, as it turns out, had been available on the Chinese Journal of Computers website the whole time. Most of the paper is written in Chinese. This abstract was fortunately written in English. It reports using a D-Wave-enabled quantum annealer to find "integral distinguishers up to 9-rounds" in the encryption algorithms known as PRESENT, GIFT-64, and RECTANGLE. All three are symmetric encryption algorithms built on a SPN—short for substitution-permutation network structure.
"This marks the first practical attack on multiple full-scale SPN structure symmetric cipher algorithms using a real quantum computer," the paper states. "Additionally, this is the first instance where quantum computing attacks on multiple SPN structure symmetric cipher algorithms have achieved the performance of the traditional mathematical methods."
The main contribution in the September paper is the process the researchers used to find integral distinguishers in up to nine rounds of the three previously mentioned algorithms.
[...] The paper makes no reference to AES or RSA and never claims to break anything. Instead, it describes a way to use D-Wave-enabled quantum annealing to find the integral distinguisher. Classical attacks have had the optimized capability to find the same integral distinguishers for years. David Jao, a professor specializing in PQC at the University of Waterloo in Canada, likened the research to finding a new lock-picking technique. The end result is the same, but the method is new.
[...] This isn't the first time the South China Morning Post has fueled undue panic about the imminent fall of widely used encryption algorithms. Last year's hype train, mentioned earlier in this article, was touched off by coverage by the same publication that claimed researchers found a factorization method that could break a 2,048-bit RSA key using a quantum system with just 372 qubits. People who follow PQC should be especially wary when seeking news there.
The coverage of the September paper is especially overblown because symmetric encryption, unlike RSA and other asymmetric siblings, is are widely belived to be safe from quantum computing, as long as bit sizes are sufficient. PQC experts are confident that AES-256 will resist all known quantum attacks.
[...] As a reminder, current estimates are that quantum cracking of a single 2048-bit RSA key would require a computer with 20 million qubits running in superposition for about eight hours. For context, quantum computers maxed out at 433 qubits in 2022 and 1,000 qubits last year. (A qubit is a basic unit of quantum computing, analogous to the binary bit in classical computing. Comparisons between qubits in true quantum systems and quantum annealers aren't uniform.) So even when quantum computing matures sufficiently to break vulnerable algorithms, it could take decades or longer before the majority of keys are cracked.
The upshot of this latest episode is that while quantum computing will almost undoubtedly topple many of the most widely used forms of encryption used today, that calamitous event won't happen anytime soon. It's important that industries and researchers move swiftly to devise quantum-resistant algorithms and implement them widely. At the same time, people should take steps not to get steamrolled by the PQC hype train.
More follow up on this story with a good explanation of what was actually achieved.
Related Stories
The cryptographer who blogs under the pseudonym Soatok has written an in depth discussion of the practical limitations of End-to-End Encryption on his blog. For some things, such as planning military strikes, Sensitive Compartmented Information Facility (SCIFs) are the right tool for the job, while smartphone apps of any stripe are not.
In the aftermath of this glorious fuck-up by the Trump administration, I have observed many poorly informed hot takes. Some of these were funny, but others are dangerous: they were trying to promote technologies that claim to be Signal alternatives, as if this whole story was somehow a failure of Signal’s security posture.
Not to put too fine a point on it: Switching to Threema or PGP would not have made a lick of difference. Switching to Matrix would have only helped if you consider “unable to decrypt message” helping.
To understand why, you need a clear understanding of what end-to-end encryption is, what it does, what it protects against, and what it doesn’t protect againt.
His prediction is that the White House will lash out at both The Atlantic and at Signal to distract from the catastrophic procedural failure which the administration demonstrated through this incident. He also observed that adding a journalist to the chat group would provide a good distraction from possibly compromised smartphones, devices which are notoriously insecure even when the stakes are much lower.
Previously:
(2025) Apple Pulls End-to-End Encryption From UK Rather Than Provide Government a Backdoor
(2024) U.S. Officials Urge Americans to Use Encrypted Apps Amid Unprecedented Cyberattack
(2024) Here's the Paper No One Read Before Declaring the Demise of Modern Cryptography
(2024) How I Got a Truly Anonymous Signal Account
... and more.
(Score: 5, Insightful) by JoeMerchant on Friday November 01, @09:08PM (2 children)
When Satoshi's wallet is cashed, I'll start to believe that ECC has been broken.
I don't care how many papers have been published claiming whatever, until there's a live demo for a skeptical audience of currently considered "hard encryption" being broken by a quantum machine, and that demo is reproduced by an independent lab on at least a couple of keys they have created for themselves, it ain't broken.
Yes, this is one case where we should be fixing it while it still ain't broke, but... I don't think we're close.
TFA mentions 50 bit RSA, Google says:
It can take a few hours to factor a 300-bit RSA integer on a personal computer using free software. 512-bit keys can be factored in a few weeks using standard hardware.
I have been using 3072 bit RSA in accordance with NIST guidelines since 2017.
🌻🌻🌻 [google.com]
(Score: 2) by Fnord666 on Saturday November 02, @02:33PM (1 child)
Does bitcoin use ECC? I thought the digital signatures were 2048 bit RSA.
(Score: 3, Informative) by JoeMerchant on Sunday November 03, @11:13PM
Nope, ECC is both more compact key size and less computationally intensive than RSA...
It has been over 5 years since I looked into it, but IIRC Bitcoin uses 256 bit ECC.
🌻🌻🌻 [google.com]
(Score: 4, Insightful) by darkfeline on Saturday November 02, @12:41AM
What's the point of downplaying post quantum cryptography?
The worst case is that we create strong post quantum crypto and don't need it. Crypto needs to be swapped out long before they're broken, especially for devices/systems that may not/cannot be updated frequently. So it makes sense to start building it now just in case we need it 10+ years from now, because we need ideally 5-10 years *before* it's broken before we start replacing everything.
And it's not like post quantum investment is creating huge economic or social interruption, like some other speculative/rushed disaster preparation work.
Join the SDF Public Access UNIX System today!
(Score: 2) by driverless on Saturday November 02, @08:28AM (1 child)
PQC is faith-based. Despite there not only being no evidence of something being able to break current crypto being able to be built, and in fact all the evidence being that it can't [auckland.ac.nz], the PQC zealots are saying we have to repent and abandon our false gods and adopt the new faith of horribly-inefficient, complex, fingers-crossed-it's-secure PQC. So this latest paper is another prophecy of doom that they can wave about, and who cares if it's full of holes. Facts and reason have no place in faith-based arguments.
(Score: 0) by Anonymous Coward on Wednesday November 06, @04:40PM
Despite there not only being no evidence of something being able to break current crypto being able to be built, and in fact all the evidence being that it can't [auckland.ac.nz], the PQC zealots are saying we have to repent and abandon our false gods and adopt the new faith of horribly-inefficient, complex, fingers-crossed-it's-secure PQC.
It's a great presentation. As hinted in the slides, most modern "security" is about selling products and not actually about security. Invent problems, sell solutions. Lots of money to be made.