dabura667 (OP)


January 02, 2015, 08:37:35 AM Last edit: January 02, 2015, 01:54:39 PM by dabura667 

I may be nitpicking, 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/884I added a similar badrs function to pythonecdsa 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 pythonecdsa perfectly (I even tried up to badrs = 30 and it was fine. https://tools.ietf.org/html/rfc6979#section3.2If you follow Step h from after the k = bits2int(T) downward, then back up to the beginning of Step h to loop. 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 pythonecdsa includes it in the loop. Including this commit will make the behavior be 100% rfc 6979 compliant. https://github.com/blockchain/MyWallet/pull/115RFC 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 rehashing 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 pythonecdsa) and then for some reason posted those two signed transactions in the public space somehow. Edit: Just put in PR to bitcoinjslib: https://github.com/bitcoinjs/bitcoinjslib/pull/336

My Tip Address: 1DXcHTJS2DJ3xDoxw22wCt11FeAsgfzdBU



hhanh00


January 02, 2015, 02:36:43 PM 

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




johoe


January 02, 2015, 06:20:56 PM 

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 doubleSHA256 while all rfc6979 implementations use HMACsingleSHA256. 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 hopeless to bruteforce. 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?

Donations to 1CF62UFWXiKqFUmgQMUby9DpEW5LXjypU3



gmaxwell
Moderator
Legendary
Offline
Activity: 4200
Merit: 8493


January 02, 2015, 07:02:34 PM Last edit: January 02, 2015, 07:15:58 PM by 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 allcaps (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 illformed adhoc things). In this case the suggestion doesn't even appear to be SHOULD level. It's common for foundontheinternet ECC cryptoimplementations 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 (OP)


January 02, 2015, 07:08:42 PM 

@dabura667: did you test it against that example?
They didn't have any secp256k1 test vectors

My Tip Address: 1DXcHTJS2DJ3xDoxw22wCt11FeAsgfzdBU



hhanh00


January 03, 2015, 01:55:14 AM 

@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 (OP)


January 03, 2015, 05:23:10 AM 

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 reimplementation) against the test vectors in the RFC. However, it is obvious if you follow the RFC6979 test case that they "regenerate 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

My Tip Address: 1DXcHTJS2DJ3xDoxw22wCt11FeAsgfzdBU



hhanh00


January 03, 2015, 05:39:24 AM 

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 reimplementation) against the test vectors in the RFC. However, it is obvious if you follow the RFC6979 test case that they "regenerate 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 (OP)


January 03, 2015, 05:46:13 AM 

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)

My Tip Address: 1DXcHTJS2DJ3xDoxw22wCt11FeAsgfzdBU



johoe


January 03, 2015, 09:09:46 AM 

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

Donations to 1CF62UFWXiKqFUmgQMUby9DpEW5LXjypU3



hhanh00


January 03, 2015, 09:21:51 AM 

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 n1 simply because kG <> 0.




dabura667 (OP)


January 03, 2015, 11:04:41 AM 

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

My Tip Address: 1DXcHTJS2DJ3xDoxw22wCt11FeAsgfzdBU



dabura667 (OP)


January 03, 2015, 11:14:33 AM 

#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 }

My Tip Address: 1DXcHTJS2DJ3xDoxw22wCt11FeAsgfzdBU



hhanh00


January 03, 2015, 12:28:01 PM 

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


January 03, 2015, 12:44:09 PM 

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.

Donations to 1CF62UFWXiKqFUmgQMUby9DpEW5LXjypU3



hhanh00


January 03, 2015, 01:47:03 PM 

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


January 03, 2015, 02:09:40 PM 

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

Donations to 1CF62UFWXiKqFUmgQMUby9DpEW5LXjypU3



hhanh00


January 03, 2015, 03:40:19 PM 

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





