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

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

Getty Images

reader comments

73 with 51 posters participating

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

In the same move, NIST advanced four additional algorithms as potential replacements pending further testing in hopes 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 latter four additional algorithms. The attack has no impact on the four PQC algorithms selected by NIST as approved standards, all of which rely on completely different mathematical techniques than SIKE.

Getting totally SIKEd

SIKE—short for Supersingular Isogeny Key Encapsulation—is now likely out of the running thanks to research that was published over the weekend by researchers from the Computer Security and Industrial Cryptography group at KU Leuven. The paper, titled An Efficient Key Recovery Attack on SIDH (Preliminary Version), described a technique that uses complex mathematics and a single traditional PC to recover the encryption keys protecting the SIKE-protected transactions. The entire process requires only about an hour’s time.

“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 encryption in the 1970s was a major breakthrough because it allowed parties who had never met to securely trade encrypted material that couldn’t 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 encrypting. Users make their public key widely available. As long as their private key remains secret, the scheme remains secure.

2016 paper. The math behind the latest attack is guaranteed to be impenetrable to most non-mathematicians. Here’s about as close as you’re going to get:

“The attack exploits the fact that SIDH has auxiliary points and that the degree of the secret isogeny is known,” Steven Galbraith, a University of Auckland mathematics professor and the “G” in the GPST adaptive attack, explained in a short writeup on the new attack. “The auxiliary points in SIDH have always been an annoyance and a potential weakness, and they have been exploited for fault attacks, the GPST adaptive attack, torsion point attacks, etc.

He continued:

Let E_0 be the base curve and let P_0, Q_0 in E_0 have order 2^a. Let E, P, Q be given such that there exists an isogeny phi of degree 3^b with phi : E_0 to E, phi(P_0) = P, and phi(Q_0) = Q.

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

Essentially, like in GPST, the attack determines the intermediate curves E_i and hence eventually determines the private key. At step i the attack does a brute-force search of all possible E_i to E_i+1, and the magic ingredient is a gadget that shows which one is correct.

(The above is over-simplified, the isogenies E_i to E_i+1 in the attack are not of degree 3 but of degree a small power of 3.)

More important than understanding the math, Jonathan Katz, an IEEE Member and professor in the department of computer science at the University of Maryland, wrote in an email: “the attack is entirely classical, and does not require quantum computers at all.”

Article Tags:
Article Categories:
Technology · Uncategorized