Algorithm in U.S. Government Test Hacked in Under an Hour with Unique Mathematical Theorem

A pair of Belgian researchers reportedly hacked an algorithm selected as part of a U.S. government security test this summer in less than one hour, thanks to a special theorem developed decades ago by a Canadian mathematician.

Back in July, a $50,000 prize was awarded in association with a cryptographic challenge originally announced by Microsoft, which invited researchers “to attempt to break the SIKE algorithm for two sets of toy parameters, and to share their findings with Microsoft.” A demonstration that generated two challenge instances took place during a live talk at a conference held on June 9, 2021, by the National Institute of Standards and Technology (NIST), which subsequently announced its selection of a second group of four candidates as part of a six-year competition aimed at testing the strength of quantum-resistant algorithms.

According to a statement from Queen’s University, a single personal computer successfully managed to hack the SIKE algorithm, which was one of those selected for additional evaluation in a fourth round of analysis. Remarkably, the feat was achieved with help from a decades-old mathematical theorem that served as the basis for the successful demonstration.

Working with the university’s Department of Mathematics and Statistics since 1986, Professor Ernst Kani, a researcher whose focus involves the use of algebraic geometry to help solve problems in mathematical number theory—a field known as arithmetic geometry—which addresses a variety of mathematical conundrums, some of which date back to antiquity.

Ernst Kani
Professor Ernst Kani (Credit: Queen’s University).

Specifically, it had been a focus on questions raised in the work of the Greek mathematician Diophantus, as well as pre-Calculus era French mathematician Pierre de Fermat, which served as the basis for the mathematics that would ultimately help crack the NIST’s algorithms.

Thomas Decru and Wouter Castryck, a pair of researchers with Belgium’s Katholieke Universiteit Leuven, succeeded in hacking the NIST’s algorithm with help from a theorem first produced by Kani back in 1997 based on such centuries-old questions, titled “The Number of Curves of Genus Two with Elliptic Differentials.”

However, Kani had not been attempting to produce a mathematical theorem with applications in cryptography at the time he initially published his work in the late 1990s. Rather, it had been an effort to advance out mathematical understanding of elliptical curves that Kani, along with German mathematician Gerhard Frey, had been focused on.

“Doing pure mathematics is an end by itself, so we don’t think of real-world applications,” Dr. Kani recently told the Queen Gazette. “But, later, many of those studies are useful for different purposes. Case in point, it would soon be realized that the duo’s work had a number of potential uses in the world of cryptography.

Kani says that since the problem he and Frey had been working to solve decades ago had virtually nothing to do with cryptography, he was surprised to hear that a successful algorithmic attack had relied in part on their work.

“It was quite ingenious, what they did there!” Kani said recently.

Apparently, Kani wasn’t the only one who was surprised. One of the co-authors of the SIKE algorithm successfully hacked by Castryk and Decru expressed similar sentiments about the way that genus two curves described in Kani’s original paper were successfully deployed to hack SIKE within an hour by gaining information about elliptic curves.

Although Kani and Frey hadn’t been attempting to do the same, he admits that the same mathematical principle “was precisely our original strategy in the 1980’s and 1990’s (and afterwards).”

Since cryptography relies on very advanced forms of mathematics—which includes the arithmetic geometry at the heart of his research—it isn’t particularly surprising that such theorems have proven very efficient in modern codebreaking applications.

Ultimately, Kani believes that future advancements in the field will require more than just mathematics alone.

“Computing experts and math experts have to work together to advance this field,” Kani said in a statement.

For those interested in exploring such concepts more deeply, Kani’s original 1997 paper, “The Number of Curves of Genus Two with Elliptic Differentials,” can be read in its entirety online.

Editor’s Note: This article has been updated to clarify that NIST did not produce or design any of the algorithms involved; NIST selected them as winners of a six-year competition. 

Micah Hanks is Editor-in-Chief and Co-Founder of The Debrief. Follow his work at micahhanks.com and on Twitter: @MicahHanks