In the US government’s ongoing campaign to protect data in the age of quantum computers, a powerful new attack that used a single traditional computer to completely break a fourth-round candidate highlights the risks involved in standardizing the next generation of encryption 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 the Diffie-Hellman elliptic curve, which they cannot withstand attacks from a quantum computer.
In the same move, NIST put forward four additional algorithms as potential replacements pending further testing in the hope that one or more of them may also be suitable encryption alternatives in a post-quantum world. The new attack breaks SIKE, which is one of the last four additional algorithms. The attack has no impact on the four PQC algorithms selected by NIST as approved standards, all of which are based on completely different mathematical techniques than SIKE.
Get totally SIKEd
SIKE, short for Supersingular Isogeny Key Encapsulation, is now probably out of circulation thanks to research published over the weekend by researchers at KU Leuven’s Computer Security and Industrial Cryptography group. The paper, titled An Efficient Key Recovery Attack on SIDH (preview), described a technique that uses complex mathematics and a single traditional PC to recover the encryption keys that protect SIKE-protected transactions. The entire process requires only about an hour.
“The newly discovered weakness is clearly a huge blow to SIKE,” David Jao, 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 encryption in the 1970s was a breakthrough because it allowed parties who had never met to securely exchange encrypted material that an adversary could not crack. Public key encryption is based on asymmetric keys, with a private key used to decrypt messages and a separate public key used to encrypt. Users make their public key widely available. As long as your private key remains secret, the scheme remains secure.
In practice, public key cryptography can often be unwieldy, so many systems rely on key encapsulation mechanisms, which allow parties that have never met before to jointly agree on a symmetric key on a public medium. like the internet. In contrast to symmetric key algorithms, key encapsulation mechanisms in use today are easily cracked by quantum computers. SIKE, before the new attack, was thought to prevent such vulnerabilities by using a complex mathematical construct known as a supersingular isogeny graph.
The cornerstone of SIKE is a protocol called SIDH, short for Supersingular Isogeny Diffie-Hellman. The research paper published over the weekend shows how SIDH is vulnerable to a theorem known as “glue and divide” developed by mathematician Ernst Kani in 1997, as well as tools devised by fellow mathematicians Everett W. Howe, Franck Lepr´evost, and Bjorn Poonen in 2000. The new technique is based on what is known as “GPST adaptive attack”, described in a 2016 paper. The mathematics behind the latest attack is guaranteed to be impenetrable to most users. not mathematicians. This is as close as you’re going to get:
“The attack exploits the fact that SIDH has helper points and that the degree of the secret isogeny is known,” explained Steven Galbraith, professor of mathematics at the University of Auckland and the “G” in the GPST adaptive attack, in a brief article about the new attack. “Auxiliary points in SIDH have always been a nuisance and potential weakness, and have been exploited for flaw attacks, the adaptive GPST attack, twist point attacks, etc.
Let be the base curve and be have order . Let occur such that there is an isogeny degree with , Y
A key aspect of SIDH is that one does not calculate directly, but as a composition of isogenies of degree 3. In other words, there is a sequence of curves connected by 3-isogenies.
Essentially, as in GPST, the attack determines the intermediate curves and thus finally determines the private key. step by step the attack does a brute force search of all possible and the magic ingredient is a gadget that shows which one is correct.
(The above is oversimplified, the isogenies in attack they are not grade 3 but grade a small power of 3.)
More important than understanding the math, Jonathan Katz, an IEEE fellow and professor in the computer science department at the University of Maryland, wrote in an email: “The attack is completely classical and doesn’t require quantum computers at all.”