search

spesmilo / electrum

Electrum Bitcoin Wallet
https://electrum.org
MIT License
7.4k stars 3.08k forks source link

Is electrum vulnerable to reusing nonce on with different public key (ECDSA pivot attack) #1876

Closed RealBTC closed 8 years ago

RealBTC commented 8 years ago

We know that reusing the nonce (k variable) can lead to private key leaking. However this was fixed in Electrum 1.9 with RFC 6979 implementation.

What I'm asking is that is the Electrum vulnerable to reusing the nonce with different public keys, does the RFC 6979 cover this vulnerability?

You can watch here what I'm talking about, they call it ECDSA pivot attack: http://livestream.com/internetsociety/hopeconf/videos/130745035

Go to 31:52, and see the guy explain this attack, it's basically due to poor random number generators yielding the same nonce (k) for different addresses.

Also they talk about sharing nonces across different private keys, does Electrum share that too in the deterministic wallet architecture?

So is Electrum protected against this attack?

dabura667 commented 8 years ago

Yes. RFC6979 covers this vulnerability with a high probability.

The way rfc6979 works is it basically hashes the private key and the message hash together with various permutations.

Since the formula to obtain s is k^-1(z + rp) mod n

Besides k, the only variables are r (which is derived from k) z (the message) and p (the private key)

So by hashing z and p together to make k (its more complicated than that, but basically that's what's happening) there are a few properties we can deduce if we assume SHA256 is a good hashing algorithm.

  1. Using the same private key, any different message will always yield a unique k.
  2. Using the same message, any different private key will always yield a unique k.
  3. Using the same private key and message, the k will always be the same.
  4. Using a different private key and different message the k will always be different.

So your concern is covered by 2 and 4

RealBTC commented 8 years ago

@dabura667 I see.

What about the nonce (k) sharing between addresses, since all private keys are derived from the seed.

Is there any link there or information leakage that could leak private key 1 from private key 2 or vice versa from the same wallet? (If for example the attacker knows that Address 1 and Address 2 are from the same wallet)

Or something similar to that, exploiting the deterministic addresses wallet structure for example.

They are also talking about the related nonce attack, at the 38:00 mark, that uses incremental nonces for each address for example in a wallet. So if k is used for Address 1, k+1 is used for Address 2, and so on. The private key is also leaking that way.

What about that?

dabura667 commented 8 years ago

Please re-read what I wrote. Your extra questions indicate that you did not understand very well.

Yes. RFC6979 protects against all of that.