Cookie Consent by Free Privacy Policy Generator
Search
Close this search box.

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

Man using computer and programming to break code. Cyber security threat. Breaking protection

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.

The Future of Materials Discovery: Reducing R&D Costs significantly with GenMat’s AI and Machine Learning Tools

When: July 13, 2023 at 11:30am

What: GenMat Webinar

Jake Vikoren

Jake Vikoren

Company Speaker

Deep Prasad

Deep Prasad

Company Speaker

Araceli Venegas

Araceli Venegas

Company Speaker

Matt Swayne

With a several-decades long background in journalism and communications, Matt Swayne has worked as a science communicator for an R1 university for more than 12 years, specializing in translating high tech and deep tech for the general audience. He has served as a writer, editor and analyst at The Quantum Insider since its inception. In addition to his service as a science communicator, Matt also develops courses to improve the media and communications skills of scientists and has taught courses. [email protected]

Share this article:

Relevant

The Future of Materials Discovery: Reducing R&D Costs significantly with GenMat’s AI and Machine Learning Tools

When: July 13, 2023 at 11:30am

What: GenMat Webinar

Jake Vikoren

Jake Vikoren

Company Speaker

Deep Prasad

Deep Prasad

Company Speaker

Araceli Venegas

Araceli Venegas

Company Speaker

Keep track of everything going on in the Quantum Technology Market.

In one place.

Join Our Newsletter