EC_POINT_mul() creates duplicate keys

[alexanderkent]

In a vanity bitcoin generator, OpenSSL thread support enabled and OpenSSL threading configured (i.e. 41 CRYPTO_num_locks), running multiple pthreads with EC_POINT_mul() creates duplicate EC_POINT randomly, i.e. say after ~1000 or so iterations.

Each thread has their own EC_GROUP etc, no global variables. Thread context "tctx" has an integer indicating thread# i.e. 0,1,2,3 etc.

    EC_POINT_mul(pgroup, ppnt, &bnpriv, NULL, NULL, ctx);
    BIGNUM *x = BN_new();
    BIGNUM *y = BN_new();
    EC_POINT_get_affine_coordinates_GFp(pgroup, ppnt, x, y, ctx);
    char *x_hex =  BN_bn2hex(x);
    char *y_hex = BN_bn2hex(y);
    printf("thread:%d x: %s \t y: %s\n", tctx->id, x_hex, y_hex);

   // Omitted: hash-table is used to check for dupes..

Result:

thread:0 x: 90A7D0BA3BBB6DAD0A98BC357E7AD07F2B43230F46D3D93C39BA4B60D2706207 y: F1F80FADC0ED6AA378A9506B596DBBBB5C8079A030F362B45F76FC1F4B09B72A
thread:1 x: 45B86811303821AC07B143321BE788B07CDE6B5510B4D4FE379DC407EA739268 y: C7C29440FCEF2F2B7692B5BE85737D9E9B5CFE10B0816EBBC2F01722A2275E3A
thread:0 x: B7261BC5292F2F50C0B4D5E59B163E2B486CBF81B7FC3DECF157F262BDD5CA93 y: 8257A13565B01DDD692E695A92191C13B74EC04ADC6413B5BA63EBCA3E76E0A3
thread:1 x: 6F3056658F0B99D00F6A34F38B8C84200FB7544C44109B9FA8C61F5E3D20083F y: 0A621B41D5B50CC8664229C679071AC8EC9BC5C6B7647AC6312725B95139A244
thread:1 x: 47C6CAFD11FCCFEE0697AA5C8B9FE0292F35E77FE762DCC34C1CC3DB9127D3EC y: 3040F605A0E1CD5CD0D1E144D0A8F13656FDE7AA6EFF59F5D2F0CEA2BFD783B3
thread:0 x: 47C6CAFD11FCCFEE0697AA5C8B9FE0292F35E77FE762DCC34C1CC3DB9127D3EC y: 3040F605A0E1CD5CD0D1E144D0A8F13656FDE7AA6EFF59F5D2F0CEA2BFD783B3

ERROR: duplicate detected: 47C6CAFD11FCCFEE0697AA5C8B9FE0292F35E77FE762DCC34C1CC3DB9127D3EC

Notice how the last two are duplicates. Is this a bug or am I missing some sort of OpenSSL config?

[mattcaswell]

What value are you storing in bnpriv?

[alexanderkent]

Right now using:
sprintf(seed, "%d_%ld", tctx->id, i); //tctx->id = thread id, i = counter

Thread 0:
0_0
0_1
..

Thread 1:
1_0
1_1
..

// Convert seed to SHA256
const unsigned char *d = SHA256(seed, strlen(seed), 0);

// Convert to bignum
BN_bin2bn(d, SHA256_DIGEST_LENGTH, &bnpriv);

and I've verified that indeed seed / bnpriv is unique for each thread

[mattcaswell]

That's a very strange seed. From the man page for BN_bin2bn:

BN_bin2bn() converts the positive integer in big-endian form of length len at s into a BIGNUM and places it in ret. If ret is NULL, a new BIGNUM is created.

So your string is filling in the seed from left to right - which will be the high-bits in the created BIGNUM. You've also created a BIGNUM which is 256 bits in length (all apart from the high bits are unspecified and just filled with whatever junk happens to be in seed after the string null terminator). I don't know what curve you are using, but I suspect you are arriving at a number which is bigger than the order of the curve generator - so the result is going to "wrap around".

Can you supply details of the curve you are using, and two different seeds (the actual bignum value) that end up at the same point?

[alexanderkent]

Ended up with those seeds whilst testing and ensuring all methods were thread safe etc...

