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.
All aboard the PQC hype train
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.”
Defining your terms
There’s a lot going on here, but what does it mean? To explain, here's a quick explanation of several important terms.
SPN: Short for substitution-permutation network, an SPN is a series of mathematical operations used in block cipher algorithms to increase their security. These algorithms take a block of plaintext and the encryption key as input and run them through a subprocess that repeats for a set number of rounds before outputting a finished ciphertext.
The best known block cipher is AES, short for Advanced Encryption Standard. Ciphertext produced with 128-bit, 192-bit, and 256-bit AES go through 10 rounds, 12 rounds, and 14 rounds respectively. Page 5 of this animation tutorial provides a useful visualization of this process.
Quantum annealing: This term is borrowed from annealing, a process that uses heat to alter the physical or chemical properties of a metal, glass, or plastic film to increase ductility and reduce hardness. Annealing works by heating materials above their recrystallization temperature, maintaining a certain temperature for a set amount of time, and then allowing them to cool slowly.
The “annealing” in quantum annealing is used metaphorically to describe a method for applying the principles of quantum mechanics to solve complex optimization problems. More on quantum annealing here and here.
In 2011, D-Wave produced the first commercial quantum annealer. Called the D-Wave One, it used a 128-qubit processor chipset. The D-Wave Advantage, the system used in the September research paper, has 5,000 qubits. D-Wave systems can solve only certain types of optimization problems, and the difficulty requires developers and scientists using D-Wave systems to break larger problems into smaller optimization problems before they can be solved with these systems.
PRESENT, GIFT64, and RECTANGLE: All three are lightweight block ciphers designed for use in “constrained” environments, such as those in embedded systems that require more speed and fewer computational resources than is possible using AES. All three are based on an SPN structure and are proposed academic designs. The related GIFT-128 is a component of GIFT-COFB, which was a finalist for the recent NIST lightweight crypto competition but lost out to an algorithm known as Ascon.
PRESENT, meanwhile, can be found in the ISO/IEC 29167-11:2014 and ISO/IEC 29192-2:2019, but it isn't used widely. It's not clear if RECTANGLE is used at all. Because all three algorithms were academic designs, they have been widely analyzed.
Integral distinguishers: In essence, finding integral distinguishers is a type of large-scale optimization problem that, when solved, provides a powerful tool for breaking encryption schemes used in block ciphers. A 2018 paper titled Finding Integral Distinguishers with Ease reported using classical computing to find integral distinguishers for dozens of algorithms. The research included 9-round distinguishers for PRESENT, GIFT64, and RECTANGLE, the algorithms studied in the September paper.
Mixed-integer linear programming: Typically abbreviated as MILP, mixed-integer linear programming is a mathematical modeling technique for solving complex problems. MILP allows some variables to be non-integers, a property that gives it flexibility, efficiency, and optimization over other methods.
The experts weigh in
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. According to a roughly translated version of the paper (the correct one, not the one from May), the researchers wrote:
Inspired by traditional cryptanalysis methods, we proposed a novel computational architecture for symmetric cryptanalysis: Quantum Annealing-Classical Mixed Cryptanalysis (QuCMC), which combines the quantum annealing algorithm with traditional mathematical methods. Utilizing this architecture, we initially applied the division property to describe the propagation rules of the linear and nonlinear layers in SPN structure symmetric cipher algorithms.
Subsequently, the SPN structure distinguisher search problems were transformed into Mixed Integer Linear Programming (MILP) problems. These MILP models were further converted into D-Wave Constrained Quadratic Models (CQM), leveraging the quantum tunneling effect induced by quantum fluctuations to escape local minima solutions and achieve an optimal solution corresponding to the integral distinguisher for the cipher algorithms being attacked. Experiments conducted using the D-Wave Advantage quantum computer have successfully executed attacks on three representative SPN structure algorithms: PRESENT, GIFT-64, and RECTANGLE, and successfully searched integral distinguishers up to 9-round. Experimental results demonstrate that the quantum annealing algorithm surpasses traditional heuristic-based global optimization algorithms, such as simulated annealing, in its ability to escape local minima and in solution time. This marks the first practical attack on multiple full-scale SPN structure symmetric cipher algorithms using a real quantum computer.
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 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. He explained:
The paper is written for an audience of researchers, not for the general public. Researchers view "developing a better lockpick" as an actual attack, but if you're writing for the general public, the general public would think that an attack means "using the lockpick to pick the lock" which is not what happened here.
To continue the analogy, it's true that this paper uses quantum computers to develop lockpicks that match previously known lockpicks in efficiency. So it is true that they have "achieved the performance" of traditional methods, although note that they have not gone beyond that. In some cases (such as RECTANGLE), it is known that no better integral distinguishers exist, so matching the existing technology is the best that can be done using this approach.
Nadia Heninger, a professor studying cryptography at the University of California San Diego, agreed.
“I'd say it's more accurate to say that the researchers formulated a cryptanalysis problem as an optimization problem and ran it on simulated annealing and on quantum annealing and claim to have gotten comparable results. But the main result is to have ‘achieved the performance of traditional mathematical methods,’ so it sounds like maybe there are other classical/mathematical approaches that are better.”
Lastly, Xavier Bonnetain, a professor at the National Institute for Research in Digital Science and Technology in France, put it this way:
They claimed they reduced the search for what is called an integral distinguisher to a Mixed-Integer Linear Programming problem (something that's been standard for years in cryptography) and solved the problem for 3 block ciphers using their quantum annealer.
They did not find anything new, which is not especially surprising given that integral distinguishers on these ciphers were already looked for classically and were already proven optimal. They solved a problem for which we already knew the answers, using another approach.
After performing a quick search, Bonnetain found this 2018 paper that found integral distinguishers for all three of the algorithms covered in the September paper.
None of these experts are denigrating the research presented in the September paper. They are, however, noting that the claims presented in the original South China Morning Post article—and repeated in the ensuing media echo chamber afterward—go beyond mere exaggeration or embellishment. Instead, they're more comparable to fabrications. Even many of the articles debunking the claims—while well intentioned—missed the mark because they, too, cited the wrong paper.
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.
I emailed two of the co-authors of the September paper: Wang Chao, mentioned earlier, and Pei Zhi, a PhD. candidate at Shanghai University, asking for their help with this story. The only response I got was two auto-replies saying their inboxes were full.
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.
Read full article
Comments
Log in
