What news from AWS re:Invent last week will have the most impact on you?
Amazon Q, an AI chatbot for explaining how AWS works.
Super-fast S3 Express storage.
New Graviton 4 processor instances.
Emily Freeman leaving AWS.
I don't use AWS, so none of this will affect me.
Security / Tech Life

Crack a 1999 NSA Cryptography Standard and Win a Bounty

A former Cloudflare/Golang cryptographer has offered a $12,288 "bounty" for finding the seeds of five elliptic curves produced by the NSA in 1999 that have since become an industry standard.
Oct 22nd, 2023 6:00am by
Featued image for: Crack a 1999 NSA Cryptography Standard and Win a Bounty
Feature image by Uwe Baumann from Pixabay.

Filippo Valsorda describes it as “a call to arms” to “help fill in a page of cryptographic history.”

The former Cloudflare/Golang cryptographer has announced a $12,288 “bounty” for finding the seeds of five elliptic curves produced by the NSA in 1999 that have since become an industry standard. Valsorda calls them the “elliptic curves that power much of modern cryptography,” noting that they’re used, among other things, for the certificates securing millions of websites. They’ve been augmented over the decades with even more utility-enhancing formulas and interfaces.

As Valsorda puts it, “They’re a big deal.”

But was there a common English phrase used to create this foundational sequence? Valsorda says its creator left behind “a cryptographic mystery, some conspiracy theories, and an historical password cracking challenge.” And he’s calling on the larger internet community to try to solve it.

Or as Valsorda put it on the social networking service formerly known as Twitter, “Do you have a bunch of GPUs and passphrase brute-forcing experience? Crack the NSA’s five SHA-1 hashes at the heart of NIST’s elliptic curves, solve a cryptographic mystery, and earn $8k (tripled if donated to charity).”

You can win half the bounty — walking away with $6,144 — just by correctly submitting one of the five seeds, according to Valsorda’s site. (Since “Even one would make history.”) The other half of the bounty goes to whoever submits all five.

And Valsorda will triple payout amounts if the winner names a U.S. 501(c)(3) charity to receive the money. (“We reserve the right to veto charity choices dramatically incompatible with our values, but we won’t be jerks about it.”)

That’s a $18,432 donation for finding just one of the seeds — and a $36,864 donation for finding all five. (Valsorda is putting up some of the money himself — aided by “generous matchers”)

But more importantly? It’s a chance to write yourself into the history of cryptography itself…

Codes of Yesteryear

It all started in September, when Steve Weis, who is both a cryptographer and a principal software engineer at Databricks, published a thought-provoking blog post. Weis notes the 1999 parameters are “the most widely used elliptic curve cryptography standard” (adopted in 2000 by the U.S. Department of Commerce’s official National Institute of Standards and Technology.)

But “Revelations of NSA interference in cryptographic standards like Dual_EC_DRBG led to speculation of whether the NIST curve seeds could have been intentionally chosen with a weakness or backdoor known only to the NSA.” The blog post notes at least one person raising this suspicion in a 1999 post to a Usenet discussion group about cryptography, and a more recent paper published in 2015 by math professors Neal Koblitz and Alfred Menezes.

Professor Menezes told Weis he’d been given the seeds as early as 1997 by long-time NSA employee Jerry Solinas (known for authoring several cryptography standards). But Weis adds “Unfortunately, Dr. Solinas died in early 2023 without publicly saying how the curve seeds were generated.” Yet Weis has uncovered some tantalizing clues. One of Solinas’s contemporaries said that around 2013, Solinas had confided that the seed was something like…

SEED = SHA1(“Jerry deserves a raise.”)

But Solinas had revealed even more, suggesting that the seed might’ve been lost even to Solinas himself. “After he did the work, his machine was replaced or upgraded, and the actual phrase that he used was lost,” Weis writes. “When the controversy first came up, Jerry tried every phrase that he could think of that was similar to this, but none matched.”

Weis adds that after publishing his blog post, “a fourth person came forward saying that in 2013, Dr. Solinas recalled to them that the seed phrase had two names in it, like ‘Give Alice and Bob a raise.'” Another source claimed Solinas told them the phrase included an arbitrary number that changed with each block of text encrypted. Since then Weis has even tried requesting any documentation under the Freedom of Information Act. (“NIST claimed they had no documentation and the NSA ceased responding.”)

This leaves what Weis calls “a long shot chance”: trying “to brute force guess short English phrases and see if any collide with a seed from the specifications.”

And of course, this inspired Valsorda…

NSA Interference?

Weis succinctly summarizes what’s at stake here. “Whenever a controversy about the NSA arises among the cryptographic community, it resurfaces a question that has been open for 25 years: How were the NIST ECDSA curve parameters generated?”

Valsorda is skeptical that the NSA repeated its interference the way they’d done with the Dual_EC_DRBG standard (noting that earlier standard’s compromised design “immediately stuck out like a sore thumb and library authors had to be paid to implement it”.) Valsorda’s blog post points out that that incident “suggests the NSA is kinda bad at backdoors, not magical.” But he believes that because of the speculation, “some fear, uncertainty, and doubt persists around the otherwise pretty good NIST curves that would be good to clear up…”

The effort is continuing. On Oct. 8 Valsorda updated the post to include a link to a massive list of nearly 12,000 potential target hashes “that cover 99% of the probability space for each of the prime order curve seeds.” Valsorda wrote on Mastodon that the list was “based on the hypothesis that maybe instead of increasing a counter, the seed/hash itself was increased until a valid one was found.”

And of course, there’s been a lively discussion on Valsorda’s Mastodon feed.

@jerry absolutely deserves a raise.

But mixed in with the comical banter, Valsorda has answered some important questions — like the user who asked “For the uninformed, the seeds being found won’t impact the security of using these curves at all?”

Valsorda’s answer? “Nope, if anything it would make them more trustworthy, although most cryptographers I know don’t think that’s necessary.”

Valsorda also explained how standardizing on these curves allowed more speedy and accurate encryption than self-generated curves — and “lets us write well optimized, safer implementations.” While you could try generating your own original encryption parameters, “the security margin you get from forcing an attacker to crack a few thousand parameters instead of one is just a dozen bits.”

And so back on his personal blog, Valsorda is now cheering on an unseen internet community who may finally solve this long-standing mystery. “We don’t actually care how you find the seeds,” Valsorda wrote. “It can be brute forcing, clever guessing, sleuth work tracking down NSA employees (don’t get arrested), or even recovering that old backup of when you used to work at NIST. If you don’t want us to, we won’t ask questions.

“May the hashrate be ever in your favor, and let’s fill out a page of cryptographic history.”


Group Created with Sketch.
THE NEW STACK UPDATE A newsletter digest of the week’s most important stories & analyses.