In the US In the government’s ongoing campaign to protect data in the age of quantum computers, a new and powerful attack that used a single conventional computer to completely break a fourth-round candidate highlights the risks of standardizing next-generation 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 elliptic curve Diffie-Hellman that cannot withstand attacks from a quantum computer.
In the same move, NIST developed four additional algorithms as potential replacements pending further testing, one or more of which may also be suitable encryption alternatives in a post-quantum world. The new attack breaks SIKE, one of the last four additional algorithms. The attack does not affect the four PQC algorithms chosen as NIST-approved standards, all of which rely on entirely different mathematical techniques than SIKE.
Getting fully SIKEd
SIKE—for short Supersingular isogeny key encapsulation— is no longer in effect, thanks to research published by researchers over the weekend Computer Security and Industrial Cryptography group at KU Leuven. The paper, titledAn Efficient Key Recovery Attack on SIDH (Preliminary Version),” described a technique that uses complex mathematics and a single traditional PC to recover encryption keys that protect SIKE-protected transactions. The entire process only takes about an hour. This feat made researchers Wouter Kastrick and Thomas Decreux eligible for a $50,000 reward from NIST.
“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 was really unexpected.”
The advent of public-key encryption in the 1970s was a major breakthrough, as it allowed parties who had never met to securely trade encrypted material that could not be broken by an adversary. Public-key encryption is based on asymmetric keys, a private key is used to decrypt messages and a separate public key is used for encrypting. Users make their public key widely available. As long as their private key is kept secret, the scheme is secure.
In practice, public-key cryptography can often be ineffective, so many systems rely on key encapsulation mechanisms, which allow parties who have never met before to jointly agree on a symmetric key through a public medium such as the Internet. Unlike symmetric-key algorithms, the key encapsulation mechanisms in use today are easily broken by quantum computers. SIKE, prior to the new attack, was thought to avoid such vulnerabilities by using a complex mathematical structure called a supersingular isogeny graph.
The cornerstone of SIKE is a protocol called SIDH, which stands for Supersingular Isogeny Diffie-Hellman. A research paper published over the weekend shows how SIDH is vulnerable to a theory of “glue-and-split” developed by mathematician Ernst Kani in 1997 and tools developed by fellow mathematicians Everett W. Howe, Frank Leprevost and Bjorn. Poonen in 2000. The new technology is based on the so-called “GPST Adaptive Attack”. 2016 paper. The math behind the latest attack is guaranteed to be impenetrable to most non-mathematicians. Here’s as close as you’re going to get:Unsolved Mystery Attack on Internet Cables in Paris
“This attack exploits the fact that SIDH has auxiliary points and knows the degree of latent isogeny” Steven GalbraithProfessor of Mathematics at the University of Auckland and “G” in the pro-GPST attack, explained in a Short writing On a new attack. “Support points in SIDH are always an irritant and a potential weakness, and they are used for fault attacks, GPST pro attack, torsion point attacks, etc.”
