Getty Images
In the US government’s ongoing campaign to protect data in the age of quantum computing, a new and powerful attack that used a traditional computer to completely crack a fourth-round candidate highlights the risks associated with standardizing the next generation of encryption algorithms.
Last month, the U.S. 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 are unable to to withstand attacks by a quantum computer.
In the same move, NIST has developed 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 had no impact on the four PQC algorithms selected by NIST as approved standards, all of which rely on completely different mathematical techniques than SIKE.
Getting totally SIKED
SIKE – short for Supersingular Isogeny Key Encapsulation – is now probably out of business thanks to research published over the weekend by researchers from the Computer Security and Industrial Cryptography group at KU Leuven. The paper, titled An Effective Key Recovery Attack on SIDH (preview), describes a technique that uses complex mathematics and a traditional computer to recover the encryption keys protecting SIKE-secured transactions. The whole process only takes about an hour.
“The newly discovered weakness is clearly a major blow to SIKE,” David Zhao, 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 major breakthrough because it allowed parties who had never met to trade securely encrypted material that could not be broken by an adversary. Public-key encryption relies on asymmetric keys, with one private key used to decrypt messages and a separate public key for encryption. Users make their public key widely available. As long as their private key remains secret, the scheme remains secure.
Advertising
In practice, public-key cryptography can often be cumbersome, so many systems rely on key encapsulation mechanisms that allow parties who have never met before to jointly agree on a symmetric key over a public medium such as the Internet. Unlike symmetric key algorithms, the key encapsulation mechanisms used today are easily broken by quantum computers. SIKE, before the new attack, was believed to avoid such vulnerabilities by using a complex mathematical construct known as a supersingular isogenic 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-split” theorem developed by mathematician Ernst Kahn in 1997, as well as tools created by fellow mathematicians Everett W. Howe, Frank Leprevost, and Bjorn Poonen in 2000. The new technique is based on what’s known as a “GPST adaptive attack,” described in a 2016 paper. The math behind the latter attack is guaranteed to be impenetrable to most non-mathematicians. Here’s the closest you’ll get:
“The attack exploits the fact that SIDH has auxiliary points and that the degree of covert isogeny is known,” explained Stephen Galbraith, a professor of mathematics at the University of Auckland and the “G” in the adaptive GPST attack, in a briefing on the new attack. “Auxiliary points in SIDH have always been an annoyance and potential weakness and have been exploited for bug attacks, GPST adaptive attack, torsion point attacks, etc.
He continued:
Let be the base curve and have a row. Let be given such that there exists an isogeny of degree with , , and
A key aspect of SIDH is that it is not calculated directly, but as a composition of isogenies of degree 3. In other words, there is a sequence of curves associated with 3-isogenies.
Essentially, like GPST, the attack determines the intermediate curves and therefore ultimately determines the private key. On a step, the attack performs a rough search for all possible , and the magic ingredient is a widget that shows which is the correct one.
(The above is an oversimplification, the attack isogenies are not of degree 3, but of degree less than 3.)
More important than understanding the math, 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 entirely classical and does not require quantum computers at all.”
Add Comment