A New Attack Easily Knocked Out a Potential Encryption Algorithm

In the U.S. government's 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 in standardizing the next generation of encryption

Last month, the US National Institute of Standards and Technology (NIST) selected four post-quantum-computing cryptanalysts to replace RSA, Diffie-Hellman, and elliptic curve Diffie-Hellman, which are unable to resist attacks from a quantum computer.

NIST advanced four more possible replacements pending further testing in hopes that one or more of them may 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.

It is getting totally snuffed.

SIKE is likely out of the running now that research from the Computer Security and Industrial Cryptography group at KU Leuven has been published. A paper titled "An Efficient Key Recovery Attack on SIDH (Preliminary Version)" 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. The researchers are eligible for a $50,000 reward from NIST.

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 people who had never met before to trade protected material. 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.

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 that is part of SIKE. A research paper published over the weekend shows how SIDH is vulnerable to a theorem known as "glue-and-split" and tools devised by mathematicians. The new technique builds on what is known as theGPST adaptive attack. 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 potential weakness.