Single-Core CPU Cracked Post-Quantum Encryption Candidate Algorithm in Just an Hour

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^[1]
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^[2]
code^[3]
breaks the Microsoft SIKE challenges^[4]
$IKEp182 and $IKEp217 in about 4 minutes and 6 minutes,
respectively,” KU Leuven researchers Wouter Castryck and Thomas
Decru said^[5]
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^[6]
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^[7]
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^[8]-based key encapsulation
suite based on pseudo-random walks in supersingular isogeny
graphs,” the description from the algorithm authors reads^[9].

Microsoft, which is one of the key collaborators on the
algorithm, said SIKE uses^[10] “arithmetic operations
on elliptic curves^[11] 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^[12], elliptic curve
cryptography (ECC^[13]), AES^[14], and ChaCha20^[15] 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^[16],” Jao said.
“Specifically, it breaks SIDH^[17] [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^[18], are also based on
SIDH, and are also broken by the new attack. Some of them, such as
CSIDH^[19] and SQIsign^[20], 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.