Deterministic Wallets and ECDSA | Bitcointalksearch.org

iddo

sr. member

Activity: 360

Merit: 251

Quote from: kjj on April 28, 2013, 09:50:37 AM

Quote from: iddo on April 28, 2013, 09:42:48 AM

Quote from: kjj on April 28, 2013, 09:07:53 AM

Also, careful implementations design their generation functions so that even if a few private keys leak, the sequence as a whole is not compromised.

If one particular privkey leaks and its corresponding chaincode also leaks, then the entire subtree that's rooted at that particular privkey also leaks, meaning that all the privkeys in that subtree of the HD wallet leak. And even worse, if that particular privkey was derived via type-2, and the parent chaincode leaks, then its parent privkey also leaks.
This means that if the HD wallet uses only type-2 derivations (this won't be the case in the default HD wallet layout), and the chaincodes aren't kept secret, then leakage of a single privkey implies that the entire HD wallet leaks.

As usual, the biggest problem in PKI is key management.

I do remember when the debate got around to which information you needed to give to a webserver so that it could generate public keys to hand out as addresses, and the consequences of the loss of such information. I wasn't really paying attention by that point.

Right. The moral is that you should keep your chaincodes private, and if you give (say) a webserver the ability to generate pubkeys for you then you may prefer to derive that keypair from its parent via type-1 instead of type-2, to minimize the damage in case of leakage.

kjj

legendary

Activity: 1302

Merit: 1026

Quote from: optimator on April 28, 2013, 09:57:49 AM

Quote from: iddo on April 28, 2013, 09:31:55 AM

Quote from: optimator on April 28, 2013, 08:50:15 AM

My understanding is that if either k or dA are NOT truly random an attack could be performed.

Your understanding is wrong. This has nothing to do with the internals of ECDSA, if the keygen that's used to create the privkeys uses pseudorandom bits instead of truly random bits, and there exists an efficient attack in the pseudorandom case, then this implies that the pseudorandom generator (SHA2 in our case) isn't actually pseudorandom. You can see this phrased as a formal proof here: https://bitcointalksearch.org/topic/m.771903

Where my understanding came from is the Sony playstation hack. My understanding is that since the random number k was repeatedly used the hackers were able to determine dA. My thinking was that if a deterministic algo changes dA in a predictable way, it makes the attack harder, but not impossible (somewhat like a timing attack).

You've given me a great starting point for a better understanding. Thanks!

You are quite correct, if dA was predictable, it would be possible to break. A lot of effort went into making sure that dA was not predictable.

optimator

sr. member

Activity: 351

Merit: 250

Quote from: iddo on April 28, 2013, 09:31:55 AM

Quote from: optimator on April 28, 2013, 08:50:15 AM

My understanding is that if either k or dA are NOT truly random an attack could be performed.

Your understanding is wrong. This has nothing to do with the internals of ECDSA, if the keygen that's used to create the privkeys uses pseudorandom bits instead of truly random bits, and there exists an efficient attack in the pseudorandom case, then this implies that the pseudorandom generator (SHA2 in our case) isn't actually pseudorandom. You can see this phrased as a formal proof here: https://bitcointalksearch.org/topic/m.771903

Where my understanding came from is the Sony playstation hack. My understanding is that since the random number k was repeatedly used the hackers were able to determine dA. My thinking was that if a deterministic algo changes dA in a predictable way, it makes the attack harder, but not impossible (somewhat like a timing attack).

You've given me a great starting point for a better understanding. Thanks!

kjj

legendary

Activity: 1302

Merit: 1026

Quote from: iddo on April 28, 2013, 09:42:48 AM

Quote from: kjj on April 28, 2013, 09:07:53 AM

Also, careful implementations design their generation functions so that even if a few private keys leak, the sequence as a whole is not compromised.

If one particular privkey leaks and its corresponding chaincode also leaks, then the entire subtree that's rooted at that particular privkey also leaks, meaning that all the privkeys in that subtree of the HD wallet leak. And even worse, if that particular privkey was derived via type-2, and the parent chaincode leaks, then its parent privkey also leaks.
This means that if the HD wallet uses only type-2 derivations (this won't be the case in the default HD wallet layout), and the chaincodes aren't kept secret, then leakage of a single privkey implies that the entire HD wallet leaks.

As usual, the biggest problem in PKI is key management.

I do remember when the debate got around to which information you needed to give to a webserver so that it could generate public keys to hand out as addresses, and the consequences of the loss of such information. I wasn't really paying attention by that point.

iddo

sr. member

Activity: 360

Merit: 251

Quote from: kjj on April 28, 2013, 09:07:53 AM

Also, careful implementations design their generation functions so that even if a few private keys leak, the sequence as a whole is not compromised.

If one particular privkey leaks and its corresponding chaincode also leaks, then the entire subtree that's rooted at that particular privkey also leaks, meaning that all the privkeys in that subtree of the HD wallet leak. And even worse, if that particular privkey was derived via type-2, and the parent chaincode leaks, then its parent privkey also leaks.
This means that if the HD wallet uses only type-2 derivations (this won't be the case in the default HD wallet layout), and the chaincodes aren't kept secret, then leakage of a single privkey implies that the entire HD wallet leaks.

iddo

sr. member

Activity: 360

Merit: 251

Quote from: optimator on April 28, 2013, 08:50:15 AM

My understanding is that if either k or dA are NOT truly random an attack could be performed.

Your understanding is wrong. This has nothing to do with the internals of ECDSA, if the keygen that's used to create the privkeys uses pseudorandom bits instead of truly random bits, and there exists an efficient attack in the pseudorandom case, then this implies that the pseudorandom generator (SHA2 in our case) isn't actually pseudorandom. You can see this phrased as a formal proof here: https://bitcointalksearch.org/topic/m.771903

kjj

legendary

Activity: 1302

Merit: 1026

k is chosen randomly for each signing.

As for the private key, those are secret to begin with. Also, careful implementations design their generation functions so that even if a few private keys leak, the sequence as a whole is not compromised. There was extensive debate on the subject a while back that you can probably find with some searching.

Armory's implementation is very solid. etotheipi is a bright guy to begin with, and he solicited input from the community, and paid attention to what he heard. The BIP for deterministic wallets was done the same way.

If I recall correctly, the function is something along the lines of pubkey_i+1=sha256(G*pubkey_i*rootkey). Using bitcoin means that you already trust that both sha256 and EC multiplication are irreversible, so you should feel pretty safe using the sequence generated from this.

optimator

sr. member

Activity: 351

Merit: 250

I'd like to ask this question, because I keep thinking about it, but I am not at all well versed in cryptography.

Does a deterministic wallet compromise the ECDSA algo in any way?

My understanding is the strength in ECDSA is that there are two unknowns which make it impossible to "reverse engineer" the solution (my words).

So, you have R = k*G and S= k^-1(z + dA*R) mod p; where k being a random number and dA being a random private key are the two unknowns.

My understanding is that if either k or dA are NOT truly random an attack could be performed. So, two part question:

1. What makes k random for each deterministic address?
2. Since dA is deterministic, doesn't that inherently negate the randomness of dA? That is, the deterministic nature opens EDSA up to something akin to a timing attack?

Thanks, just trying to learn!

Topic: Deterministic Wallets and ECDSA (Read 1189 times)