Single-Core CPU cracked post-quantum encoding candidate algorithm in just an hour


A late-stage candidate encryption algorithm intended to withstand decryption by powerful quantum computers in the future has been trivially cracked by using a computer with an Intel Xeon CPU in an hour.

The algorithm in question is SIKE – short for Supersingular Isogeny Key Encapsulation – that the fourth round of the Post-Quantum Cryptography (PQC) standardization process by the US Department of Commerce’s National Institute of Standards and Technology (NIST).

“Run on a single core, the attached Magma code breaks the Microsoft SIKE Challenges $IKEp182 and $IKEp217 in approximately 4 minutes and 6 minutes respectively”, KU Leuven researchers Wouter Castryck and Thomas Decru said in a new newspaper.

“A run on the SIKEp434 parameters, previously believed to meet NIST’s quantum security level 1, took approximately 62 minutes, again on a single core.”

The code was run on an Intel® Xeon CPU E5-2630v2 at 2.60 GHz, which was released in 2013 using the chipmaker’s Ivy Bridge microarchitecture, the academics further noted.

The findings come as NIST announced its first set of quantum-resistant encryption algorithms in early July: CRYSTALS-Kyber for general purpose encryption and CRYSTALS-Dilithium, FALCON and SPHINCS+ for digital signatures.

“SIKE is a isogeny-based key encapsulation suite based on pseudo-random walks in supersingular isogeny graphs”, the description of the algorithm authors is reading.

Microsoft, one of the key contributors to the algorithm, said SIKE applications “arithmetic operations on elliptic curves defined over finite fields and calculation maps, so-called isogenies, between such curves.”

“The safety of SIDH and SIKE depends on the difficulty of finding a specific isogeny between two such elliptic curves, or equivalently, on finding a path between them in the isogeny graph,” explains the tech giant’s research team.

Quantum-resistant cryptography is an effort to develop encryption systems that are secure against both quantum and traditional computing systems, while also interoperating with existing communication protocols and networks.

The idea is to ensure that data is encrypted today using current algorithms such as: RSAelliptic curve cryptography (ECC), AESand ChaCha20 will not be made vulnerable to brute force attacks in the future with the advent of quantum computers.

“Each of these systems is based on some kind of math problem that’s easy to perform in one direction, but difficult in the other,” David Jao, one of SIKE’s co-inventors, told The Hacker News. “Quantum computers can easily solve the hard problems underlying RSA and ECC, which would affect about 100% of encrypted Internet traffic if quantum computers were built.”

Although SIKE was positioned as one of the NIST-designated PQC candidates, the latest research effectively invalidates the algorithm.

“The work of Castryck and Decru breaks SIKE“said Jao. “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 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 like CSIDH and SQIsignare not based on SIDH and, as far as we know, are not directly affected by the new attack.”

As for next steps, Jao said, while SIDH may be updated to reinstate the new key recovery attack rule, it is expected to be delayed until further investigation.

“It is possible that SIDH can be patched or fixed to prevent the new attack, and we have some ideas for doing this, but more analysis of the new attack is needed before we can confidently make a statement about potential solutions. ‘ said Joe.