Ride the Lightning

Post-Quantum Encryption Contender Blown Out of the Water in One Hour

August 4, 2022

Ars Technica reported on August 2 that, in our national 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 U.S. Department of Commerce’s National Institute of Standards and Technology (NIST) selected four post-quantum computing encryption algorithms to replace algorithms like RSA, Diffie-Hellman, and elliptic curve Diffie-Hellman, which cannot withstand attacks from a quantum computer.

Additionally, NIST advanced four additional algorithms as potential replacements pending further testing, hoping one or more of them might also be 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.

SIKE—short for Supersingular Isogeny Key Encapsulation—is apparently out of the running because of research that was published 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 feat makes the researchers, Wouter Castryck and Thomas Decru eligible for a $50,000 reward from NIST. Well earned – and a potential disaster avoided.

“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 cornerstone of SIKE is a protocol called SIDH, short for Supersingular Isogeny Diffie-Hellman. The research paper published over the weekend shows how SIDH is vulnerable to a theorem known as “glue-and-split” developed by mathematician Ernst Kani in 1997, as well as tools devised by fellow mathematicians Everett W. Howe, Franck Leprévost, and Bjorn Poonen in 2000. The new technique builds on what’s known as the “GPST adaptive attack,” described in a 2016 paper. The math behind the latest attack is guaranteed to be impenetrable to most non-mathematicians.

As a devout resister to learning mathematics, even the simplified description below is impenetrable to me, but it’s as close to being “simple” as this subject can apparently 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.)”

My failure to understand his words was complete and utter.

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.”

Ah, that I get.

SIKE is the second NIST-designated PQC candidate to be invalidated this year. In February, IBM post-doc researcher Ward Beullens published research that broke Rainbow, a cryptographic signature scheme with its security, according to Cryptomathic, “relying on the hardness of the problem of solving a large system of multivariate quadratic equations over a finite field.”

NIST’s PQC replacement campaign has been running for five years. Here’s a short fascinating history:

1st round (2017)—69 candidates

2nd round (2019)—26 surviving candidates

3rd round (2020)—7 finalists, 8 alternates

4th round (2022)—3 finalists and 1 alternate selected as standards. SIKE and three additional alternates advanced to a fourth round.

Rainbow fell during Round 3. SIKE had made it until Round 4.

Katz commented, “It is perhaps a bit concerning that this is the second example in the past six months of a scheme that made it to the 3rd round of the NIST review process before being completely broken using a classical algorithm. (The earlier example was Rainbow, which was broken in February.) Three of the four PQC schemes rely on relatively new assumptions whose exact difficulty is not well understood, so what the latest attack indicates is that we perhaps still need to be cautious/conservative with the standardization process going forward.”

After my utter failure to comprehend the subject matter of this article, I am relieved that I went to law school.

Hat tip to Dave Ries.

Sharon D. Nelson, Esq., President, Sensei Enterprises, Inc.
3975 University Drive, Suite 225, Fairfax, VA 22030
Email:   Phone: 703-359-0700
Digital Forensics/Cybersecurity/Information Technology
https://senseient.com
https://twitter.com/sharonnelsonesq
https://www.linkedin.com/in/sharondnelson
https://amazon.com/author/sharonnelson