Bitcoinjs-lib: Signing includes random data, but I'm seeing the same signature every time
I noticed the ECKey sign function is creating the same signature for a given curve, key, and hash. It is my understanding that the ECC security should include random data and therefore create unique signatures each time this is called.
ECKey.sign: https://github.com/bitcoinjs/bitcoinjs-lib/blob/e42c497a3c9afe67c86ba0a602b5a0e9bd66e604/src/eckey.js#L80-L82
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Security
How can I add the secure random data to the signature?
jcalfee
All 17 comments
Someone has explained to me that this looks fine they way it is used because your using deterministicGenerateK to create the random data used for the signature. My challenge is to produce a canonical signature using the same message hash. I'm attempting to solve this by using a sequence nonce in my copy of deterministicGenerateK so I try on average of 3 times before I get a signature that passes as canonical.
jcalfee
on 31 Dec 2014
@jcalfee you are correct that we are using RFC6979.
I think what you may be after is simply a compact signature.
To get 'canonical' r, s values, you just need to pad the resultant r, s values.
Let me know if this helps.
dcousens
on 1 Jan 2015
I am using compact.. Our chain did reject the compact signature making the change I made necessary.
This is the code I need to satisfy:
Someone speculated on this part of the code:
ECDSA are poorly engineered, they're 256+1 bit keys and IIRC 512+1bit signatures.
So he's probably generating keys that make sure the sign bit is 0, which effectively halves the signature strength but that's not really a problem.
And generating signatures in a loop until he gets one that fits.
jcalfee
on 4 Jan 2015
@jcalfee I'm still seeing this behavior in 2018 for the sign function. Was a solution never found/included in bitcoinjs? Sorry to re-open, but I was shocked to discover this.
EvilJordan
on 8 Feb 2018
If it wasn't clear from the above, the behaviour of RFC6979 is intentional.
dcousens
on 8 Feb 2018
Huh. So k is not random and one always gets the same signature for a given private key + message.
What's interesting is this BitcoinPHP ECDSA implementation produces different signatures each time the sign function is run, and verifies successfully within its own implementation and with bitcoinjs.
So what does that mean? BitcoinPHP is non-conforming, but works?
EvilJordan
on 8 Feb 2018
So what does that mean? BitcoinPHP is non-conforming, but works?
Exactly that.
The danger is that if the RNG [used by BitcoinPHP] is in any way predictable, you can recover the private key.
dcousens
on 8 Feb 2018
@EvilJordan ECDSA signatures do not have to be "different everytime"... the only requirement is that:
- You never reuse k values. Ever.
RFC 6979 basically says.
Well, since r is:
var r = G.mul(k).x // grab x coordinate of the point
and s is:
var s = (z + r * q) / k
(Where z = hash of message being signed, G is the secp256k1 generator point, and q is the private key)
If you look at the s equation (I removed mod n for clarity) you notice that if you remove k and r (because r is derived from k) all you have is z and q left (message hash and private key)
So if you hash z and hash q then stick those two hashes together and hash that, and use that result as k, you are guaranteed that you will not EVER generate the same k twice without it being the exact same signature. which gives no new information to an attacker.
The vulnerability for reusing k is because you have two different s values for the same k (and r) values with the same private key used... then you can calculate the private key using the following:
s1 = (z1 + r * q) / k // using same private key and same k value (which gives same r value)
s2 = (z2 + r * q) / k // but different messages, therefore different s values.
s1 - s2 = ((z1 + r * q) / k) - ((z2 + r * q) / k)
s1 - s2 = ((z1 + r * q) - (z2 + r * q)) / k
s1 - s2 = (z1 - z2) / k
k = (z1 - z2) / (s1 - s2)
// now we have k, plug into either s formula
s1 = (z1 + r * q) / k
k * s1 = (z1 + r * q)
k * s1 - z1 = rq
q = (k * s1 - z1) / r
// we know k, s, z, and r... so we can calculate the private key
BUT since we use RFC6979, there is NEVER a chance for "The same r is used with different s values on different messages with the same private key" and the ability to calculate the k value requires knowledge of the private key.
junderw
on 8 Feb 2018
@junderw the code looks less scary than the math TBH
dcousens
on 8 Feb 2018
@dcousens lol, integration tests to make sure our library can properly steal bitcoins from people using worse libraries ;-) (just kidding)
TIL we had this. lol
describe('bitcoinjs-lib (crypto)', function () {
it('can recover a private key from duplicate R values', function () {
Very cool. Thanks for the explanation, everyone!
EvilJordan
on 8 Feb 2018
@EvilJordan I took a peek at the PHP library you linked.
I highly recommend not using that library....... o_0
junderw
on 8 Feb 2018
@junderw Yeah, I don't like it, either. I'm trying to rewrite as I can't find any other available alternatives, but I admittedly am not very strong with this very intense crypto-math, so it's not going well!
EvilJordan
on 8 Feb 2018
For future generations that may stumble on this thread, this is a much better library for PHP-related Elliptic Curve Cryptography.
I'm abandoning ship on my own work and switching to this. I am not a madman.
EvilJordan
on 8 Feb 2018
Hate to message with just a plug @EvilJordan, but for PHP you might find this library useful: https://github.com/Bit-Wasp/bitcoin-php, it depends on phpecc also, plus has libsecp256k1 bindings :)
afk11
on 8 Feb 2018
@afk11
P2SH & Segregated witness scripts
Does this mean it can sign/verify segwit??
EvilJordan
on 8 Feb 2018
Yep, anything you can sign you can also verify, also using libbitcoinconsensus if you'd rather avoid a native PHP script interpreter :P
afk11
on 8 Feb 2018
Related issues
LeonYanghaha
路
3Comments
tuyennvtb
路
3Comments
rbndg
路
3Comments
panpan2
路
3Comments
dakk
路
3Comments