Post-quantum encryption contender is taken out by single-core PC and 1 hour

In the US 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 involved.

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 like RSA, Diffie-Hellman, and elliptic curve Diffie-Hellman, which are unable to withstand attacks from a quantum computer.

NIST advanced four more possible replacements pending further testing in hopes that one or more of them may also be suitable alternatives in a post-quantum world. SIKE is one of the other four additional algorithms. There is no impact on the NIST approved standards that use completely different mathematical techniques than the ones attacked.

Getting totally SIKEd

The research that was published over the weekend by researchers from the Computer Security and Industrial Cryptography group at KU Leuven is believed to have ended SIKE's chances. A paper titled An Efficient Key Recovery Attack on SIDH describes a technique that uses complex mathematics and a single traditional PC to recover the encryption keys protecting the SIKE-protected transactions. It takes about an hour to complete the process.

David Jao, a professor at the University of Waterloo and co-inventor of SIKE, said in an email that the newly uncovered weakness was a major blow to the project. The attack is completely unforeseen.

The advent of public key encryption in the 1970s made it possible for parties who had never met to securely trade material that couldn't be broken by an adversary. A private key and a public key are used for public key encryption. The public key of users is widely available. The scheme is secure as long as the private key is not public.

Advertisement

Key encapsulation mechanisms allow parties who have never met before to agree on a symmetric key over a public medium such as the Internet. Key encapsulation mechanisms are easy to break by quantum computers. SIKE was thought to avoid vulnerabilities by using a supersingular isogeny graph.

SIDH is a protocol used in SIKE. A research paper published over the weekend shows how SIDH is vulnerable to a theorem known as "glue-and-split". There is a new technique called the "GPST adaptive attack" described in a 2016 paper. Most non-mathematicians won't be able to understand the math behind the latest attack. This is about as close as you will get.

The new attack exploits the fact that SIDH has auxiliary points and that the degree of the secret isogeny is known. The auxiliary points in SIDH have always been an annoyance and a weakness.

He said something else.

Let be the base curve and let have order . Let be given such that there exists an isogeny of degree with , , and

A key aspect of SIDH is that one does not compute directly, but as a composition of isogenies of degree 3. In other words, there is a sequence of curves connected by 3-isogenies.

Essentially, like in GPST, the attack determines the intermediate curves and hence eventually determines the private key. At 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 over-simplified, the isogenies in the attack are not of degree 3 but of degree a small power of 3.)

The professor of computer science at the University of Maryland wrote in an email that the attack was classical and didn't require quantum computers.