It Is A Riddle Wrapped In A Mystery Inside an Enigma; But Perhaps There is a Key: Is P256 safe?

What would be the greatest hack of the Internet? Perhaps the cracking of the key exchange for TLS connections? If the NSA could crack these, almost every Web connection could be revealed. These either use RSA to encapsulate the key to be used for the encrypted tunnel or, more commonly, use the ECDH method. The most common curve used for ECDH is the NIST-defined P256 curve. So, is it safe from the prying eyes of the NSA? Well, as Winston Churchill once said of Russia:

It Is A Riddle Wrapped In A Mystery Inside an Enigma; But Perhaps There
is a Key — Winston Churchill

NSA backdoors in crypto

The backdoor in the EC random number generation method in Dual_EC_DRBG was most probably planted by the NSA:

Assange, Snowden and the Trap Door

But, what about the other conspiracy theory that the most commonly used curve (P256) has an NSA backdoor? Well, if it has, then billions of network connections would be at risk, as P256 is the most common method used for key exchange.

Many people who believe that the NSA has compromised the curve point to this page [here]:

But, P256 (secp256r1) not being safe is not a proof that it has been compromised. We can see that the secp256k1 curve (as used with Bitcoin and Ethereum) are also marked as unsafe.

The basics of P-256 is that it uses a form the parameters of:

y² =x²+ax+b (mod p)

and then we pick a base point G on the curve. Here are the parameters [here]:

In this case we have G, a, and b, and where N is the order of the curve (and basically the number of possible points that can be selected).

So has it been cracked?

It should be remembered that in most cases, everything can be cracked in cybersecurity, and it all depends on the resources that someone is willing to put into it. But, generally, for 128-bit security at the current time, it would take all the energy to boil all the oceans on the planet, and many times more, to crack a single elliptic curve key. As P256 has 128-bit security, it is generally seen as being safe from brute force. With the advent of quantum computers, though, this is unlikely to be the case.

Overall, at the current time, it is likely to be safe, but we cannot guareetee that. This is the reason that it cannot be marked as safe. The “Not safe” marking on the page just shows that there are a few things that would have helped to demonstrate that it was fully safe at the current time, and that the curve is not fully optimized. It should be remembered that P256 has probably been used trillions and trillions of times more than many of the curves that are marked as safe.

The great debate on P256 comes from the seed that was used to generate its parameters. This seed value was 0xc49d360886e70493 6a6678e1139d26b7819f7e90. At the core of the debate is that the curve was first defined by Jerry Solinas and who at one time worked for the NSA [here]. Selecting such a large random value makes it difficult to check the security of the curve, and where the seed value could have been discovered to have a backdoor.

Overall, in the generation of the elliptic curve parameters, we can have randomly generated ones or specially selected ones. Curve 25519 has ones which are specially selected for performance and security, and the Brainpool ones are randomly generated. The method for generating randomly generated curves are well documented, and includes the seed value used. One problem with this, is that we may generate something which breaches an existing patent. This approach is the “nothing up my sleeves”, and the random seed can be shown to have some from a random source. This is like a dealer handing over the cards to a mechanised card shuffler, and who will randomly shuffle the cards using a truely random source as its seed, and handing the cards back to the dealer. So, unfortunately, we do not have the original proof of the random value for P256, as its source has been lost. No-one knows if NIST were the one who actually generated the seed for the curve, or not.

So, it’s unlikely we will ever be able to prove that P256 is safe or not, but on the balance of probabilities, it probably is. One thing that is sure, is that ECC will crumble first with the onslaught of quantum computers (QCs), so we should perhaps think about moving away from it some time soon. RSA, though, will be a tougher nut to crack for QCs, and may be able to hold the fort for longer.

An excellent article on this is by the ever wonder Matthew Green:

A riddle wrapped in a curve

In the article, Matthew outlines a paper from the co-creator of ECC (Koblitz) and one of the most knowledgable authors of cryptography (Menezes) on the NSA speculation [1]:

In the paper, the authors outline that if someone believes in the conspiracy, they should perhaps avoid using ECC altogether, and switch to RSA for digital signing.

Meeting the curves

There are lots of different types of standard elliptic curves, and the most common ones are Brainpool, SEC, and NIST. The two most common curves are secp256k1 (as used in Bitcoin and Ethereum) and NIST (FIPS) P-256 (as used in TLS). These curves give us around 128 bits of security. Famously secp256k1 has the curve parameters of:

G=(79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8,1,0), N=115792089237316195423570985008687907852837564279074904382605163141518161494337, H=1
A =0
B=7
Field size=256

But there are many other curves, including Brainpool256r1:

G=(8bd2aeb9cb7e57cb2c4b482ffc81b7afb9de27e1e3bd23c23a4453bd9ace3262,547ef835c3dac4fd97f8461a14611dc9c27745132ded8e545c1d54c72f046997,1,7d5a0975fc2c3057eef67530417affe7fb8055c126dc5c6ce94a4b44f330b5d9), N=76884956397045344220809746629001649092737531784414529538755519063063536359079, H=1
A =7d5a0975fc2c3057eef67530417affe7fb8055c126dc5c6ce94a4b44f330b5d9
B=26dc5c6ce94a4b44f330b5d9bbd77cbf958416295cf7e1ce6bccdc18ff8c07b6
Field size=256

