Cryptography specialist Filippo Valsorda has issued a challenge for the first person to crack the seed values for elliptic curve cryptography and recover the plain text values which were used to generate them back in 1997.
Elliptic Curve Cryptography (ECC) was chosen as the alternative to RSA cryptography, the reason being that ECC uses much smaller values to achieve the same strength of encryption.
RSA cryptography
With RSA, a user creates and publishes a public key which is based on two large prime numbers, along with an auxiliary value. The prime numbers must be kept secret.
Messages can be encrypted by anyone, via the public key, but can only be decoded by someone who knows the prime numbers.
As technology advances, the time it takes to process all possible prime values for a given key is reduced – eventually to a point where it is trivial to obtain the keys, and thus be able to decrypt all messaged which have been encrypted with that key.
As a result, in order to keep using RSA, larger, and larger prime values must be chosen, leading to high computational overheads
ECC Cryptogrpahy
ECC uses the mathematical concept of elliptic curves defined over finite fields to generate relatively short yet secure keys. Using curves ensures that, for a selected point (on them), it’s computationally infeasible to determine the multiple of that point (scalar) used to produce it, providing the basis for encryption.
A starting point is chosen on the curve, and a line is drawn such that it intersects the curve at two further points. Mirroring the points along the x-axis allows for e new line to be drawn which intersects the curve.
By repeating this action n-times, we arrive at a value which is used for the encryption process.
However, on being given a value on the curve, it is infeasible to reverse the process back to the originating start point on the curve.
The NIST elliptic curves – known as P-192, P-224, P-256, P-384, and P-521 were generated in 1997 using seed which were provided by the NSA. Nobody knows how the original seeds were generated, but rumors and research suggest that they are hashes of English sentences provided by the NSA. The phrases are believed to have been hashed using the SHA-1 hashing algorithm.
Dr. Jerry Solinas was the person who picked the phrases to generate the seeds, but Dr. Solinas, passed away in early 2023 leaving behind a cryptographic mystery, some conspiracy theories, and an historical password cracking challenge.
Voices of concern from the cryptographic community started many years ago, starting with the Dual_EC_DRBG controversy that claimed the NSA backdoored the algorithm.
The most worrying scenario arises from speculation and skepticism about an intentional weakness incorporated in the NIST curves, which would enable the decryption of sensitive data.
Even though no substantial evidence exists to support these scenarios, the seeds’ origin remains unknown, creating fear and uncertainty in the community.
The challenge is to try to break the SHA-1 hashes to recover the seed values.
