A late-stage candidate encryption algorithm that was meant to withstand decryption by powerful quantum computers in the future has been trivially cracked by using a computer running Intel Xeon CPU in an hour’s time.
The algorithm in question is SIKE — short for Supersingular Isogeny Key Encapsulation — which made it to the fourth round of the Post-Quantum Cryptography (PQC) standardization process by the U.S. Department of Commerce’s National Institute of Standards and Technology (NIST).
“Ran on a single core, the appended Magma code breaks the Microsoft SIKE challenges $IKEp182 and $IKEp217 in about 4 minutes and 6 minutes, respectively,” KU Leuven researchers Wouter Castryck and Thomas Decru said in a new paper.
“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.”
The code was executed on an Intel Xeon CPU E5-2630v2 at 2.60GHz, which was released in 2013 using the chip maker’s Ivy Bridge microarchitecture, the academics further noted.
The findings come as NIST, in early July, announced the first set of quantum-resistant encryption algorithms: CRYSTALS-Kyber for general encryption, and CRYSTALS-Dilithium, FALCON, and SPHINCS+ for digital signatures.
“SIKE is an isogeny-based key encapsulation suite based on pseudo-random walks in supersingular isogeny graphs,” the description from the algorithm authors reads.
Microsoft, which is one of the key collaborators on the algorithm, said SIKE uses “arithmetic operations on elliptic curves defined over finite fields and compute maps, so-called isogenies, between such curves.”
“The security of SIDH and SIKE relies on the hardness of finding a specific isogeny between two such elliptic curves, or equivalently, of finding a path between them in the isogeny graph,” the tech giant’s research team explains.
Quantum-resistant cryptography is an attempt to develop encryption systems that are secure against both quantum and traditional computing systems, while also interoperating with existing communications protocols and networks.
The idea is to ensure that data encrypted today using current algorithms such as RSA, elliptic curve cryptography (ECC), AES, and ChaCha20 is not rendered vulnerable to brute-force attacks in the future with the advent of quantum computers.
“Each of these systems relies on some sort of math problem which is easy to do in one direction but hard in the reverse,” David Jao, one of the co-inventors of SIKE, told The Hacker News. “Quantum computers can easily solve the hard problems underlying RSA and ECC, which would affect approximately 100% of encrypted internet traffic if quantum computers were to be built.”
While SIKE was positioned as one of the NIST-designated PQC contenders, the latest research effectively invalidates the algorithm.
“The work by Castryck and Decru breaks SIKE,” Jao said. “Specifically, it breaks SIDH [Supersingular Isogeny Diffie-Hellman], the ‘hard’ problem on which SIKE is based (analogous to how integer factorization is the hard problem on which RSA is based).”
“There are other isogeny-based cryptosystems other than SIKE. Some of these, such as B-SIDH, are also based on SIDH, and are also broken by the new attack. Some of them, such as CSIDH and SQIsign, are not based on SIDH, and as far as we know, are not directly affected by the new attack.”
As for the next steps, Jao said while SIDH can be updated to remediate the new line of the key recovery attack, it’s expected to be put off until further examination.
“It is possible that SIDH can be patched or fixed up to avoid the new attack, and we have some ideas for how to do so, but more analysis of the new attack is required before we can confidently make a statement about any possible fixes,” Jao said.