Crack a 1999 NSA Cryptography Standard and Win a Bounty – The New Stack
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 theyre used, among other things, for the certificates securing millions of websites. Theyve been augmented over the decades with even more utility-enhancing formulas and interfaces.
As Valsorda puts it, Theyre 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 hes 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 NSAs five SHA-1 hashes at the heart of NISTs 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 Valsordas 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 wont be jerks about it.)
Thats 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? Its a chance to write yourself into the history of cryptography itself
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 Commerces 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 hed 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 Solinass 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 mightve 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
Weis succinctly summarizes whats 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 theyd done with the Dual_EC_DRBG standard (noting that earlier standards compromised design immediately stuck out like a sore thumb and library authors had to be paid to implement it.) Valsordas 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, theres been a lively discussion on Valsordas 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 wont impact the security of using these curves at all?
Valsordas answer? Nope, if anything it would make them more trustworthy, although most cryptographers I know dont think thats 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 dont actually care how you find the seeds, Valsorda wrote. It can be brute forcing, clever guessing, sleuth work tracking down NSA employees (dont get arrested), or even recovering that old backup of when you used to work at NIST. If you dont want us to, we wont ask questions.
May the hashrate be ever in your favor, and lets fill out a page of cryptographic history.
See the original post here:
Crack a 1999 NSA Cryptography Standard and Win a Bounty - The New Stack