Scalar multiplication wrong in 1 of 2 test cases

[philsmd]

Hey,
I'm investigating some ECC code since a couple of days and found this "library" quite interesting.

The problem is that the result of the point multiplication I get by using this library is NOT the same I get by using other tools/libraries etc. It's incorrect almost exactly once when testing twice, on average. By testing twice I mean to use a different randomly picked 32 byte scalar which is MOD the secp256k1 prime (I don't mean running the same input twice, just to be clear !)

I kind of tracked this problem down to the code NOT using the scalar correctly and starting to ignore the first bit here:

micro-ecc/uECC.c

Line 876 in 601bd11

for (i = num_bits - 2; i > 0; --i) {

(btw a -1 there would be kinda acceptable because of the offset ending with size -1 of course if starting to count from 0 .... but of course would still NOT give the correct result for other reasons double vs double+adding, initial doubling until the first bit is set).

My suspicion is that the code just assumes that the first bit of the scalar is set and therefore does kind of an add+double (it's not directly/really doing this because the first one is just 0 + P and therefore it's just set to P of course) instead of initially doubling as long as there is NO 1 bit found (at least this is what I found out during my little resarch these few days I investigate this).

Here is my example code (please do not blame me for my bad code ;) , I allow anybody to use this/my own code for any purpose, public domain):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include "uECC.h"
#include "uECC.c"

// EXAMPLE:
// base point G:
// public:  02f73ee58173720a4dc105a5f9b3685cfcfe5ea035b9544aec3345d64bbc417f82
// pub_x:     f73ee58173720a4dc105a5f9b3685cfcfe5ea035b9544aec3345d64bbc417f82
// pub_y:     14e8071ae36ce40c8ecc5201e0508591314c8ff15426fc63b94d5488723a67bc

// k of k * G:
// scalar:    68b00b3389dfcc230f0d0c5c4017e8943355186eeb072bae5a1eb03eebaf618a

// wrong:   03b8e16e1dffe5b39fc3ef993b9b1c4fb8863070810697538773fff95115aa9503
// correct:
// private: 035df14b4b5c178339005e118138ae8a14fbac8d01841615d529545ac3e2acc160
// priv_x:    5df14b4b5c178339005e118138ae8a14fbac8d01841615d529545ac3e2acc160
// priv_y:    57782d8504c1aebdddb3307f7c21b5a9c15d52d560f127033bb204fc537aca65

// problem is that it treats this:
// 68b00b3389dfcc230f0d0c5c4017e8943355186eeb072bae5a1eb03eebaf618a
// as
// e8b00b3389dfcc230f0d0c5c4017e8943355186eeb072bae5a1eb03eebaf618a
// (i.e. it always adds at the start, regardless if first bit is 0)

// compile this with:
// gcc -Wall -Wextra uacc_test_case.c -Imicro-ecc/ -DuECC_CURVE=uECC_secp256k1 -DuECC_ASM=uECC_asm_none -DuECC_WORD_SIZE=4 -DuECC_ENABLE_VLI_API -o uacc_test_case

int main ()
{
  // select the curve first, because many sizes depend on the curve itself:

  uECC_Curve curve = uECC_secp256k1 ();

  int num_bytes  = curve->num_bytes;
  int num_words  = curve->num_words;
  int num_n_bits = curve->num_n_bits;

  // base point:

  // pub_x: f73ee58173720a4dc105a5f9b3685cfcfe5ea035b9544aec3345d64bbc417f82

  uint8_t x[num_bytes];

  memcpy (x, "\xf7\x3e\xe5\x81\x73\x72\x0a\x4d\xc1\x05\xa5\xf9\xb3\x68\x5c\xfc"
             "\xfe\x5e\xa0\x35\xb9\x54\x4a\xec\x33\x45\xd6\x4b\xbc\x41\x7f\x82", num_bytes);

  // pub_y: 14e8071ae36ce40c8ecc5201e0508591314c8ff15426fc63b94d5488723a67bc

  uint8_t y[num_bytes];

  memcpy (y, "\x14\xe8\x07\x1a\xe3\x6c\xe4\x0c\x8e\xcc\x52\x01\xe0\x50\x85\x91"
             "\x31\x4c\x8f\xf1\x54\x26\xfc\x63\xb9\x4d\x54\x88\x72\x3a\x67\xbc", num_bytes);


  // base point: (x, y)

  uint8_t base[num_bytes * 2];

  memcpy (base +         0, x, num_bytes);
  memcpy (base + num_bytes, y, num_bytes);


  // tweak/scalar:

  // tweak (all bytes reversed from back to forth):

  uECC_word_t scalar[num_words];

  memcpy (scalar, "\x8a\x61\xaf\xeb\x3e\xb0\x1e\x5a\xae\x2b\x07\xeb\x6e\x18\x55\x33"
                  "\x94\xe8\x17\x40\x5c\x0c\x0d\x0f\x23\xcc\xdf\x89\x33\x0b\xb0\x68", num_bytes);

  // ATTENTION (BUG BUG BUG !): same result with this:

  // memcpy (scalar, "\x8a\x61\xaf\xeb\x3e\xb0\x1e\x5a\xae\x2b\x07\xeb\x6e\x18\x55\x33"
  //                 "\x94\xe8\x17\x40\x5c\x0c\x0d\x0f\x23\xcc\xdf\x89\x33\x0b\xb0\xe8", num_bytes);



  /*
   * Start:
   */

  int ret = 0;

  ret = uECC_valid_public_key (base, curve);

  if (ret != 1)
  {
    fprintf (stderr, "ERROR: public key is NOT valid\n");

    return -1;
  }



  uECC_word_t pub[num_words * 2];

  uECC_vli_bytesToNative (pub +         0, base +         0, num_bytes);
  uECC_vli_bytesToNative (pub + num_words, base + num_bytes, num_bytes);

  ret = uECC_valid_point (pub, curve);

  if (ret != 1)
  {
    fprintf (stderr, "ERROR: point is NOT valid point on the secp256k1 curve\n");

    return -1;
  }



  // main elliptic curve multiplication by a scalar:

  uECC_word_t priv[num_words * 2];

  EccPoint_mult (priv, pub, scalar, 0, num_n_bits, curve);



  // debug/output:
  // (I know we could convert it back with uECC_vli_nativeToBytes ())

  printf ("x: ");

  for (int i = 1 * num_words - 1; i >=         0; i--) printf ("%08x", priv[i]); // print  7..0

  printf ("\n");

  printf ("y: ");

  for (int i = 2 * num_words - 1; i >= num_words; i--) printf ("%08x", priv[i]); // print 15..8

  printf ("\n");

  return 0;
}

