ECDSA does not conform to RFC6979 for messages > curve_order

[paulmillr]

RFC6979 3.2.d says:

K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))

where bits2octets is, as per RFC6979 2.3.4 curve order modulo-reduced message:

   The bits2octets transform takes as input a sequence of blen bits and
   outputs a sequence of rlen bits.  It consists of the following steps:

   1.  The input sequence b is converted into an integer value z1
       through the bits2int transform:

          z1 = bits2int(b)
   2.  z1 is reduced modulo q, yielding z2 (an integer between 0 and
       q-1, inclusive):

          z2 = z1 mod q

       Note that since z1 is less than 2^qlen, that modular reduction
       can be implemented with a simple conditional subtraction:
       z2 = z1-q if that value is non-negative; otherwise, z2 = z1.

   3.  z2 is transformed into a sequence of octets (a sequence of rlen
       bits) by applying int2octets.

The implementation's sign takes msg32 — not modulo-reduced msg, and passes it forward.

secp256k1/src/secp256k1.c

Line 476 in 0559fc6

ret = !!noncefp(nonce32, msg32, seckey, NULL, (void*)noncedata, count);

Seems like a bug, which does not exist in go-btcec etc.

[sipa]

Yes and no.

secp256k1_scalar_set_b32_seckey only accepts numbers in range [1,order), which are equal to their reductions modulo order.

So the behavior here is to reject nonces >= order, rather than to reduce them. This isn't an observable difference though, given how close the order is to 2^256.

[paulmillr]

@sipa Ah, this isn't about nonces > curve_order, this is about message aka hashes over curve order. There isn't any check being done for it.

[sipa]

In that case there is no problem, I think. secp256k1_scalar_set_b32(&msg, msg32, NULL); reduces modulo the order (the scalar type is implicitly modulo the curve order).

[paulmillr]

The library reduces msg32 into msg:

secp256k1/src/secp256k1.c

Line 473 in a1102b1

secp256k1_scalar_set_b32(&msg, msg32, NULL);

But! it forgets to pass it 2 lines below:

secp256k1/src/secp256k1.c

Line 476 in a1102b1

ret = !!noncefp(nonce32, msg32, seckey, NULL, (void*)noncedata, count);

RFC6979 3.2.d says it should be reduced before being passed to noncefp

[sipa]

Oh, now I finally understand why you were linking to the nonce generation line.

I agree, it technically deviates from the spec, but not in an observable way.

[paulmillr]

Here's a test case where it'll produce a signature which is different from some other implementations:

key=0000000000000000000000000000000000000000000000000000000000000001
msg=ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

Which seems like a consensus bug between libraries? Is there any disadvantage in making it conform to spec?

[sipa]

It only matters on the signing side, so it's not a consensus issue. I also believe it is harmless (both because msg should be a hash for ecdsa_verify to be secure, and even if it isn't, it just strictly increases the information fed to the nonce functions, which never hurts).

I see no reason why it couldn't be fixed to make it follow the spec to the letter, though.

[kklash]

More background here: paulmillr/noble-secp256k1#42