Bitcoin uses secp256k1:

EC_GROUP *pgroup = EC_GROUP_new_by_curve_name (NID_secp256k1);
BN_CTX *ctx = BN_CTX_new();
EC_GROUP_precompute_mult(pgroup, ctx);


seed string = 0_0
SHA256(seed) in hex = 87194e11340606118b69fc87e10a5d80edfeec6ece04969366bc291262706c97
BN_bn2hex(&bnpriv) = 87194E11340606118B69FC87E10A5D80EDFEEC6ECE04969366BC291262706C97

We can verify that "0_0" is "87194e11340606118b69fc87e10a5d80edfeec6ece04969366bc291262706c97" (Secret Exponent) using https://brainwallet.github.io/

   printf("SHA256(seed) in hex = ");
   dumphex(d,SHA256_DIGEST_LENGTH);

   // Create bignum
   BN_bin2bn(d, SHA256_DIGEST_LENGTH, &bnpriv);

   // Verify bignum
   const char *hexFromBN = BN_bn2hex(&bnpriv);
   printf("BN_bn2hex(&bnpriv) = %s\n", hexFromBN);

We populate the bignum and verify via BN_bn2hex and get 87194E11340606118B69FC87E10A5D80EDFEEC6ECE04969366BC291262706C97

We should always just have 32-byte (SHA256_DIGEST_LENGTH) bnpriv.

Ultimately we use bnpriv in EC_POINT_mul() and EC_POINT_get_affine_coordinates_GFp()

[mattcaswell]

Ok...but can you give me two different BIGNUMs that multiply to the same point on that curve - you only gave me one above.

[alexanderkent]

I will try provide better sample data. To try clarify, if we run in a single thread we never have any issues. As soon as we run multiple threads we end up with duplicates (but they are random) possibly from EC_POINT_mul() ??? but we don't know. Fairly certain that bnpriv is always unique in each thread.

[mattcaswell]

I assume you have set up the crypto locking callbacks?

https://www.openssl.org/docs/crypto/threads.html

[alexanderkent]

Yes we've setup locking callbacks and even tried dynamic callbacks too based on crypto/threads/mttest.c for our platform (Mac OS X and Linux) pthreads. In main() we call a function to set the crypto callbacks before we start the threads.

fprintf(stdout,"%s: %d CRYPTO_num_locks\n", __func__,CRYPTO_num_locks());

// outputs
thread_setup: 41 CRYPTO_num_locks

[alexanderkent]

Wondering about my usage of:
unsigned char *d = SHA256(seed,strlen(seed), 0);

unsigned char *SHA256(const unsigned char *d, size_t n,unsigned char *md);
Is that just a wrapper around SHA256_CTX ?

[mattcaswell]

Urgh. That's your problem. Just looked at the code for SHA256. It's not thread safe if you don't supply a buffer in the third argument. Its basically just a wrapper that calls SHA256_Init, SHA256_Update and SHA256_Final. The third argument is supposed to be the buffer that you are going to populate. If you don't supply one then it uses a static local variable. Yuk. That's going to cause big problems with a multi threaded implementation.

The work around is to supply your own buffer. We probably need to deprecate that usage and document it. Not sure there is another solution :-(

[alexanderkent]

OMG! Mystery solved, that makes sense now. I'll give it a go and will report back.

Would it be best for me to just use SHA256_CTX or use SHA256() with a local buffer?

    SHA256_CTX sha256;
    SHA256_Init(&sha256);
    SHA256_Update(&sha256, seed, strlen(seed));
    SHA256_Final(d, &sha256);

[alexanderkent]

I don't want to speak too soon but I just replaced:

unsigned char *d = SHA256(seed,strlen(seed), 0);

with:

unsigned char d[SHA256_DIGEST_LENGTH];
SHA256_CTX sha256;
SHA256_Init(&sha256);
SHA256_Update(&sha256, seed, strlen(seed));
SHA256_Final(d, &sha256);
..
.

And using 16 threads it already processed 6 million iterations with no duplicates.

[mattcaswell]

Great - good news. For info, the preferred API functions to use are actually the EVP_Digest* functions:

https://www.openssl.org/docs/crypto/EVP_DigestInit.html

[alexanderkent]

Perfect. Thank you.