optimator (OP)
|
|
April 28, 2013, 01:50:15 PM |
|
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!
|
|
|
|
kjj
Legendary
Offline
Activity: 1302
Merit: 1026
|
|
April 28, 2013, 02:07:53 PM |
|
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 pubkeyi+1=sha256(G*pubkeyi*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.
|
17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8 I routinely ignore posters with paid advertising in their sigs. You should too.
|
|
|
iddo
|
|
April 28, 2013, 02:31:55 PM Last edit: April 28, 2013, 02:43:23 PM by iddo |
|
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://bitcointalk.org/index.php?topic=19137.msg771903#msg771903
|
|
|
|
iddo
|
|
April 28, 2013, 02:42:48 PM |
|
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.
|
|
|
|
kjj
Legendary
Offline
Activity: 1302
Merit: 1026
|
|
April 28, 2013, 02:50:37 PM |
|
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.
|
17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8 I routinely ignore posters with paid advertising in their sigs. You should too.
|
|
|
optimator (OP)
|
|
April 28, 2013, 02:57:49 PM |
|
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://bitcointalk.org/index.php?topic=19137.msg771903#msg771903Where 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
Offline
Activity: 1302
Merit: 1026
|
|
April 28, 2013, 03:16:29 PM |
|
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://bitcointalk.org/index.php?topic=19137.msg771903#msg771903Where 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.
|
17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8 I routinely ignore posters with paid advertising in their sigs. You should too.
|
|
|
iddo
|
|
April 28, 2013, 03:17:02 PM |
|
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.
|
|
|
|
|