NIST post-quantum algorithm candidate’s future uncertain, with second attack proposed

Uncertainty surrounds a cracked post-quantum cryptography algorithm being considered by the National Institute of Standards and Technology, now that researchers have potentially discovered a second attack method.

NIST won’t make a final decision on whether to standardize any of its four Round 4 candidates, including the Supersingular Isogeny Key Encapsulation (SIKE), for 18 to 24 months, giving the team behind it time to find fixes if it chooses.

Researchers from the University of Bristol on Monday proposed an attack on SIKE they say “significantly reduces” the security of SIKE by solving it with torsion.

The agency already selected four quantum-resistant cryptographic algorithms for standardization to address concerns foreign adversaries like China are developing quantum computers capable of breaking the public-key cryptography securing most federal systems. SIKE represents an alternative approach to general encryption, should others prove vulnerable to quantum computers, but it was recently cracked by two researchers with a single-core computer in about an hour — albeit using complex math.

“NIST selected SIKE as a fourth-round candidate because it seemed promising, but it needed further study before we would have sufficient confidence to select it as a standard,” Lily Chen, Cryptographic Technology Group manager, told FedScoop. “The attack on SIKE, while not good news for SIKE, is a positive sign that the research community is taking this challenge seriously.”

Still NIST will only accept “minor changes, not substantial redesigns” to SIKE and has already rejected algorithm changes proposed by previous candidates cracked in “major attacks” for that reason, Chen said.

NIST continues to study isogeny-based cryptography more generally and work with the research community to analyze SIKE’s weaknesses revealed by the attack, which exploited the fact its public key and ciphertext are based on an elliptic curve with publicly known properties and contain auxiliary information not always given by similar cryptosystems.

The attack might be thwarted by a modification to the Supersingular Isogeny Diffie-Hellman (SIDH) protocol that would generate the elliptic curve while hiding its sensitive properties, Chen said.

Whether that’s a useful fix remains unclear because two more researchers proposed an attack algorithm Monday they say wouldn’t require publicly known curve properties to be successful using a regular computer, David Jao, SIKE’s principal submitter, told FedScoop.

“If the research community remains unsettled with no consensus, then that in and of itself would indicate that SIKE is not ready to proceed to standardization,” Jao said. “There is nothing wrong with this outcome, and in fact it may even be the most exciting scenario from a research standpoint. But standardization requires stability.”

The SIKE team has only exchanged “one round of emails” with NIST on an initial fix, he added.

NIST’s confidence in its algorithm candidates depends on the cryptography research community taking its post-quantum cryptography (PQC) challenge seriously, Chen said.

“The NIST PQC standardization process depends on this type of community involvement, and we have expected cryptanalysis results such as this during the process,” she said. “This is not the only such result released so far, and we will handle it in the same way as we have before.”