In the US government’s ongoing campaign to protect data in the age of quantum computers, a new and powerful attack uses a single traditional computer to completely disrupt a candidate. The fourth highlighted 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 the Diffie-Hellman elliptic curve, which are not resistant to attacks from quantum computers.
In the same move, NIST has elevated four additional algorithms as potential alternatives pending further testing in the hope that one or more of them could also be cryptographic alternatives. relevant in the post-quantum world. The new attack breaks SIKE, which is one of four later added algorithms. The attack had no impact on the four PQC algorithms selected by NIST as the approved standard, all of which are based on completely different mathematical techniques from SIKE.
Get Full SIKed
SIKE — short for Super Isogeny Lock Packing—Which is now likely to come out of active status thanks to a study published over the weekend by researchers from Computer security and industrial cryptography group at KU Leuven. Article, titled 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 SIKE-protected transactions. The whole process only takes about an hour.
“The newly discovered weakness is clearly a blow to SIKE,” David Jao, a professor at the University of Waterloo and co-inventor of SIKE, wrote in an email. “The attack was really unexpected.”
The introduction of public-key encryption in the 1970s was a major breakthrough because it allowed never-before-seen parties to securely transact encrypted documents that an adversary could not break. Public key encryption is based on asymmetric keys, with a private key used to decrypt the message and a separate public key for encryption. Users provide their public keys widely. As long as their private key remains secret, the plan is safe.
In practice, public-key cryptography can often be difficult to use, so many systems are based on key encapsulation, which allows parties that have never met before to agree on a symmetric key over a single method. public facilities such as the Internet. In contrast to symmetric key algorithms, the key encapsulation mechanisms in use today are very vulnerable to quantum computers breaking. SIKE, prior to the new attack, is said to have avoided such vulnerabilities by using a complex mathematical structure known as a supernormal caste graph.
The foundation of SIKE is a protocol called SIDH, which stands for Supersingular Isogeny Diffie-Hellman. The research paper published over the weekend shows how susceptible SIDH is to a theorem known as “glue and division” developed by mathematician Ernst Kani in 1997, as well as other works. tool invented in 2000 by fellow mathematicians Everett W. Howe, Franck Lepr´evost, and Bjorn Poonen. The new technique builds on what is known as the “GPST adaptive attack”, described in 2016 paper. The math behind the latest attack is guaranteed to be impenetrable to most non-mathematicians. This is roughly what you will get:
“The attack exploits the fact that SIDH has known plug-ins and class secrecy,” Steven Galbraitha University of Auckland mathematics professor and “G” in GPST adaptive attack, explained in a write short about the new attack. “Plugins in SIDH have always been a pain point and a potential weakness, and they have been exploited for bug attacks, GPST adaptive attacks, twist point attacks, etc.
Let is the basis curve and let have orders . Let given such that there exists an equality level with , and
An important aspect of SIDH is that it does not compute directly, but as components of tertiary isotopes. In other words, there is a series of curves linked by 3-isogenies.
Basically, like in GPST, the attack determines the intermediate curves and thus finally determine the private key. At step the attack makes a rough search all possible and the magic component is a utility that tells which one is right.
(The above is oversimplified, the equality in the attack not at level 3 but at a level of a small power of 3.)
More important than understanding the math, Jonathan Katz, an IEEE Fellow and professor in the department of computer science at the University of Maryland, wrote in an email: “The attack is completely classical and does not require a quantum calculator. death”.