ECDSA does not conform to RFC6979 for messages > curve_order #1063

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.

https://github.com/bitcoin-core/secp256k1/blob/0559fc6e41b65af6e52c32eb9b1286494412a162/src/secp256k1.c#L476

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

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.

@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.

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).

The library reduces msg32 into msg:

https://github.com/bitcoin-core/secp256k1/blob/a1102b12196ea27f44d6201de4d25926a2ae9640/src/secp256k1.c#L473

But! it forgets to pass it 2 lines below:

https://github.com/bitcoin-core/secp256k1/blob/a1102b12196ea27f44d6201de4d25926a2ae9640/src/secp256k1.c#L476

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

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.

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?

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.

More background here: https://github.com/paulmillr/noble-secp256k1/pull/42