Single-Core PC Breaks Post-Quantum Encryption Candidate Algorithm in One Hour
Defeating next-gen quantum cryptography with pure math.
Researchers with the Computer Security and Industrial Cryptography group (CSIS) at KU Leuven have managed to break one of the late-stage candidate algorithms for post-quantum encryption. The algorithm, SIKE (short for Supersingular Isogeny Key Encapsulation), made it through most stages of the US Department of Commerce’s National Institute of Standards and Technology (NIST) competition that aimed to define standardized, post-quantum algorithms against the threat posed by quantum computers - which will render current encryption schemes obsolete.
The researchers approached the problem from a purely mathematical standpoint, attacking the core of the algorithm’s design instead of any potential code vulnerabilities.
For mathematicians, the researchers were able to crunch SIKE by attacking its base encryption math, Supersingular Isogeny Diffie-Hellman (SIDH). They showed that SIDH is vulnerable to the “glue-and-split” theorem, developed by mathematician Ernst Kani in 1997, with additional mathematical tools devised in 2000. Still placed squarely in the mathematical arena, the attack uses genus two curves to attack elliptic curves (genus 1 curves). According to SIKE co-inventor David Jao, a professor at the University of Waterloo, “The newly uncovered weakness is clearly a major blow to SIKE” - which it is. But he added that all of this goes back to cryptographers’ sometimes imperfect dominion of pure mathematics, in that the approach taken by the researchers was “really unexpected.”
For the rest of us, all of that means that the researchers used math to understand SIKE’s encryption scheme and could predict - and then retrieve - its encryption keys.
For their troubles and the paper titled An Efficient Key Recovery Attack on SIDH (Preliminary Version), the researchers received a Microsoft-sponsored $50,000 bounty.
SIKE emerged to prominence after making it one of four additional candidates being considered by NIST after the organization last month officially announced the four algorithms that will replace the currently-used RSA, Diffie-Hellman, and elliptic curve Diffie-Hellman algorithms. Most of the globe’s cybersecurity stands on these algorithms, which have been invaluable in securing information against bad actors - when they aren’t compromised by other means. But they have a fundamental issue: they’ll be easily bested once quantum computers scale enough. And that’s not a matter of “if” anymore: it’s a matter of “when.”
“When” is expected to occur within this decade, so there’s a veritable race to harden future computing systems and update the encryption schemes applied to current information.
Stay On the Cutting Edge: Get the Tom's Hardware Newsletter
Get Tom's Hardware's best news and in-depth reviews, straight to your inbox.
To put the big problem into perspective, consider this: the current estimation is that humanity will have produced and stored 64 zettabytes (1,000 bytes to the seventh power) of data by 2020. Almost none of that information is currently quantum-resistant. But, for now, we’re somewhat insulated from a cascade of quantum-powered hacks by the technology’s complexity - only the most remarkable corporations and prosperous states have the brain, human, and monetary capital for these systems.
But the cost will decrease. Close to “off-the-shelf” solutions will eventually appear. And when they do, any data secured with classical algorithms will have as good a protection as an apple’s skin is at preventing you from sinking your teeth into its core.
Yet it seems that all it takes to break specific leading-edge designs - namely, SIKE - is a single-core computer and an exotic application of high-level math. So it begs the question: are we ready to create standards for such a burgeoning field of computing, where novel approaches and breakthroughs are announced daily?
As Jonathan Katz, an IEEE Member and professor in the department of computer science at the University of Maryland, wrote in an email to Ars Technica, “It is perhaps a bit concerning that this is the second example in the past six months of a scheme that made it to the 3rd round of the NIST review process before being completely broken using a classical algorithm.” Rainbow, the candidate he is referring to, was broken in February this year, although only at a theoretical level. He continued: “Three of the four PQC schemes rely on relatively new assumptions whose exact difficulty is not well understood, so what the latest attack indicates is that we perhaps still need to be cautious/conservative with the standardization process going forward.”
Whether the time is ripe for standardization or not, one thing is certain: intense work in post-quantum cryptography is needed. Just think about the systemic damage a single successful attack on a medium-sized bank - flipping all its information to a zero, for instance - would have on its very human clients and the financial system at large. We’re talking about everything ranging from single-parent families to 401K savings accounts through small and not-so-small companies.
There are few issues as important as this one. Its cryptographic and mathematically-sound exploration is paramount.
Francisco Pires is a freelance news writer for Tom's Hardware with a soft side for quantum computing.
-
davidjao There are some inaccuracies in this article. The $50000 bounty mentioned in the article was not sponsored by NIST; it was provided by Microsoft. The article also does not clearly distinguish between the four algorithms selected as replacement standards by NIST and the four additional algorithms selected as candidates for further study; these two collections of four algorithms each are separate sets of algorithms.Reply -
InvalidError In science and engineering, many complex problems in the time domain become trivial in the frequency domain and vice-versa.Reply
I'm getting the vibe that something similar may happen between quantum and classic computing. -
jeremyj_83 It would be quite ironic if the requirements for encryption to be quantum resistant would make it easily susceptible to classic computers and algorithms.Reply -
RodroX This is what happend every time you want to solve a problem, and forget or neglect to take into consideration the whole science and engineering available.Reply -
bit_user
True, but we don't even know if these two algorithms were indeed quantum-resistant.jeremyj_83 said:It would be quite ironic if the requirements for encryption to be quantum resistant would make it easily susceptible to classic computers and algorithms.
Yet, the question stands: just how much intersection exists between quantum-resistant and classical-resistant algorithms. I expect anyone solving such a conjecture deserves a fair bit more than $50k! -
bit_user BTW, I expect the title really means "single-threaded program" breaks post-quantum encryption, but I can't read it without thinking how far back you'd have to go to find a single-core x86 CPU! Would it be from the Core2 generation?Reply -
InvalidError
They probably meant: "single-threaded algorithm breaks post-quantun crypto."bit_user said:BTW, I expect the title really means "single-threaded program" breaks post-quantum encryption, but I can't read it without thinking how far back you'd have to go to find a single-core x86 CPU! Would it be from the Core2 generation?
Doesn't matter how many extra cores a CPU has if you don't use them. -
jeremyj_83
The AMD A6-9400 based on Bristol Ridge was released in 2019 and is a 1c/2t CPU. If you want something that was without SMT or CMT it would be Core2 era from Intel or Phenom era from AMD.bit_user said:BTW, I expect the title really means "single-threaded program" breaks post-quantum encryption, but I can't read it without thinking how far back you'd have to go to find a single-core x86 CPU! Would it be from the Core2 generation? -
samopa bit_user said:BTW, I expect the title really means "single-threaded program" breaks post-quantum encryption, but I can't read it without thinking how far back you'd have to go to find a single-core x86 CPU! Would it be from the Core2 generation?
You can rent single core single thread (1C1T) Compute Engine from the cloud provider. -
InvalidError
I can only imagine people renting a 1C virtual servers to run lightweight private servers independently from their home/office internet connection. Doesn't make much sense for actual compute that doesn't need online connectivity since your department likely has several PCs many times as powerful.samopa said:You can rent single core single thread (1C1T) Compute Engine from the cloud provider.