NIST Elliptic Curve $12k bounty

In the late 1990s NIST developed a standard to cover elliptic curve cryptography called the “Digital Signature Standard”. A copy of the standard published in 2000 can be found here.

Background

There’s a lot of complicated maths involved but in simple terms the standard has "recommended elliptic curves for federal government use". These are called the P-Curves (P-192, P-224, P-256, P-384 and P-521) and are derived from a Pseudo-random seed values. To a certain degree the seed values don’t really matter so long as they are selected at random.

US National Security Agency

To help generate the seed values for the P-Curves NIST turned to the NSA and specifically their representative named Jerry Solinas. It has been said that Jerry created the seeds using the SHA-1 algorithm by taking sentences and hashing them. At face value and for the purposes of security this is sufficient to ensure its randomness to satisfy the standard. So far so good.

Conspiracy theories

The problem comes from the fact that the NSA (Jerry) did not record the original sentences used and given their history of allegedly ‘backdooring’ cryptographic technology, conspiracy theories abound. The main theory is that the sentences were selected to weaken the standard to such an extent that the NSA can break the encryption but no one else. It is some what unbelievable that NSA did not record the original sentences used to derive the seeds, but it does show they are human just like the rest of us. Jerry was probably expecting to re-generate suitable seeds when the time came but failed to revisit them – we’ve all been there.

Seed creation

There are some suggestions that the original sentences were something like “Give Jerry a raise”. Unfortunately, we can’t ask Jerry direct as he recently passed away (in 2023). Another variation is “Give Jerry and Laurie raises123”. Laurie was a colleague of Jerry’s at the NSA and was co-author of a cryptographic paper. It has been mentioned that the sentence may reference two people and include a counter at the end. As you can see the number of variations of this sentence are increasing as we delve deeper.

The bounty

This is where the bounty comes in. Filippo Valsorda, according to his web site, is a cryptography engineer with experience working at Google and Cloudflare. He with a number of other interested minds have announced a bounty for cracking five hashes. More details and some background can be found on Filippo Valsorda's website.

IT Security Locksmith approach

At IT Security Locksmith we are currently using our expertise to attempt to crack the original sentences generated by the NSA. While we have used our standard triage process for solving the challenge it is clear that the length and the complexity of the seed are proving robust. We have now switched to synthetic sentence generation combined with Artificial Intelligence to help drive some of the avenues of investigation.

Artificial Intelligence

The most interesting for us has been using AI:

1. To advise on the best computer language for string manipulation and synthetic sentence creation. There were various answers and we selected python – of which we have some but limited experience.
2. To generate python code for sentence creation to drive SHA-1 hash creation and comparison. While care is required to create the statement of requirements for the code, we have found AI to be remarkably good at code generation and diagnostics when it all goes wrong. It’s like having your in-house programmer sitting right next to you.
3. To locate more information on cryptography. This can obviously be done using google search or similar but what’s different is quality of the presentation. It was summarised, bulleted and to the point. No more searching and scrolling down looking for what’s the best. The best options are right in front of you – it’s as if the AI is your own personal assistant. This was used to create a list all probable colleagues of Jerry at the NSA for inclusion in the sentence creation.
4. To generate lists for use in sentence generation.
   a. A selection of common English word lists for input into the python code to create synthetic sentences
   b. List of US male and US female names
5. To suggest other options which quite frankly we are still trying to understand but look very interesting as further avenues to progress.

Conclusion

IT Security Locksmith are currently enjoying the challenge of breaking the seeds generated by the NSA. We are not convinced that the starting information from the NSA is correct given the number of attempts made to date and the myriad of English sentences attempted with up to 10 digits appended. Maybe we may simply need to wait 5 years to see if Quantum Computers can crack this conspiracy!

The AI revolution has started

From our short rummage around the world of Artificial Intelligence it is very evident that AI will:

1. Turbocharge peoples’ ability to generate code (and other capabilities) with little or no experience. This may be a very good or a very bad thing depending on the specific situation.
2. Reduce the amount of time we spend searching for things on the internet. This should not be underestimated because the time wasted on a global basis is huge - not to mention the amount of electrical power it consumes.
3. Drastically reduce the amount of time to create content but care is required because it sometimes 'makes stuff up' and you need to check the output!
4. Make internet technology more accessible to people with sight loss or impairment (if combined with voice recognition). It’s making the computer interface more human.

If you haven’t tested an AI platform yet we would highly recommend it.

Finally, a big thank you to Filippo and colleagues for adding a bit of fun back into cryptography!

About IT Security Locksmith

IT Security Locksmith is a cybersecurity company that specialises in board level training and consultancy.

• To find out more about our capabilities please click here
• Our services page showcases the types of services we offer
• Click here to contact us for a no obligation initial consultation.