We care about your data, and we'd like to use cookies to give you a smooth browsing experience. Please agree and read more about our privacy policy.
Quanta Homepage
  • Physics
  • Mathematics
  • Biology
  • Computer Science
  • Topics
  • Archive
‘Post-Quantum’ Cryptography Scheme Is Cracked on a Laptop
Comment
Read Later
Share
Facebook
Twitter
Copied!
Copy link
Email
Pocket
Reddit
Ycombinator
Flipboard
    • Comment
      Comments
    • Read Later
    cryptography

    ‘Post-Quantum’ Cryptography Scheme Is Cracked on a Laptop

    By Jordana Cepelewicz

    August 24, 2022

    Two researchers have broken an encryption protocol that many saw as a promising defense against the power of quantum computing.
    Comment
    Read Later

    Kristina Armitage/Quanta Magazine

    By Jordana Cepelewicz

    Senior Writer


    August 24, 2022


    View PDF/Print Mode
    Abstractions blogcomputer sciencecomputer securitycryptographyelliptic curvesmathematicsquantum computingAll topics
    Watch and Learn Watch and Learn

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

    Share this article
    Facebook
    Twitter
    Copied!
    Copy link
    Email
    Pocket
    Reddit
    Ycombinator
    Flipboard

    Newsletter

    Get Quanta Magazine delivered to your inbox

    Recent newsletters

    Merrill Sherman/Quanta Magazine

    Introduction

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

    By Jordana Cepelewicz

    Senior Writer


    August 24, 2022


    View PDF/Print Mode
    Abstractions blogcomputer sciencecomputer securitycryptographyelliptic curvesmathematicsquantum computingAll topics
    Watch and Learn Watch and Learn
    Share this article
    Facebook
    Twitter
    Copied!
    Copy link
    Email
    Pocket
    Reddit
    Ycombinator
    Flipboard

    Newsletter

    Get Quanta Magazine delivered to your inbox

    Recent newsletters
    The Quanta Newsletter

    Get highlights of the most important news delivered to your email inbox

    Recent newsletters

    Comment on this article

    Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation. Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected. Moderators are staffed during regular business hours (New York time) and can only accept comments written in English. 

    An illustration of a blue swirling galaxy inside an amillary sphere. A black hole appears in the center.

    Next article

    What Drives Galaxies? The Milky Way’s Black Hole May Be the Key.
    Quanta Homepage
    Facebook
    Twitter
    Youtube
    Instagram

    • About Quanta
    • Archive
    • Contact Us
    • Terms & Conditions
    • Privacy Policy
    • Simons Foundation
    All Rights Reserved © 2023