bitcoinjs-lib and related repos are not 100% RFC6979 compliant (only 99.999...%)

[dabura667]

I may be nit-picking, as the chance of an out of bounds k or bad r or s value is so infinitesimally small...

But shouldn't we all be 100% RFC 6979 compliant if possible?

Here's some of the repos I cleaned up.

https://github.com/bitpay/bitcore/pull/884

I added a similar badrs function to python-ecdsa and compared the results.

The 1 badrs (aka forcing it to loop once) gave me a different value. It turns out you missed one of the v = hmac_k(v) steps during the loop.

Adding one extra v = hmac_k(v) in each loop makes it match up with python-ecdsa perfectly (I even tried up to badrs = 30 and it was fine.

https://tools.ietf.org/html/rfc6979#section-3.2

If you follow Step h from after the k = bits2int(T) downward, then back up to the beginning of Step h to loop.

Code:

K = HMAC_K(V || 0x00)
V = HMAC_K(V)
Empty T
V = HMAC_K(V)
T = V    (since we know tlen == qlen)
k = bits2int(T)

As you can see, the original code in Bitcore was missing one V = HMAC_K(V) whereas python-ecdsa includes it in the loop.

Including this commit will make the behavior be 100% rfc 6979 compliant.

https://github.com/blockchain/My-Wallet/pull/115

RFC specifies that if the k value is out of bounds OR if r or s is 0 you must loop through Step h until a proper value is found.

The way bitcore implements this is by including an integer called "badrs" that will force entering the re-hashing loop of Step h. The incrementing of badrs is done in a do while loop around k generation and r and s calculation.

The only way this could be a security issue is if someone had a transaction + privkey pair that just happened to produce an out of bounds k (or in bitcore's case, a bad r or s)... AND they decided to sign that transaction using both bitcore/blockchain.info AND Electrum (uses python-ecdsa) and then for some reason posted those two signed transactions in the public space somehow.

Edit: Just put in PR to bitcoinjs-lib:

https://github.com/bitcoinjs/bitcoinjs-lib/pull/336

[1713864771]

1713864771

[1713864771]

1713864771

[1713864771]

1713864771

[hhanh00]

I thought the RFC had an example of such a case in section A1. Am I mistaken or they didn't test it?

[johoe]

Nice find.  I think Trezor has the same issue.  There are probably more.

Looking closer at the spec, it requires to use HMAC with the same hash that is used for hashing the message.  Bitcoin uses double-SHA256 while all rfc6979 implementations use HMAC-singleSHA256. I'm not sure how many crypto libraries support hmac with double sha256 out of the box.  It would be a bigger change with no real advantage.

Otherwise, the old code produced identical signature except for border cases with probabilty 3.7*10^-39 (that is really,really tiny).  However, this low probability makes it impossible to generate a real test case for this.  You would also want a test case where s is 0, but that is hope-less to brute-force.

I thought the RFC had an example of such a case in section A1. Am I mistaken or they didn't test it?

I think they didn't test it.  It is for a different curve, so the k values are only 163 bits, but at least the K,V,T values should be the same.

@dabura667: did you test it against that example?

[gmaxwell]

Looking closer at the spec, it requires to use HMAC with the same hash that is used for hashing the message.

It does not.  In RFCs, requirements are usually specified using all-caps (though not strictly required), and special keywords. See RFC 2119.  It does make a suggestion to do so, but there are often good reasons not to do so; e.g. becuase of application layering, code availability, etc. (also RFC6979 is kind of embarrassingly slow already, mandating it be half again slower in our case would just encourage more people to do ill-formed adhoc things). In this case the suggestion doesn't even appear to be SHOULD level.

It's common for found-on-the-internet ECC crypto-implementations to be pedantically incorrect, and in worse ways than this. Caveat emptor. Virtually none of them that I've seen have evidence of strong peer review, or evidence that their authors have an especially detailed understanding of what they're doing. (Turns out you can implement working, or at least mostly working ECC just by aping some tutorials, which were themselves often written by people new to the subject).

I think being correct in this respect is important, not just in case someone manages to find the p=2^-256 inputs that expose misbehaviour, but also because the same code may later be reused for future curves where the field isn't so insanely close to 2^256, and a failure to implement this correctly can turn into a serious security vulnerability. It's also important to do right because it simplifies review: one can mechanically check each step and not resort to time consuming (and risky!) cryptographic reasoning about the implication of any particular change, the bug (or backdoor) that kills you is the one that looked harmless on the surface.

[dabura667]

@dabura667: did you test it against that example?

They didn't have any secp256k1 test vectors 

[hhanh00]

@dabura667: did you test it against that example?

They didn't have any secp256k1 test vectors  

Yes, but first you code the general case, and then you can simplify.

Btw, BIP32 has a similar rule. It may be worth checking their implementation of it too.

[dabura667]

Yes, but first you code the general case, and then you can simplify.

I'm not about to stretch out their implementation to accommodate all curves and implementations just so I can test their implementation (which by that point would be mostly my re-implementation) against the test vectors in the RFC.

However, it is obvious if you follow the RFC6979 test case that they "re-generate T" which includes the extra V = HMAC_K(V) that I included in my pull request.

As for the BIP32 case, I do believe most places account for out of bounds private key results... but there are so many implementations of BIP32 compared to RFC6979... x.x

[hhanh00]

Yes, but first you code the general case, and then you can simplify.

I'm not about to stretch out their implementation to accommodate all curves and implementations just so I can test their implementation (which by that point would be mostly my re-implementation) against the test vectors in the RFC.

However, it is obvious if you follow the RFC6979 test case that they "re-generate T" which includes the extra V = HMAC_K(V) that I included in my pull request.

As for the BIP32 case, I do believe most places account for out of bounds private key results... but there are so many implementations of BIP32 compared to RFC6979... x.x

I meant you as the impersonal pronoun - not you per say. If I remember correctly, the only shortcut is regarding tlen=qlen. Everything else had to be implemented and it was tricky at a few places.

[dabura667]

I think Trezor has the same issue.

https://github.com/trezor/trezor-crypto/blob/9fea8f8ab377dc514e40c6fd1f7c89a74c1d8dc6/ecdsa.c#L285

It looks as though they have the proper number of HMACs, but only check for in bounds k.

https://github.com/trezor/trezor-crypto/blob/9fea8f8ab377dc514e40c6fd1f7c89a74c1d8dc6/ecdsa.c#L349
https://github.com/trezor/trezor-crypto/blob/9fea8f8ab377dc514e40c6fd1f7c89a74c1d8dc6/ecdsa.c#L362  (Note: &k is the s value)

It looks like if r or s is 0, they do not follow RFC6979 and continue to the next loop of k generation... instead they throw an error.
So the only way a user could then send their bitcoins is to choose a different input, or change the send amount slightly to change the transaction hash and/or private key for signing.

[dabura667]

I meant you as the impersonal pronoun - not you per say. If I remember correctly, the only shortcut is regarding tlen=qlen. Everything else had to be implemented and it was tricky at a few places.

Ahh ok.

Yeah, tlen=qlen assumption will come to bite us in the behind if Bitcoin ever decides to switch from secp256k1... lol (idk if that will ever happen)

[johoe]

I think Trezor has the same issue.

https://github.com/trezor/trezor-crypto/blob/9fea8f8ab377dc514e40c6fd1f7c89a74c1d8dc6/ecdsa.c#L285

It looks as though they have the proper number of HMACs, but only check for in bounds k.

https://github.com/trezor/trezor-crypto/blob/9fea8f8ab377dc514e40c6fd1f7c89a74c1d8dc6/ecdsa.c#L349
https://github.com/trezor/trezor-crypto/blob/9fea8f8ab377dc514e40c6fd1f7c89a74c1d8dc6/ecdsa.c#L362  (Note: &k is the s value)

It looks like if r or s is 0, they do not follow RFC6979 and continue to the next loop of k generation... instead they throw an error.
So the only way a user could then send their bitcoins is to choose a different input, or change the send amount slightly to change the transaction hash and/or private key for signing.

Okay, the r=0 (are there points on secp256k for x=0?) or s=0 is another (unlikely to occur) problem.

But I think it needs this patch to be fully compliant (one can then also remove the variable t). 
The hmac in line 290 should run on the output of the hmac in line 283.

Code:

--- a/ecdsa.c
+++ b/ecdsa.c
@@ -280,8 +280,8 @@ int generate_k_rfc6979(bignum256 *secret, const uint8_t *pri
        hmac_sha256(k, sizeof(k), v, sizeof(k), v);
 
        for (i = 0; i < 10000; i++) {
-               hmac_sha256(k, sizeof(k), v, sizeof(v), t);
-               bn_read_be(t, secret);
+               hmac_sha256(k, sizeof(k), v, sizeof(v), v);
+               bn_read_be(v, secret);
                if ( !bn_is_zero(secret) && bn_is_less(secret, &order256k1) ) {
                        return 0; // good number -> no error
                }

I haven't tested this at all though.

[hhanh00]

I think you got something confused. k = 0 isn't the same as r=0 or s=0. The point at infinity has no X,Y but cannot be generated if k is between 1 and n-1 simply because kG <> 0.

[dabura667]

I think you got something confused. k = 0 isn't the same as r=0 or s=0. The point at infinity has no X,Y but cannot be generated if k is between 1 and n-1 simply because kG <> 0.

They are using C, and for some reason they kept running all the calculations and mutating &k until it became s.

The variable &k is the s of the signature by the time they check it in line 362.

I am aware k is the normal naming for the random number in the R = kG (where r = R's x coord)... however, if you follow all the operations, you will see that &k is representing the (r, s) signature's s value.

[dabura667]

Code:

#if USE_RFC6979
	// generate K deterministically
	if (generate_k_rfc6979(&k, priv_key, digest) != 0) {    <<< this stores the k value into &k
		return 1;
	}
#else
	// generate random number k
	if (generate_k_random(&k) != 0) {
		return 1;
	}
#endif

	// compute k*G
	scalar_multiply(&k, &R);    <<< this calcs kG and stores it into &R
	if (pby) {
		*pby = R.y.val[0] & 1;
	}
	// r = (rx mod n)
	bn_mod(&R.x, &order256k1);
	// if r is zero, we fail
	if (bn_is_zero(&R.x)) return 2;
	bn_inverse(&k, &order256k1);      <<< this takes the modular inverse of &k over the order of secp256k1, and places it back into &k (Now &k is = (k)^-1)
	bn_read_be(priv_key, da);
	bn_multiply(&R.x, da, &order256k1);   <<< multiplies da * r and stores it into da
	for (i = 0; i < 8; i++) {
		da->val[i] += z.val[i];
		da->val[i + 1] += (da->val[i] >> 30);
		da->val[i] &= 0x3FFFFFFF;
	}
	da->val[8] += z.val[8];                  <<< This for loop and the operation after it adds the hash of the message (z) to (da*r) and stores it into da... (now da is = z+(da*r) )
	bn_multiply(da, &k, &order256k1);    <<< multiplies &k * da and stores it into &k   (Now &k is = k^-1 * (z + (da * r)).... which is = s)
	bn_mod(&k, &order256k1);               <<< mod &k (which is s) over the order.
	// if k is zero, we fail
	if (bn_is_zero(&k)) return 3;           <<< checking the s value if it is 0
...
...
...
within generate_k_rfc6979 we actually have a check for if k is 0 or not... Line 285
		if ( !bn_is_zero(secret) && bn_is_less(secret, &order256k1) ) {  <<< checking if k is in between 1 and the order - 1 (inclusive)
			return 0; // good number -> no error
		}

[hhanh00]

Ah ok. R can't be 0 if k is in the right range. S can be 0 but should be retried per ecdsa algorithm. The odds are so low though.

[johoe]

BTW there is no point on the curve with x=0, but r=0 is still possible because 04fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd036414198f66641cb0ae 1776b463ebdee3d77fe2658f021db48e2c8ac7ab4c92f83621e is a point on the curve (but nobody knows the k?).

s=0 holds if and only if z = -r*d, where z is the hash of the message and d the private key.

[hhanh00]

I got confused. As I said earlier, r = 0 isn't the same as the point at infinity.
If you can have X=n, you can have x=0.
y2 = ax3 + 7 (n) => y2 = 7 (n)
However, I don't know if you X=n is possible. Not all X are on the curve in Fp.

s = 0 is avoided because you can find the private key as you said.

[johoe]

I got confused. As I said earlier, r = 0 isn't the same as the point at infinity.
If you can have X=n, you can have x=0.
y2 = ax3 + 7 (n) => y2 = 7 (n)
However, I don't know if you X=n is possible. Not all X are on the curve in Fp.

s = 0 is avoided because you can find the private key as you said.

There are two primes, n=fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f and q=fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141.
The prime n is the modulo of the field where the two-dimensional points live in, while q is the order of the curve. Since q < n, the point with x coordinate q can be a valid point on the curve and this is the case for the "Bitcoin curve".  For the point I mentioned y^2 = q^3 + 7 (mod n) holds.

Since ECDSA computes r = R.x mod q, this point would yield r = 0.

s=0 is also avoided, because the algorithm that checks signatures divides by s. 
r=0 is avoided, because once you know the corresponding k, you can sign every message with every key with an r=0 signature (this would reveal the k).

[hhanh00]

Ah yes! You are right. I used the wrong modulus.

[gmaxwell]

Okay, the r=0 (are there points on secp256k for x=0?) or s=0 is another (unlikely to occur) problem.

R.x == 0 is not a point on the curve; but R.x congruent to 0 (mod order) _is_ on the curve, and so r can be zero because r is the x value of R mod the curve order.

(And likewise, s can be zero; e.g. I have a test in libsecp256k1 for s==0:
https://github.com/bitcoin/secp256k1/commit/8d11164bc0e03024d38d5694e81f334ea31ec238#diff-4655d106bf03045a3a50beefc800db21R1210)