In the US government’s ongoing campaign to protect data in the age of quantum computers, a new and powerful attack that used a single classical computer to completely crack the fourth-round filter highlights the risks involved in standardizing the next generation of cryptographic algorithms.
Last month, the US Department of Commerce’s National Institute of Standards and Technology, or NIST, selected four post-quantum computing encryption algorithms to replace algorithms such as RSA, Diffie-Hellman, and Elliptic Curve Diffie-Hellman, which cannot withstand attacks from a quantum computer.
In the same step, NIST has developed four additional algorithms as potential alternatives pending further testing in the hope that one or more of them will also be suitable cryptographic alternatives in the post-quantum world. The new attack breaks SIKE, one of the last four additional algorithms. The attack has no effect on the four PQC algorithms chosen by NIST as the approved standards, all of which are based on completely different mathematical techniques than SIKE.
SIKE – short for Supersingular Isogeny Key Encapsulation – is now likely to drop out of the race thanks to research published over the weekend by researchers from the Computer Security and Industrial Cryptography Group at KU Leuven. The paper, titled Effective Key Recovery Attack on SIDH (Initial Version), described a technique that uses complex mathematics and a single traditional computer to recover cryptographic keys that protect SIKE-protected transactions. The whole process takes about an hour.
“It is clear that the recently revealed vulnerability is a huge blow to SIKE,” David Gao, a professor at the University of Waterloo and co-inventor of SIKE, wrote in an email. “The attack is really unexpected.”
The advent of public-key cryptography in the 1970s was a major breakthrough because it allowed parties who had never met to securely trade encrypted material that an adversary could not crack. Public key cryptography is based on asymmetric keys, with one private key used for decrypting messages and a separate public key for encryption. Users make their public key widely available. As long as their private key remains secret, the system remains secure.
In practice, public key cryptography is often impractical, so many systems rely on key-encapsulation mechanisms, which allow parties that have not met before to jointly agree on a symmetric key over a public medium such as the Internet. In contrast to symmetric key algorithms, the key-encapsulation mechanisms in use today can be easily broken by quantum computers. Prior to the new attack, SIKE was believed to circumvent such vulnerabilities by using a complex mathematical structure known as a hypergenomic isogenic graph.
The cornerstone of SIKE is a protocol called SIDH, which is an acronym for Supersingular Isogeny Diffie-Hellman. The research paper published over the weekend shows SIDH’s exposure to a theory known as “glue and cleavage” developed by mathematician Ernst Kanye in 1997, as well as tools devised by fellow mathematicians Everett W. Howe, Frank Leprovost, and Bjorn Poonen in 2000. The new technique is based on what’s known as an “adaptive GPST attack,” described in a 2016 research paper. The computations behind the latest attack are certainly impenetrable for most non-mathematicians. Here’s as close as you can get:
Stephen Galbraith, a professor of mathematics at the University of Auckland and the letter “G” in the GPST adaptive attack, explained in a short message about a new attack. “SIDH auxiliary points have always been a potential nuisance and vulnerability, and they have been exploited for crash attacks, GPST adaptive attack, warp point attacks, etc.
Leaves Have a base curve and allow you have a request . Leaves It must be given such a presence of symmetry class with And the And the
A key aspect of SIDH is that one does not count directly, but as a composition of homogeneous of degree 3. In other words, there is a series of curves Connected to 3-isogenies.
Basically, as in GPST, the attack determines the mean curves Thus it finally defines the private key. in step The attack searches everything possible with brute force The magic component is a tool that shows which one is correct.
(The above are too simplistic, homophones Its attack is not a class 3 but a small force class of 3.)
More important than understanding mathematics, Jonathan Katz, an IEEE member and professor in the Department of Computer Science at the University of Maryland, wrote in an email: “The attack is completely classic, and it doesn’t require quantum computers at all.”