“Quantum-Safe” Crypto Hacked by 10-Year-Old PC

Future quantum computers could quickly break modern cryptography. Now researchers find that a promising algorithm designed to protect computers from these advanced attacks can be broken in just 4 minutes. And the catch is that the 4-minute timestamp was not achieved by a cutting-edge machine, but by an ordinary 10-year-old desktop computer. This latest, surprising defeat highlights the many hurdles post-quantum cryptography must clear before adoption, researchers say.

In theory, quantum computers can quickly solve problems that would take classical computers countless ages to solve. For example, much of modern cryptography relies on the extreme difficulties classical computers face when it comes to mathematical problems such as factoring huge numbers. However, quantum computers can in principle run algorithms that can quickly crack such encryption.

To stay ahead of this quantum threat, cryptographers worldwide have spent the past two decades designing post-quantum cryptography (PQC) algorithms. These are based on new mathematical problems that both quantum and classical computers have difficulty solving.

“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 candidates for PQC algorithms in 2016, and received 82 submissions in 2017. In July, after three rounds of review, NIST announced four algorithms would become standards, and four more would enter a new round of review as possible additional candidates.

Now, a new study has revealed a way to completely break one of those contenders under consideration, known as SIKE, which Microsoft, Amazon, Cloudflare and others have been investigating. “The attack came out of the blue, and was a silver bullet,” says the cryptographer Christopher Peikert at the University of Michigan in Ann Arbor, who did not participate in this new work.

Elliptical training sessions

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 of NIST, who was not involved in this new work. “They are described by an equation that looks like y² = x³ + Ax + B, where A and B are numbers. So for example an elliptic curve can be y² = x³ + 3x + 2.”

In 1985, “mathematicians figured out a way to make cryptosystems involving elliptic curves, and these systems have become widely distributed,” says Moody. “But these elliptic curve cryptosystems turn out to be vulnerable to attack by a quantum computer.”

Around 2010, researchers found a new way to use elliptic curves in cryptography. “It was believed that this new idea was not susceptible to attack by quantum computers,” says Moody.

This new approach is based on how two points can be added on an elliptic curve to get another point on the elliptic curve, says Moody. An “isogeny” is a map from one elliptic curve to another elliptic curve that preserves this law of addition.

“If you make this map complex enough, the supposedly hard problem, which allows encryption of data, is that given two elliptic curves, it’s hard to find an isogeny between them,” says study co-author 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,” says Decru.

However, one of SIKE’s vulnerabilities was that in order for it to work, it had to provide additional information to the audience known as auxiliary torsion points. “Attackers have been trying to exploit this extra information for some time, but had been unsuccessful in using it to break SIKE,” says Moody. “But this new paper found a way to do that using some pretty advanced math.”

To explain this new attack, Decru says that although elliptic curves are one-dimensional objects, in mathematics elliptic curves can be visualized as objects with 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 detect, and they were right.”
—Steven Galbraith, University of Auckland

Using a 25-year-old theorem, the new attack uses the additional 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 August 5 in the Cryptology ePrint Archive.

“To me, the most surprising thing is that the attack seemingly came out of nowhere,” says cryptographer Jonathan Katz of the University of Maryland in College Park, who was not involved in this new work. “There were very few previous results that showed any weaknesses in SIKE, and suddenly this result appeared with a completely devastating attack – namely, it finds the entire secret key, and does it relatively quickly without any quantum computation.”

How one PC > All 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 is 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 produces not a total break, but a significant weakening of system. In this case, we saw none of that,” says Peikert. “Attacks on SIDH/SIKE went from virtually no progress in 11 to 12 years, since SIDH was first proposed, to a total pause.”

Although researchers had been testing SIKE for more than a decade, “one of the reasons SIKE was not chosen for standardization is that there was concern that it is too new and has not been studied enough,” says mathematician Steven Galbraith of the University of Auckland, in New Zealand, which did not participate in this new work. “People were naturally concerned that there might still be major attacks to detect, and they were right.”

One reason SIKE’s vulnerability wasn’t discovered until now was because the new attack “uses very advanced mathematics—I can’t think of another situation where an attack has used such deep mathematics compared to the system that’s broken,” Galbraith says. Katz agrees, saying, “I suspect that fewer than 50 people in the world understand both the underlying mathematics and the necessary cryptography.”

Also, 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, California, who was not involved in this new work. “This makes it more likely that fundamental errors can persist undetected this late in the competition.”

“We proposed a system that everyone agrees seemed like a good idea at the time, and after subsequent analysis someone might find a break. It’s 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 previous rounds, the cryptanalysis was spread much more thinly, whereas in the last couple of years researchers have been able to concentrate on a smaller group of algorithms,” says Joseph.

SIKE co-inventor David Jao, a professor at the University of Waterloo, in Canada, says: “I think the new result is amazing 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 that everyone agrees seemed like a good idea at the time, and after subsequent analysis someone might find a break. It’s unusual that it took 10 years, but otherwise there’s nothing to see here except that normal progress.”

Additionally, “it is far better for SIKE to be broken now than in a hypothetical alternate world where SIKE becomes widespread and everyone comes to trust it before it is broken,” says Jao.

Breach in the system

SIKE is the second NIST PQC candidate to be broken this year. In February, cryptographer Ward Beullens at IBM Research, in Zurich, revealed that he could crack third-round contender Rainbow in a weekend on a laptop. “So this shows that all of the PQC schemes still require further study,” says Katz.

Still, these new findings break SIKE, but not other isogen-based cryptography systems, such as CSIDH or SQIsign, notes Moody. “People outside might think isogeny-based cryptography is dead now, but this is far from true,” says Decru. “There’s still a lot of research to be done, if you ask me.”

Additionally, this new work may not reflect one way or another of NIST’s PQC research. SIKE was the only isogeny-based cryptosystem out of the 82 submissions that NIST received. Similarly, Rainbow was the only multivariate algorithm among these submissions, says Decru.

“We have no absolute guarantee of security for any cryptosystem. The best we can say is that after much study by many smart people, no one 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 that they are secure, but it just means that they have resisted attacks for a longer period of time.”

Moody agrees, noting that “it’s always the case that an amazing breakthrough result can be discovered that 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, no one has found any cracks in the cryptosystem.”

Still, “our process was designed to allow for fits and breaks,” says Moody. “We have seen them in each of the evaluation rounds. It is the only way to gain confidence in security.” Galbraith agrees, noting that such research “is the process that works.”

Still, “I feel that the combination of the Rainbow and SIKE cases will make more people think seriously about requiring a backup plan for any winner that emerges from the NIST post-quantum standardization process,” says Decru. “Relying on just one mathematical concept or schema can be too risky. This is something NIST themselves are also thinking – their main scheme will most likely be lattice based, but they will have a non-lattice backup.”

Decru notes that other researchers are already developing new versions of SIDH/SIKE, which they suggest can prevent this new attack. “I expect more such results to follow, with people trying to patch SIDH/SIKE, as well as improvements to our attack,” says Decru.

All in all, the fact that the starting point for this new attack was a theorem “completely unrelated to cryptography” shows “the importance of fundamental research in pure mathematics to understanding cryptosystems,” says Galbraith.

Decru agrees, noting that “in math, not everything is immediately applicable. Hell, there are things that will almost certainly never be applicable in any real-world situations. But that doesn’t mean we shouldn’t let research rule into these more obscure topics from time to time.”