A few months back I came across this blog post by Steve Weis which can only equate to a lost treasure hunt of the security industry! The lore goes as follows:
Since the inception of ECDSA there have been controversies and debate especially around the seed values used at its foundation.
These seed values were chosen by Jerry Solinas, a NSA employee collaborating with the authors of the ECDSA RFC at the time, and it was unearthed that he didn’t choose this at random and instead used a phrase.
The phrase was allegedly just a SHA-1 hash of the phrase “Jerry deserves a raise…”.
Jerry has since forgotten the exact phrase and had even attempted to uncover it himself without success. Unfortunately Jerry died in early 2023.
So the question remains, what was the original phrase? Even prominent cryptographers and security folks have asked and even set cash bounties. Now my curiosity has also peaked!
The Approach
According to the blog post, Jerry simply SHA-1 hashed an English sentence along with a discrete number of digits to generate the ECDSA seed values. Something like:
seed = SHA-1("Jerry and Bob need raises123")
Since the format is pretty simple, and most of the value is dictionary words, I figure it’ll be a small enough search space for me to run a brute-force and try all possible ways to say the phrase and add incrementing permutations of char values and SHA-1 hash it to see it’ll match any of the ECDSA seed values.
Using OpenAI seems like the easiest way find out all the ways to say “Jerry and Bob need raises”.
For the additional values, I’ll recursively generate all permutations of chars from the full ASCII values and attach it both to the front, back, and front/back of the phrase.
Even if the search space is truly this narrow it’ll take forever to run through this brute-force in series. So I’ll spawn threads for each of the phrases that’ll run through all permutations, to make the effort multithreaded.
And I put together the following brute force golang application!
The Results
I ran the above application for 48 hours on a 1 OCPU E2 VM in my free tier account on Oracle Cloud. And unfortunately I was unable to uncover any of the ECDSA seeds 😢. But I made a few interesting observations.
After the first 200 or so the phrases being returned by OpenAI were getting longer and wordier making their likeliness to be the original phrase less plausible. Placing restrictions on the phrases returned, like asking OpenAI to reducing word count, only caused it to give-up earlier.
The strategy for the additional values needs to be further thought out like increasing the max length to beyond 3 and trying attempts where I sprinkle it through the phrase than just pre-pending/post-pending.
Also obviously I’ll need a beefier hardware, the 1 OCPU was being nearly fully utilized at almost 98% for the entire 48 hours!
So I’m kinda out of ideas at this point 😀. I can say for sure the phrase used to generate the ECDSA seed values is not as straightforward as the legend indicates. But I’m still curious to solve it, so would love to hear feedback!