NIST Post-Quantum Cryptography Candidate Cracked

Belgian researchers have cracked the SIKE cryptographic algorithm, a fourth and final-round candidate that the U.S. National Institute of Standards and Technology (NIST) was evaluating for its Post-Quantum Cryptography (PQC) standard.

Wouter Castryck and Thomas Decru, research experts at the KU Leuven research university in Leuven, Belgium, broke the SIKE algorithm in about 62 minutes. They did it using a single core on a six-core Intel Xeon CPU E5-2630v2 at 2.60GHz, according to their article, An Efficient Key Recovery Attack On SIDH. 

NIST intends its PQC standard algorithms to resist post-quantum hacking capabilities. Yet, the researchers broke SIKE using a legacy computer chip.

According to an article on the news site The Debrief, experts, authorities, and news outlets have confirmed the researchers' findings. NIST has since determined that it will not standardize the SIKE algorithm.

As part of its PQC Standardization Process, NIST chose 69 of 82 cryptographic algorithm candidates for the first round of its evaluations, according to The Register. NIST had narrowed its list to eight algorithms, including SIKE, by July 2022, according to NIST.

The same month, Castryck and Decru cracked SIKE, including SIKE parameters that people thought could meet NIST quantum security levels one through five, according to the article by Castryck and Decru. "On July 22, we informed the SIKE team about our attack, and on July 30, we posted our corresponding paper online," says Castryck.

PQC algorithms matter because criminal hoard encrypted data for future attacks using quantum computers. "There's a threat called' harvest now, decrypt later'. Your enemy could get access to your data and copy it. Though it's encrypted, they can hold on to it until the quantum computer comes out, then they can get into it," says Dustin Moody, a mathematician at NIST.

According to a Whitehouse.gov fact sheet, President Biden has mandated that NIST will publish quantum-resistant cryptographic standards to mitigate the risk that quantum computers could break the cryptography safeguarding digital communications on the Internet.

According to an Office of Management and Budget memorandum, the U.S. must transition its cryptographic systems to quantum-resistant cryptography, mitigating as much of the quantum risk as possible by 2035. However, according to McKinsey, quantum computers may crack classical encryption methods as soon as 2030. Obviously, affected organizations must implement the PQC standards as quickly as they can once these become available.

The SIKE crack is both concerning and encouraging, according to Tomas Gustavsson, chief Public Key Infrastructure (PKI) officer of Keyfactor, a PKI-as-a-Service company. "It's normal to break new suggested algorithms, which is a sign that good cryptographers are working on evaluating those," says Gustavsson.

"The concern is that we probably can't trust SIKE's underlying mathematical problem of supersingular isogenies any longer," says Gustavsson. "So, the SIKE hack may also have implications for other algorithms that people have based on the same problem," he says. 

NIST has already selected four cryptographic algorithms for PQC standardization: CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON, and SPHINCS+. Three additional algorithms are under consideration in the fourth round of the NIST evaluation process: Classic McEliece, BIKE, and HQC. "We think we might choose one or two more of those fourth-round algorithms, but we wanted more time to evaluate them," says Moody.

There are challenges to creating cryptographic algorithms that can resist quantum-level hacking. "Solving challenging scientific problems, and having a high level of confidence in these, always takes a lot of time and effort by scientists, engineers, and whole teams of people," says Gustavsson.

The algorithms NIST chose for PQC standardization use older, harder math problems that many people have studied, according to Castryck. The hope is that quantum computers will not break these four algorithms, he says, although there is always that possibility.

According to Moody, no one can guarantee that no one will ever develop a smart new attack that could break a post-quantum cryptographic algorithm. "The best we can do in cryptography (post-quantum or not) is say that a lot of smart people have looked at it for many years and believe it is secure, i.e., no known attacks or lines of attack seem viable," says Moody.

It is essential for organizations not to lock into a single algorithm, according to Ted Shorter, CTO of Keyfactor. "I suspect that's part of why NIST is looking to standardize several algorithms this time," says Shorter. 

According to its infographic, the U.S. Department of Homeland Security supports cryptographic agility (or crypto-agility), which enables organizations to move to new cryptographic algorithms without costly infrastructure updates.

"Organizations must practice and prepare for crypto-agility. The days of relying on a small number of algorithms for long periods are almost over," says Shorter, as organizations must have a plan for how to change to a new algorithm quickly.

 

David Geer is a journalist who focuses on issues related to cybersecurity. He writes from Cleveland, OH, USA.