As you can see from the code, my coordinates and scalar are:

public:  02f73ee58173720a4dc105a5f9b3685cfcfe5ea035b9544aec3345d64bbc417f82
pub_x:     f73ee58173720a4dc105a5f9b3685cfcfe5ea035b9544aec3345d64bbc417f82
pub_y:     14e8071ae36ce40c8ecc5201e0508591314c8ff15426fc63b94d5488723a67bc

scalar:    68b00b3389dfcc230f0d0c5c4017e8943355186eeb072bae5a1eb03eebaf618a

wrong:   03b8e16e1dffe5b39fc3ef993b9b1c4fb8863070810697538773fff95115aa9503
priv_x:    b8e16e1dffe5b39fc3ef993b9b1c4fb8863070810697538773fff95115aa9503
priv_y:    f159000f8d383df8502d60d0326b2c0b61dc63d2d8e779af0baecf82feac3d05

correct: 035df14b4b5c178339005e118138ae8a14fbac8d01841615d529545ac3e2acc160
priv_x:    5df14b4b5c178339005e118138ae8a14fbac8d01841615d529545ac3e2acc160
priv_y:    57782d8504c1aebdddb3307f7c21b5a9c15d52d560f127033bb204fc537aca65

The main problem is that it treats my scalar
68b00b3389dfcc230f0d0c5c4017e8943355186eeb072bae5a1eb03eebaf618a

as it was this one:
e8b00b3389dfcc230f0d0c5c4017e8943355186eeb072bae5a1eb03eebaf618a
i.e. as if the first bit was set to 1 (0x68 | 0b10000000 == 0xe8)

I'm pretty sure my x, y and k/scalar values are correct/acceptable, they are all MOD the prime and are all accepted also by other tools (which do a lot of sanity checks like the secp256k1 library by Peter Wuille itself).

Of course there might be still a slight possibility that I am doing something wrong in the code or that some input is incorrect (but since it works in every second try, that would be quite strange).
It could still be pebcak (especially since I'm pretty new to this ECC stuff and most of all to this specific library). Excuse me if it's my fault, but I think it's still worth to mention my "observations"/problems here, just in case.

In my opinion it would be quite bad if half of the multiplications were done incorrectly and I'm really wondering what would happen if there was really such a serious bug and the code was used for years in production (of course I know that nobody should blindly use some code and assume everything is correct, but we all know how people just grab and use the first working open source library they find ;) ) etc

Maybe I'm completely wrong here and I need to provide different x,y,z inputs etc (but still... then the users would just use the API incorrectly, because users assume it works exactly like I was testing it, I guess). I hope I'm wrong... but please investige at least a little bit here @kmackay et al.

Thank you so much for the library and for your attention (I hope I didn't waste your time)

BTW: just to clarify, I say 1 in 2 cases because if we assume randomly generated keys, the first bit has the change of 50:50 or 1 in 2 to be set or unset.
To make it very clear, I assume the code fails whenever the scalar does NOT have the first bit set (which should be a totally fine/acceptable input, the only prerequisite we need to respect is that the scalar is MOD the secp256k1 prime, as far as I know)

[gmaxwell]

If it does this for the ecdsa signature nonce too it is effectively a total break.

https://eprint.iacr.org/2014/161.pdf

[jpcrypt]

I think this is a documentation issue, you're meant to use uECC_point_mult(), not EccPoint_mult().
The former is a wrapper around the latter, with the addition of a regularizing step on the scalar which results in its MSB being set; I think this is done to protect against side-channel attacks.