‘Post-Quantum’ Cryptography Scheme Is Cracked on a Laptop
Kristina Armitage/Quanta Magazine
Introduction
If today’s cryptography protocols were to fail, it would be impossible to secure online connections — to send confidential messages, make secure financial transactions, or authenticate data. Anyone could access anything; anyone could pretend to be anyone. The digital economy would collapse.
When (or if) a fully functional quantum computer becomes available, that’s precisely what could happen. As a result, in 2017 the U.S. government’s National Institute of Standards and Technology (NIST) launched an international competition to find the best ways to achieve “post-quantum” cryptography.
Last month, the agency selected its first group of winners: four protocols that, with some revision, will be deployed as a quantum shield. It also announced four additional candidates still under consideration.
Then on July 30, a pair of researchers revealed that they had broken one of those candidates in an hour on a laptop. (Since then, others have made the attack even faster, breaking the protocol in a matter of minutes.) “An attack that’s so dramatic and powerful … was quite a shock,” said Steven Galbraith, a mathematician and computer scientist at the University of Auckland in New Zealand. Not only was the mathematics underlying the attack surprising, but it reduced the (much-needed) diversity of post-quantum cryptography — eliminating an encryption protocol that worked very differently from the vast majority of schemes in the NIST competition.
“It’s a bit of a bummer,” said Christopher Peikert, a cryptographer at the University of Michigan.
The results have left the post-quantum cryptography community both shaken and encouraged. Shaken, because this attack (and another from a previous round of the competition) suddenly turned what looked like a digital steel door into wet newspaper. “It came out of the blue,” said Dustin Moody, one of the mathematicians leading the NIST standardization effort. But if a cryptographic scheme is going to get broken, it’s best if it happens well before it’s being used in the wild. “There’s many emotions that go through you,” said David Jao, a mathematician at the University of Waterloo in Canada who, along with IBM researcher Luca De Feo, proposed the protocol in 2011. Certainly surprise and disappointment are among them. “But also,” Jao added, “at least it got broken now.”
Secret Walks Among Curves
Jao and De Feo had seen an opportunity for a cryptographic system that was both similar to and suitably distinct from well-known protocols. Their scheme, called the supersingular isogeny Diffie-Hellman protocol (SIDH), dealt with elliptic curves — the same mathematical objects used in one of the most widespread types of cryptography deployed today. But it used them in a completely different way. It was also the most compact scheme that NIST was considering (with the trade-off that it was slower than many of the other candidates).
And “mathematically, it’s really elegant,” said Jao. “At the time, it seemed like a beautiful idea.”
Merrill Sherman/Quanta Magazine
Say two parties, Alice and Bob, want to exchange a message in secret, even under the watchful gaze of a potential attacker. They begin with a collection of points connected by edges called a graph. Each point represents a different elliptic curve. If you can transform one curve into another in a particular way (via a map called an isogeny), draw an edge between the pair of points. The resulting graph is huge and easy to get lost in: If you take a relatively short walk along its edges, you’ll end up somewhere that looks completely random.
Alice’s and Bob’s graphs have all the same points, but the edges are different — they’re defined by different isogenies. Alice and Bob start at the same point, and they each hop along random edges on their own graph, keeping track of their path from one point to another. Each then publishes their ending location but keeps their path secret.
Now they swap places: Alice goes to Bob’s final point, and Bob to Alice’s. Each repeats their secret walk. They do this in such a way that they will both end up at the same point.
This location has been found in secret, so Alice and Bob can use it as their secret key — information that allows them to encrypt and decrypt each other’s messages securely. Even if an attacker sees the intermediate points that Alice and Bob send each other, they don’t know Alice’s or Bob’s secret walk, so they cannot figure out that final endpoint.
But to make SIDH work, Alice and Bob also need to exchange some additional information about their walks. That extra information is what led to SIDH’s downfall.
A New Twist on Old Mathematics
Thomas Decru didn’t set out to break SIDH. He was trying to build on it — to generalize the method to enhance another type of cryptography. That didn’t work out, but it sparked an idea: His approach might be useful for attacking SIDH. And so he approached Wouter Castryck, his colleague at the Catholic University of Leuven in Belgium and one of his former doctoral advisers, and the two dived into the relevant literature.
They stumbled across a paper published by the mathematician Ernst Kani in 1997. In it was a theorem that “was almost immediately applicable to SIDH,” Castryck said. “I think once we realized that … the attack came quite quickly, in one or two days.”
Ultimately, to recover Alice’s secret walk (and therefore the shared key), Castryck and Decru examined the product of two elliptic curves — Alice’s starting curve and the curve she sent publicly to Bob. That combination produces a kind of surface called an abelian surface. They then used these abelian surfaces, Kani’s theorem (which relates abelian surfaces to elliptic curves), and the extra information Alice gave Bob to uncover each step Alice took.
“It’s almost like a homing signal that lets you lock in on [certain abelian surfaces],” Jao said. “And that signal tells you that this is the way you should go to take the next step to find the correct [secret walk].” Which led them straight to Alice and Bob’s shared key.
“It’s a very unexpected approach, going to more complicated objects to derive results about the simpler object,” Jao said.
“I was very excited to see this technique being used,” said Kristin Lauter, a mathematician and cryptographer at Meta AI Research who not only helped develop isogeny-based cryptography but has also worked on abelian surfaces. “So shame on me for not thinking about it as a way to break [it].”
Castryck and Decru’s attack broke the lowest-security version of the SIDH protocol in 62 minutes and the highest-security level in just under a day. Then, shortly afterward, another expert tweaked the attack so that it took just 10 minutes to break the low-security version and a couple hours to break the high-security one. More general attacks posted in the past few weeks make it unlikely that SIDH can be salvaged.
“It was a special feeling,” Castryck said, albeit a bittersweet one. “We killed one of our favorite systems.”
A Watershed Moment
It’s impossible to guarantee that a system is unconditionally secure. Instead, cryptographers rely on enough time passing and enough people trying to break the problem to feel confident. “That does not mean that you won’t wake up tomorrow and find that somebody has found a new algorithm to do it,” said Jeffrey Hoffstein, a mathematician at Brown University.
Hence why competitions like NIST’s are so important. In the previous round of the NIST competition, Ward Beullens, a cryptographer at IBM, devised an attack that broke a scheme called Rainbow in a weekend. Like Castryck and Decru, he was only able to stage his attack after he viewed the underlying mathematical problem from a different angle. And like the attack on SIDH, this one broke a system that relied on different mathematics than most proposed post-quantum protocols.
“The recent attacks were a watershed moment,” said Thomas Prest, a cryptographer at the startup PQShield. They highlight how difficult post-quantum cryptography is, and how much analysis might be needed to study the security of various systems. “A mathematical object may have no obvious structure in one perspective, and have an exploitable structure in another,” he said. “The hard part is to identify the right new perspective.”
