Bitcoin Forum
May 06, 2024, 11:11:40 AM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: ECDSA Question about safety of deterministic wallet  (Read 606 times)
jl2012 (OP)
Legendary
*
Offline Offline

Activity: 1792
Merit: 1093


View Profile
April 13, 2014, 05:47:30 PM
 #1

It is well known that reusing the k in different signatures will leak the private key. The reuse of k is very obvious as the r for different signatures will be the same.

What about the case for BIP32 deterministic wallet? Let say an attacker knows the root public key and the chain code. If the private key holder signs 2 different messages using the same k, with 2 different addresses in the same (or different) branch of the deterministic wallet, is it possible for the attacker to detect it and deduce the private keys for the singing addresses (or even the root private key)?

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3 (Bitcoin ONLY)
LRDGENPLYrcTRssGoZrsCT1hngaH3BVkM4 (LTC)
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
1714993900
Hero Member
*
Offline Offline

Posts: 1714993900

View Profile Personal Message (Offline)

Ignore
1714993900
Reply with quote  #2

1714993900
Report to moderator
1714993900
Hero Member
*
Offline Offline

Posts: 1714993900

View Profile Personal Message (Offline)

Ignore
1714993900
Reply with quote  #2

1714993900
Report to moderator
"With e-currency based on cryptographic proof, without the need to trust a third party middleman, money can be secure and transactions effortless." -- Satoshi
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1079


Gerald Davis


View Profile
April 13, 2014, 06:01:00 PM
 #2

It is well known that reusing the k in different signatures will leak the private key. The reuse of k is very obvious as the r for different signatures will be the same.

What about the case for BIP32 deterministic wallet? Let say an attacker knows the root public key and the chain code. If the private key holder signs 2 different messages using the same k, with 2 different addresses in the same (or different) branch of the deterministic wallet, is it possible for the attacker to detect it and deduce the private keys for the singing addresses (or even the root private key)?

I don't know the direct answer to that (and I would also be interested) however the use of a random value for k is a pretty poor implementation.  There will always be edge case issues, you also will always be vulnerable to both intentional flaws and accidental defects in PRNG implementations.   

The good news is that k doesn't need to be random it just needs to be a nonce.  A transaction is already unique and a hash of that transaction is likewise "unique" (ignoring the improbable hash collision).  The future should be in deterministic signatures along with deterministic wallets.

Not only does it bypass the potential problem you outline it reduces the dependency on PRNG.  A lifetime of transactions can be done from a single random number*.  Hell you could generate your wallet seed by rolling some dice and never have a PRNG related risk again. 


* While not protocol related if the wallet is encrypted the key derivative function should use a salt value.  A truncated hash (or multiple hashes) of the seed could be used as the salt.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8382



View Profile WWW
April 13, 2014, 06:39:56 PM
 #3

It is well known that reusing the k in different signatures will leak the private key. The reuse of k is very obvious as the r for different signatures will be the same.
What about the case for BIP32 deterministic wallet? Let say an attacker knows the root public key and the chain code. If the private key holder signs 2 different messages using the same k, with 2 different addresses in the same (or different) branch of the deterministic wallet, is it possible for the attacker to detect it and deduce the private keys for the singing addresses (or even the root private key)?
You should clarify that you're talking about the non-hardened derivation, since obviously none of this applies to the hardened derivation.

But yes, that's insecure.

If you have two signatures with the same unknown nonce (k) you have two (r,s) signatures of message m_n, such that r_1==r_2 because r is just k*G.  Normally you would write out s_1 - s_2 = k^-1 * (m_1 - m_2), simplifying from the signing equation, and divide m_1 - m_2 by that yielding k.   If you replace the secret key in the signing equation by the secret key plus a known constant the first step simplifies out to s_1 - s_2 = k^-1 * (m_1 - m_2 - r*constant) since you have the chaining code you know the value of the constant so you can compute (m_1 - m_2 - r*constant) / (k^-1 * (m_1 - m_2 - r*constant)) = k.   I haven't actually tried it, but I believe it will work. This also follows naturally that if you have one private key and the chaining code, you have all the private keys on a non-hardened chain.

You should treat all bip32 private keys on the same non-hardened chain as the same private key for security purposes. They're all just a constant private key plus a set of increment values known to attackers who know the chaining code. Additionally, even ignoring bip32 I would never reuse a nonce on signatures of different messages even with different keys.
fbueller
Sr. Member
****
Offline Offline

Activity: 412
Merit: 266


View Profile
April 13, 2014, 08:46:43 PM
 #4

It is well known that reusing the k in different signatures will leak the private key. The reuse of k is very obvious as the r for different signatures will be the same.

What about the case for BIP32 deterministic wallet? Let say an attacker knows the root public key and the chain code. If the private key holder signs 2 different messages using the same k, with 2 different addresses in the same (or different) branch of the deterministic wallet, is it possible for the attacker to detect it and deduce the private keys for the singing addresses (or even the root private key)?

There is nothing in the BIP about using either a random k or another possibility like deterministic k for signatures.

So when someone spends inputs at addresses on two consecutive addresses, there is no concern unless they do it again with the same k values. If you find out the private key for each and determine the offset, which comes from the parent chain, you can compromise each private key in that chain. When you derive a BIP32 key, the keys at depth=1 are hardened, so you can't compromise the whole chain.

All said it's fairly unlikely, but still possible. pybitcointools has a function to do it.

Bitwasp Developer.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!