One of four encryption algorithms recommended by the U.S. National Institute of Standards and Technology (NIST) as likely to resist decryption by quantum computers has been cracked by researchers using a single core of an Intel Xeon processor , released in 2013.
The Supersingular isogeny key encapsulation (SIKE) was selected by NIST last month as a standards candidate, which means it has moved on to an additional round of testing on the way to adoption.
Within SIKE are a public key encryption algorithm and an encapsulated key mechanism, each instantiated with four sets of parameters: SIKEp434, SIKEp503, SIKEp610, and SIKEp751.
Microsoft – whose research team played a role in developing the algorithm along with several universities, Amazon, Infosec Global and Texas Instruments – has set up a $50,000 program prime for anyone who might break it.
Belgian boffins Wouter Castryck and Thomas Decru claim to have done just that.
“Running on a single core, the added Magma code breaks Microsoft SIKE challenges $IKEp182 and $IKEp217 in approximately 4 minutes and 6 minutes, respectively. 62 minutes, again on a single core,” wrote Castryck and Decru, from the Katholieke Universiteit Leuven (KU Leuven) in aa preliminary article [PDF] announcing their discovery.
The authors have made their code public, as well as the coordinates of their processor: a 2.60 GHz Intel Xeon E5-2630v2 processor. This kit was released in Q3 2013, used Intel’s Ivy Bridge architecture and a 22 nm manufacturing process. The chip offered six cores – not that five of them were in any way bothered by this challenge.
Research into quantum-resistant encryption is a hot topic as it is believed that quantum computers will almost certainly become widespread and powerful enough to break 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 one’s limits abound.
Microsoft describe the algorithm uses arithmetic operations on elliptic curves defined over finite fields and calculates maps, also called isogenies, between the curves.
Finding such isogeny was considered difficult enough to provide reasonable security – a belief now shattered by nine-year-old technology.
Along with the vintage CPU, Castryck and Decru used a key recovery attack on the Supersingular Isogeny Diffie–Hellman (SIDH) key exchange protocol based on Ernest Kani’s “stick and split” theorem.
“The attack exploits the fact that SIDH has auxiliary points and the degree of covert isogeny is known. Auxiliary points in SIDH have always been an annoyance and potential weakness, and they have been exploited for fault attacks, GPST adaptive attack, twist point attacks, etc.” supported Stephen Galbraith, a mathematician from the University of Auckland, in his crypto blog.
The math gets cerebral, and Galbraith suggests that 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 wealth of experience in elliptic curve cryptography and want a quick immersion, there is various Twitter feeds that analyze realization at greater depth.
Some professionals in the arena propose that all is not lost with SIKE.
SIKE co-creator David Jao would have believes that the version of SIKE submitted by NIST used a single step to generate the key, and a possible more resilient variant could be built in two steps.
This possibility still lies in a yet unknown part of the intersection of mathematics and computer science. In the meantime, crypto experts are reeling.
“There is no doubt that this result will reduce confidence in isogenies. The sudden appearance of such a powerful attack shows that the field is not yet mature,” commented Galbraith.
Security Researcher Kenneth White tweeted his admiration and noted “In 10-20 years (or 50, or never), we *might* have practical quantum computers, so let’s deploy the replacement PQ crypto now. What could be trivially broken today, on a laptop.”
But as Kevin Reed, CISO of cybersecurity firm Acronis, put it in a LinkedIn position: “It’s still better than if it were discovered after it was standardized.” ®