SIKE, one of the four algorithms selected by the National Institute of Standards and Technology (NIST) for Post-Quantum Cryptography (PQC), was recently outclassed by a single-core Intel chip in just over one hour. The algorithm had made it to round four of PQC, an NIST and U.S. government-backed effort to find alternatives to present-day encryption standards.
Being fourth-round candidates, the four algorithms were NIST’s answer to quantum computing-driven decryption, which can overwhelm current encryption techniques such as Diffie-Hellman, RSA, ChaCha20, AES, etc. The goal of PQC is to find algorithms that could resist future threats.
However, one of these — Supersingular Isogeny Key Encapsulation (SIKE) — probably won’t contend anymore, given it could be broken by the power of an outdated computer in just 62 minutes, or the amount of time it would take two pizzas to be delivered.
Kevin Bocek, vice president of security strategy and threat intelligence at Venafi, told Spiceworks, “You have to remember that we’ve had RSA keys for almost 45 years and that they’ve been tested everywhere across that period. This is our first real step towards post-quantum resistance, so it’s only natural that the first run isn’t a water-tight solution. It’d be more alarming if researchers found no flaws at all, as that would suggest testing hasn’t been rigorous enough.â€
“We’re also not going to deploy these new algorithms into production today, so early-stage testing and finding faults will only help to make the algorithms more secure in the long run. In fact, the findings on SIKE will only encourage researchers to find more flaws, which is exactly what we need since we will rely on these algorithms to move us forwards.â€
According to research by Wouter Castryck and Thomas Decru, the duo could break SIKE encryption using a program dubbed Magma, and an Intel Xeon CPU E5-2630v2, a 2.60 GHz CPU released in 2013. For reference, today’s computers are based on multi-core processors.
In their paperOpens a new window , titled An Efficient Key Recovery Attack on SIDH (Preliminary Version), Castryck and Decru, who work in Computer Security and Industrial Cryptography (COSIC) at KU Leuven, noted, “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. We also ran the code on random instances of SIKEp503 (level 2), SIKEp610 (level 3) and SIKEp751 (level 5), which took about 2h19m, 8h15m and 20h37m, respectively.â€
The math for SIKE to be broken existed since the 1990s, acknowledged David Jao, a professor in the Faculty of Mathematics at the University of Waterloo and one of the co-inventors of SIKE. Jao said the following to ArsTechnica:
“In general, there is a lot of deep mathematics which has been published in the mathematical literature but which is not well understood by cryptographers. I lump myself into the category of those many researchers who work in cryptography but do not understand as much mathematics as we really should. So sometimes, all it takes is someone who recognizes the applicability of existing theoretical math to these new cryptosystems. That is what happened here.â€
See More: PKI Silos, Post-Quantum Crypto and Other Emerging Trends in Cryptography: Part 1
As it stands, the other three candidates, viz., BIKE, Classic McEliece, and Hamming Quasi-Cyclic (HQC), will be measured against the results of the four third-round finalists which the NIST plans to standardize. However, NIST hasn’t officially omitted SIKE altogether from its assessment.
The cryptography algorithm that is officially gone is Rainbow, which was invalidatedOpens a new window by Ward Beullens, a postdoc at IBM Research, Zurich.
Castryck and Decru are entitled to $5,000 and $50,000Opens a new window from Microsoft for breaking the $IKEp182 and $IKEp217 challenges, respectively.
NIST’s assessment under PQC has thus far looked like the following in the last five years:
|
Round |
Year | Candidates (Public-key Encryption + Digital Signature Algorithms) |
Comments |
|
Round 1 |
2017 | 69Opens a new window | 33 eliminated |
| Round 2 | 2019 | 26Opens a new window |
11 eliminated |
|
Round 3 |
2020 | 7Opens a new window | 8 others including SIKE proceeded as alternatives |
| Round 4 | 2022 | 3Opens a new window |
1 alternative. Four additional alternatives, including SIKE, went into Round 4. |
SIKE was developed in collaboration betweenOpens a new window researchers at Microsoft, IBM, Amazon, LinkedIn, Texas Instruments, University of Waterloo, Louisiana Tech University, Radboud University, and the University of Toronto. Microsoft describes it as “a family of post-quantum key encapsulation mechanisms based on the Supersingular Isogeny Diffie-Hellman (SIDH) key exchange protocol.â€
But Bocek isn’t worried. He added, “At the moment, I don’t think we need to think about post-quantum algorithms as ‘hackable’ or ‘unhackable.’ The transition to post-quantum isn’t going to happen overnight – more likely decades, so the fact that we’re starting to see some positive steps towards it is a good sign.â€
One positive step that could and should be derived from the failure of SIKE is the need for crypto-agility in designing quantum encryption algorithms. InfoSec Global defines crypto-agility or cryptographic agility as the ability of an organization to rapidly and efficiently deploy new cryptographic policies across its digital footprint.
The endgame should be deterrence against unpredictable cryptographic vulnerabilities and the protection of digital assets. So even if a vulnerable encryption technique is enforced, it should be easily amended.
Bocek opined that we’re still far from a reality where post-quantum algorithms have become mainstream. He concluded, “The industry needs to have patience and ensure that any algorithms that are released are rigorously tested.â€
“This means that for the foreseeable future, we’re likely to see a hybrid approach, with current standards of encryption used whilst robust post-quantum algorithms are tested and eventually put into production alongside current forms of encryption. This is similar to the transition from combustion to electric cars that we’re currently in the midst of – it started with hybrids.â€
Let us know if you enjoyed reading this news on LinkedInOpens a new window , TwitterOpens a new window , or FacebookOpens a new window . We would love to hear from you!