“Quantum-Safe” Crypto Hacked by 10-Year-Old PC
Many challenges still lie ahead for postquantum cryptography
Future quantum computers may rapidly break modern cryptography. Now researchers find that a promising algorithm designed to protect computers from these advanced attacks could get broken in just 4 minutes. And the catch is that 4-minute time stamp was not achieved by a cutting-edge machine but by a regular 10-year-old desktop computer. This latest, surprising defeat highlights the many hurdles postquantum cryptography will need to clear before adoption, researchers say.
In theory, quantum computers can quickly solve problems it might take classical computers untold eons to solve. For example, much of modern cryptography relies on the extreme difficulty that classical computers face when it comes to mathematical problems such as factoring huge numbers. However, quantum computers can in principle run algorithms that can rapidly crack such encryption.
To stay ahead of this quantum threat, cryptographers around the world have spent the past two decades designing postquantum cryptography (PQC) algorithms. These are based on new mathematical problems that both quantum and classical computers find difficult to solve.
“What is most surprising is that the attack seemingly came out of nowhere.”
—Jonathan Katz, University of Maryland at College Park
For years, researchers at organizations such as the National Institute of Standards and Technology (NIST) have been investigating which PQC algorithms should become the new standards the world should adopt. NIST announced it was seeking candidate PQC algorithms in 2016, and received 82 submissions in 2017. In July, after three rounds of review, NIST announced four algorithms that would become standards, and four more would enter another round of review as possible additional contenders.
Now a new study has revealed a way to completely break one of these contenders under review, known as SIKE, which Microsoft, Amazon, Cloudflare, and others have investigated. “The attack came from out of the blue, and was a silver bullet,” says cryptographer Christopher Peikert at the University of Michigan at Ann Arbor, who did not take part in this new work.
SIKE (Supersingular Isogeny Key Encapsulation) is a family of PQC algorithms involving elliptic curves. “Elliptic curves have long been studied in mathematics,” says mathematician Dustin Moody at NIST, who did not take part in this new work. “They are described by an equation looking like y2 = x3 + Ax + B, where A and B are numbers. So for example, an elliptic curve could be y2 = x3 + 3x + 2.”
In 1985, “mathematicians figured out a way to make cryptosystems involving elliptic curves, and these systems have been widely deployed,” Moody says. “However, these elliptic curve cryptosystems turn out to be vulnerable to attacks from a quantum computer.”
Around 2010, researchers found a new way to use elliptic curves in cryptography. “It was believed that this new idea wasn’t susceptible to attacks from quantum computers,” Moody says.
This new approach is based on how two points can be added on an elliptic curve to get another point on the elliptic curve, Moody says. An “isogeny” is a map from one elliptic curve to another elliptic curve that preserves this addition law.
“If you make this map complex enough, the conjectured hard problem, which allows encryption of data, is that given two elliptic curves, it’s hard to find an isogeny between them,” says study coauthor Thomas Decru, a mathematical cryptographer at KU Leuven in Belgium.
SIKE is a form of isogeny-based cryptography based on the Supersingular Isogeny Diffie-Hellman (SIDH) key exchange protocol. “SIDH/SIKE was one of the first practical isogeny-based cryptographic protocols,” Decru says.
However, one of SIKE’s vulnerabilities was that in order for it to work, it needed to provide extra information to the public known as auxiliary torsion points. “Attackers have tried to exploit this extra information for a while, but had not been successful in using it to break SIKE,” Moody says. “However, this new paper found a way to do it, using some pretty advanced mathematics.”
To explain this new attack, Decru says that although elliptic curves are one-dimensional objects, in mathematics elliptic curves can be visualized as objects of two dimensions or any other number of dimensions. One can also create isogenies between these generalized objects.
“People were naturally concerned that there might still be major attacks to be discovered, and they were right.”
—Steven Galbraith, University of Auckland
By applying a 25-year-old theorem, the new attack uses the extra information that SIKE makes public to construct an isogeny in two dimensions. This isogeny can then reconstruct the secret key that SIKE uses to encrypt a message. Decru and study senior author Wouter Castryck detailed their findings on 5 August in the Cryptology ePrint Archive.
“To me what is most surprising is that the attack seemingly came out of nowhere,” says cryptographer Jonathan Katz at the University of Maryland at College Park, who did not take part in this new work. “There were very few prior results showing any weaknesses in SIKE, and then suddenly this result appeared with a completely devastating attack—namely, it finds the entire secret key, and does so relatively quickly without any quantum computation.”
How One PC > All the Qubits (in This Case)
Using an algorithm based on this new attack, the researchers found that a 10-year-old Intel desktop took 4 minutes to find a secret key secured by SIKE.
“Usually, when a proposed cryptosystem gets seriously attacked, this happens relatively soon after the system is proposed, or begins to attract attention, or in a progression of research results over time, or yields not a total break but significant weakening of the system. In this instance we saw none of that,” Peikert says. “Attacks on SIDH/SIKE went from essentially no progress for 11 to 12 years, since SIDH was first proposed, to a total break.”
Although researchers had tested SIKE for more than a decade, “one of the reasons why SIKE was not selected for standardization is that there was concern that it is too new and has not been studied enough,” says mathematician Steven Galbraith at the University of Auckland, in New Zealand, who did not take part in this new work. “People were naturally concerned that there might still be major attacks to be discovered, and they were right.”
One reason SIKE’s vulnerability was not detected until now was because the new attack “applies very advanced mathematics—I can’t think of another situation where an attack has used such deep mathematics compared with the system being broken,” says Galbraith. Katz agrees, saying, “I suspect that fewer than 50 people in the world understand both the underlying mathematics and the necessary cryptography.”
Moreover, isogenies “are notoriously ‘difficult,’ both from an implementation and a theoretical perspective,” says cryptographer David Joseph at the PQC startup Sandbox AQ in Palo Alto, Calif., who did not take part in this new work. “This makes it more likely that fundamental flaws can persist undetected so late in the competition.”
“We proposed a system, which everyone agrees seemed like a good idea at the time, and after subsequent analysis someone is able to find a break. It is unusual that it took 10 years, but otherwise nothing to see here.”
—David Jao, University of Waterloo
Furthermore, “it should be noted that with many more algorithms in earlier rounds, the cryptanalysis was spread much more thinly, whereas for the past couple of years researchers have been able to concentrate on a smaller batch of algorithms,” Joseph says.
SIKE co-inventor David Jao, a professor at the University of Waterloo, in Canada, says, “I think the new result is magnificent work and I give the authors my highest praise.” At first, “I felt sad that SIKE had been invalidated, because it is such a mathematically elegant scheme, but the new findings simply reflect how science works,” he says. “We proposed a system, which everyone agrees seemed like a good idea at the time, and after subsequent analysis someone is able to find a break. It is unusual that it took 10 years, but otherwise nothing to see here except the ordinary course of progress.“
In addition, “it’s far better for SIKE to be broken now than in some hypothetical alternative world where SIKE becomes widely deployed and everyone comes to rely on it before it gets broken,” Jao says.
Breaks in the System
SIKE is the second NIST PQC candidate to get broken this year. In February, cryptographer Ward Beullens at IBM Research, in Zurich, revealed he could break third-round candidate Rainbow in a weekend on a laptop. “So this shows that all the PQC schemes still require further study,” Katz says.
Still, these new findings break SIKE but not other isogeny-based cryptography systems, such as CSIDH or SQIsign, Moody notes. “People from the outside may think isogeny-based cryptography is dead now, but this is far from true,” Decru says. “There’s still much to research, if you ask me.”
In addition, this new work also may not reflect one way or the other on NIST’s PQC research. SIKE was the only isogeny-based cryptosystem of the 82 submissions that NIST received. Similarly, Rainbow was the only multivariate algorithm among those submissions, Decru says.
“We have no absolute guarantee of security for any cryptosystem. The best we can say is that after a lot of study by a lot of smart people, nobody has found any cracks.”
—Dustin Moody, NIST
The other designs that NIST is adopting as standards or have made it to NIST’s fourth round “are based on mathematical ideas that have a longer track record of study and analysis by cryptographers,” Galbraith says. “This does not guarantee they are secure, but it just means they have withstood attacks for a longer time.”
Moody agrees, noting “it is always the case that some amazing breakthrough result could be discovered which breaks a cryptosystem. We have no absolute guarantee of security for any cryptosystem. The best we can say is that after a lot of study by a lot of smart people, nobody has found any cracks in the cryptosystem.”
Still, “our process was designed to allow for attacks and breaks,” Moody says. “We’ve seen them in each of the evaluation rounds. It’s the only way to gain confidence in the security.” Galbraith agrees, noting that such research “is the process working.”
Nevertheless, “I feel like the combination of Rainbow and SIKE falling will make more people seriously think about requiring a back-up plan for any winner that emerges from the NIST postquantum standardization process,” Decru says. “Relying on just one mathematical concept or scheme may be too risky. This is something NIST themselves thinks as well—their main scheme will most likely be lattice-based, but they want a nonlattice backup.”
Decru notes that other researchers are already developing new versions of SIDH/SIKE they suggest may thwart this new attack. “I expect more such results to follow, where people try to patch SIDH/SIKE, as well as improvements on our attack,” Decru says.
All in all, the fact that the starting point of this new attack was a theorem “totally unrelated to cryptography” shows “the importance of fundamental research in pure mathematics in order to understand cryptosystems,” Galbraith says.
Decru agrees, noting that “in mathematics, not everything is applicable right away. Hell, there are things that will almost surely never be applicable to any real-life situation. But that doesn’t mean we should not allow research to steer in these more obscure topics from time to time.”
This article appears in the November 2022 print issue as “‘Quantum-Safe’ Crypto Cipher Hacked by a 10-Year-Old PC.”