Post-quantum crypto cracked in an hour with one core of an ancient Xeon

NIST's nifty new algorithm looks like it's in trouble

One of the four encryption algorithms America's National Institute of Standards and Technology (NIST) considered as likely to resist decryption by quantum computers has had holes kicked in it by researchers using a single core of a regular Intel Xeon CPU, released in 2013.

The Supersingular Isogeny Key Encapsulation (SIKE) algorithm was described by NIST as under consideration for standardization, meaning it advanced to an extra round of testing en route to adoption.

Within SIKE lies a public key encryption algorithm and a key encapsulated mechanism, each instantiated with four parameter sets: SIKEp434, SIKEp503, SIKEp610 and SIKEp751.

Microsoft – whose research team played a role in the algorithm's development along with multiple universities, Amazon, Infosec Global and Texas Instruments – set up a $50,000 bounty for anyone who could crack it.

Belgian boffins Wouter Castryck and Thomas Decru claim to have done just that, using some good ol' non-quantum x86 silicon.

"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. 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," wrote Castryck and Decru, of Katholieke Universiteit Leuven (KU Leuven ) in a a preliminary article [PDF] announcing their discovery.

The authors made their code public, as well as the details of their processor: an Intel Xeon CPU E5-2630v2 at 2.60GHz. That bit of kit was launched in Q3 2013, used Intel's Ivy Bridge architecture and a 22nm manufacturing process. The chip offered six cores – not that five of them were in any way encumbered by this challenge.

Quantum-resistant encryption research is a hot topic because it is felt that quantum computers are almost certain to become prevalent and sufficiently powerful to crack existing encryption algorithms. It is therefore prudent to prepare crypto that can survive future attacks, so that data encrypted today remains safe tomorrow, and digital communications can remain secure.

Thus, bounties for testing its limits abound.

Microsoft described the algorithm as using arithmetic operations on elliptic curves defined over finite fields and compute maps, also called isogenies, between the curves.

Finding such an isogeny was thought to be sufficiently difficult to provide reasonable security – a belief now shattered by nine-year-old tech.

Alongside the vintage processor, Castryck and Decru used a key recovery attack on the Supersingular Isogeny Diffie–Hellman key exchange protocol (SIDH) that was based on Ernst Kani's "glue-and-split" theorem.

"The attack exploits the fact that SIDH has auxiliary points and that the degree of the secret isogeny is known. The auxiliary points in SIDH have always been an annoyance and a potential weakness, and they have been exploited for fault attacks, the GPST adaptive attack, torsion point attacks, etc." argued University of Auckland mathematician Stephen Galbraith in his cryptography blog.

The math gets cerebral, and Galbraith suggests if you really want to understand it, you need to study Richelot isogenies and abelian surfaces.

Damn. Another missed opportunity during lockdown.

But we digress. For those who already have a rich background in elliptic curve cryptography and want a quick immersion, there are several Twitter threads that analyze the achievement at greater depth.

Some professionals in the arena propose that not all is lost with SIKE.

SIKE co-creator David Jao reportedly believes the NIST submitted version of SIKE used a single step to generate the key, and a possible more resilient variant could be constructed with two steps.

That possibility lies still in a yet undiscovered portion of the intersection of mathematics and computer science. In the meantime, cryptography experts are shaken.

"There is no doubt that this result will reduce confidence in isogenies. The sudden appearance of an attack this powerful shows that the field is not yet mature," commented Galbraith.

Security researcher Kenneth White tweeted his awe and noted "In 10-20 yrs (or 50, or never) we *might* have practical quantum computers, so let's roll out replacement PQ crypto now. Which could be trivially broken today, on a laptop."

But as Kevin Reed, CISO of cybersecurity firm Acronis, put it in a LinkedIn post: "It's still better than if it was discovered after it is standardized." ®