Post-Quantum Safe Algorithm Candidate Cracked in an Hour on a PC

Well, that decrypted quickly…

A team of scientists report they were able to defeat one of the post-quantum safe algorithms that is still under consideration as part of the National Institute of Standards and Technology’s (NIST) PQC program — and it only took one computational core on a PC working for about an hour.

The team, from Computer Security and Industrial Cryptography group (CSIS) at KU Leuven, were able to crack the algorithm SIKE — or Supersingular Isogeny Key Encapsulation (SIKE) — using a mathematical approach to understand SIKE’s encryption and then predict and steal its encryption keys.

In the study, the researchers write: “We present a new and powerful key recovery attack on the Supersingular Isogeny Diffie–Hellman key exchange protocol and its instantiation SIKE that recently advanced to the fourth round of NIST’s ongoing Post-Quantum Cryptography standardization process. It is based on a “glue-and-split” theorem from 1997 due to Ernst Kani and heavily outperforms previous attack strategies…”

Startingly, the hack was performed on a classical computer — and took about an hour to complete.

They write: “A run on the SIKEp434 parameters, previously believed to meet NIST’s quantum security level 1, took about 62 minutes, again on a single core. We also ran the code on random instances of SIKEp503 (level 2), SIKEp610 (level 3) and SIKEp751 (level 5), which took about 2h19m, 8h15m and 20h37m, respectively.”

SIKE was among several algorithms that passed a NIST competition to identify and define standardized post-quantum algorithms. Because quantum computers represent a threat to current measures for securing information and data, the organization wanted to pinpoint algorithms that stood the best chance of withstanding attacks from quantum computers.

In a blog post, Steven Galbraith, a University of Auckland mathematics professor and a leading cryptographic expert, explains how they accomplished the hack: “The attack exploits the fact that SIDH has auxiliary points and that the degree of the secret isogeny is known. The auxiliary points in SIDH have always been an annoyance and a potential weakness, and they have been exploited for fault attacks, the GPST adaptive attack, torsion point attacks, etc.”

It’s not the end for SIKE. There may be ways to modify the algorithm to withstand these specific types of attacks. However, in an Ars Technica story, Jonathan Katz, professor in the department of computer science at the University of Maryland, said the news that a classical computer could crack an encryption scheme meant to be safe from quantum devices is troubling.

Katz wrote: “It is perhaps a bit concerning that this is the second example in the past six months of a scheme that made it to the 3rd round of the NIST review process before being completely broken using a classical algorithm. (The earlier example was Rainbow, which was broken in February.) Three of the four PQC schemes rely on relatively new assumptions whose exact difficulty is not well understood, so what the latest attack indicates is that we perhaps still need to be cautious/conservative with the standardization process going forward.”

Based on the achievement, the team — Wouter Castryck and Thomas Decru — should be in line to win $50,000 from Microsoft’s SIKE Cryptographic Challenge.