With elliptic curve cryptography, we start with a definition for the curve, such as:

y²=x³+ax+b (mod p)

This defines values for a, b and p. Next we select a base point on the curve (G, and generate a random scalar value (D). This is the private key, and where the public key is generated from a point multiplcation of:

Q=D.G

This results in an (x,y) point on the curve.

Coding

First we create a folder named “bc_ec02”, and then go into that folder.We can create a Dotnet console project for .NET 8.0 with:

dotnet new console --framework net8.0

Next we can install the Bouncy Castle library with:

dotnet add package BouncyCastle.Crypto.dll --version 1.8.1

Next some code [here]:

namespace ECCurves
{
    using Org.BouncyCastle.Asn1.X9;
    using Org.BouncyCastle.Security;
    using Org.BouncyCastle.Crypto.Parameters;
class Program
    {
        
        static void Main(string[] args)
        {
            
            
          
            var curvename="secp256k1";

           if (args.Length >0) curvename=args[0];
          
  
             
            try {

            X9ECParameters ecParams = ECNamedCurveTable.GetByName(curvename);
            var curveparam = new ECDomainParameters(ecParams.Curve, ecParams.G, ecParams.N, ecParams.H, ecParams.GetSeed());
  
            Org.BouncyCastle.Crypto.Parameters.ECKeyGenerationParameters keygenParams = new Org.BouncyCastle.Crypto.Parameters.ECKeyGenerationParameters (curveparam, new SecureRandom());
            Org.BouncyCastle.Crypto.Generators.ECKeyPairGenerator generator = new  Org.BouncyCastle.Crypto.Generators.ECKeyPairGenerator();
            generator.Init(keygenParams);
            var keyPair = generator.GenerateKeyPair();

            var privateKey = (ECPrivateKeyParameters) keyPair.Private;
            var publicKey = (ECPublicKeyParameters) keyPair.Public;

            Console.WriteLine("== Curve: {0} ",curvename);
            Console.WriteLine("\n== Private key === ");
            Console.WriteLine("== D ==={0} ",privateKey.D.ToString()); 
            Console.WriteLine("\n== Public key === ");
            Console.WriteLine("== Q_x ==={0} ",publicKey.Q.XCoord);
            Console.WriteLine("== Q_t ==={0} ",publicKey.Q.YCoord);

            Console.WriteLine("\n\nCurve details: G={0}, N={1}, H={2}", ecParams.G, ecParams.N, ecParams.H);
            Console.WriteLine("A={0}\nB={1}\nField size={2}",ecParams.Curve.A,ecParams.Curve.B,ecParams.Curve.FieldSize);

    } catch (Exception e) {
    Console.WriteLine("Error: {0}",e.Message);
    }
    }
    }

}

We should now be able to generate a key pair for virtually every standard curve possible:

A sample run for secp2561 gives [here]:

== Curve: secp256k1 
== Private key === 
== D ===31064867539724903891960137032820676127521229242105362809544430719991795260503 
== Public key === 
== Q_x ===8c65b935e0fd6e174c7b180f5d1db7cda52bf8222d11f7abc924067c40e11de8 
== Q_t ===6e4602ae3c8f42683f4d7269c4abf55a28bcd69ff84060118f327d25c1074a1e 
Curve details: G=(79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8,1,0), N=115792089237316195423570985008687907852837564279074904382605163141518161494337, H=1
A =0
B=7
Field size=256

And for NIST (FIPS) P-256 [here]:

== Curve: P-256 
== Private key === 
== D ===36520681454922814890347386938615718499728808447933454325466265828246263851321 
== Public key === 
== Q_x ===d52722849984ff0a89d50de91877f66377ba4065c5802adc169c235ad37d1eea 
== Q_t ===7fc6d99095fe7712f5ec1f5b5f9d5425cf7ae9de4f2d77d4022f67d6f8aa3f75 
Curve details: G=(6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5,1,ffffffff00000001000000000000000000000000fffffffffffffffffffffffc), N=115792089210356248762697446949407573529996955224135760342422259061068512044369, H=1
A =ffffffff00000001000000000000000000000000fffffffffffffffffffffffc
B=5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
Field size=256

Here is the creation using Microsoft Code:

Conclusions

The time of using ECC is coming to an end, and we must migrate to PQC (Post Quantum Cryptography) methods over the next few years. Hopefully, these will all have provably secure techniques and “nothing-up-my-sleeve”. If you do think that the NSA have cracked P256, then perhaps switch to RSA for your signatures and key exchange, or a PQC method.

References

[1] Koblitz, N., & Menezes, A. (2016). A riddle wrapped in an enigma. IEEE Security & Privacy, 14(6), 34–42.