IN USA government’s ongoing campaign to protect data in the age of quantum computers, a new and powerful attack that used a single traditional computer to completely break a fourth-round candidate highlights the risks associated with standardizing the next generation of encryption algorithms.
Last month, the US Commerce Department chose the National Institute of Standards and Technology, or NIST four post-quantum-computing encryption algorithms to replace algorithms such as RSA, Diffie-Hellman and elliptic curve Diffie-Hellman, which are unable to withstand attacks by a quantum computer.
In the same move, NIST advanced 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 chosen by NIST as approved standards, all of which rely on completely different mathematical techniques than SIKE.
Gets totally SIKEd
SIKE – abbreviation for Supersingular Isogeny Key Encapsulation-is now likely out of business, thanks to research published over the weekend by researchers from Computer security and industrial cryptography group at KU Leuven. The newspaper entitled “An Effective Key Recovery Attack on SIDH (Preliminary Version),” described a technique that uses complex mathematics and a single traditional PC to recover the encryption keys that protect the SIKE-protected transactions. The whole process only takes about an hour. The feat makes the researchers, Wouter Castryck and Thomas Decru, eligible for a $50,000 reward from NIST.
“The newly uncovered weakness is clearly a major 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 cryptography in the 1970s was a major breakthrough because it allowed parties who had never met to transact 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.
In practice, public key cryptography can often be unwieldy, 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, key encapsulation mechanisms in use 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 isogenigraph.
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,” developed by mathematician Ernst Kani in 1997, as well as tools devised by fellow mathematicians Everett W. Howe, Franck Leprévost and Bjorn Poonen in 2000. The new technique is based on what is known as “GPST adaptive attack”, described in a 2016 paper. The math behind the latest attack is guaranteed to be impenetrable to most non-mathematicians. Here’s about as close as you’ll get:
“The attack exploits the fact that SIDH has auxiliary points and that the degree of the secret isogeny is known,” Steven Galbraitha mathematics professor at the University of Auckland and the “G” of the adaptive GPST attack, explained in a short writing on the new attack. “The auxiliary points in SIDH have always been an annoyance and a potential weakness, and they have been exploited for bug attacks, the adaptive GPST attack, torsion point attacks, etc.”