goodlord666


February 22, 2012, 11:59:50 AM 

so how do u get priv/pub keypairs out of the root key/Bitcoin address?
I picked a suboptimal construction, and wished I had talked to gmaxwell and sipa before I commmitted myself to it, because I like theirs better. I like the visual appeal of Armory. The general design, the logo, the name.






Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.

iddo


February 27, 2012, 04:30:25 PM 

I'd like to add to this thread the simple explanation why the crypto behind deterministic wallets is sound, i.e. why it's safe to assume that an attacker who only looks at public data (that's sent over the bitcoin network and stored in the blockchain) doesn't have an advantage if the participants use deterministic wallets instead of the regular randomindependent wallets. As discussed here, obviously if an attacker obtains the master private key and random seed then he can generate new keys, unlike the case of randomindependent wallets, but the focus here is about an attack without access to the secret data.
Since with type2 deterministic wallet the public keys are generated independently of the master private key, using key homomorphism, it's enough to say why signing transactions with pseudorandom private keys and revealing the signatures is safe from relatedkey attacks. The only assumption needed is that PRFs (pseudorandom functions) exist, which is a more conservative assumption than PKE exists. In other words it should be safer to assume that sha256 is pseudorandom than that elliptic curves give publickey encryption, though admittedly elliptic curves are used in bitcoin just for digital signatures and not PKE.
So assuming that the hash function h(x)=hash(typeseedx) is a PRF, a PPT (probabilistic poly time) adversary who's given r_i=h(i) for i=1,2,...,n=poly(security parameter) cannot distinguish them from R_i that are truly random. Now suppose (sk_i,pk_i)=keygen(r_i) and the signatures sgn_i=sign_sk_i(msg_i) are published along with the msg_i, and a PPT adversary A1 can create a signature sgn' for a new msg' so that verify_pk_j(msg',sgn') is true for some j<=n with a nonnegligible advantage compared to the case where the keys were generated with keygen(R_i) randomly. This means that there exists another PPT adversary A2 who can distinguish between pseudorandom r_i=h(i) and random R_i sequences with nonnegligible probability, simply by taking his input sequence t_i and creating (sk_i,pk_i)=keygen(t_i) and signing sgn_i=sign_sk_i(msg_i), and then simulating A1 by giving it the msg_i and sgn_i signatures and testing whether A1 successfully signs some new msg''. Therefore A2 is a PPT distinguisher and the hash function isn't a PRF, QED by contradiction.
In more simple words, this proof just says that for any efficient computation that you do on peudorandom input, the output of this computation is computationally indistinguishable from that output that you'd get in case you did the computation on truly random data. In this particular case it might seem to be a little confusing because the attacker A1 isn't supposed to be able to efficiently compute a signature for a new message. So it's a proof by contradiction, saying that if such a miraculous A1 actually existed, then we could use it to distinguish between pseudorandom input and random input. Our entire computation is efficient, because the keygen algorithm and the signing algorithm (when we now the secret keys) and the verification algorithm are efficient.
That was a generic argument why pseudorandom keys are safe from relatedkey attacks, it has nothing to do with bitcoin wallets. However, in the context of bitcoin the optimal behavior of signing only once with each key is also true for deterministic wallets, meaning that an adversary has less than 10 minutes on average to try to attack, under the (even more conservative) assumption that the address hash is a oneway function.
So the bottom line is this: let's say that you have a 10 megabytes file f1 that contains truly random data, and another file f2 that was created by taking 256 truly random bits as a seed and creating the 10 megabytes file f2=(sha256(seed1),sha256(seed2),sha256(seed3),...). If you agree that it's infeasible to tell which file is f1 and which is f2, then a deterministic wallet is right for you. If you disagree, then stick with a randomindependent wallet. If you're unsure, then go with a deterministic wallet, it's cryptographically sound and it's much safer/easier in terms of backups.




thanke


October 02, 2012, 03:37:05 AM 

The clients that offer type2 deterministic wallets (like electrum and armory) should advise their users that sharing any private key from the derived chain (not the master private key, of course) MUST be avoided. Such a sharing of a private key could happen for example by funding your MtGox account with the "Redeem private key" option. Recall the suggested computation of the key chains was this: Privatekey(type,n) = Master_private_key + H(nStype) Publickey(type,n) = Master_public_key + H(nStype)*point
where S is a random seed. The use scenario is that a "hot" machine (connected to the internet and potentially vulnerable) generates a chain of public keys, and for that purpose stores Master_public_key as well as S. In a reasonable threat model both values become available to an attacker because the "hot" machine is vulnerable. Since the serial numbers n and the type can be guessed, a single leaked private key will leak Master_private_key as well by a simple substraction in the finite field underlying secp256k1. Conclusion: Users should be advised that ANY private key from the generated key chain is to be secured with the same security level as the master private key. This seems to affect not only the implementation of deterministic wallets in electrum and armory but also the hierarchical deterministic wallets suggested in BIP 032: We define the child key derivation function CKD((kpar,cpar),n), which takes a parent extended secret key (kpar,cpar) and a 32bit integer n, to produce a child extended secret key (kn,cn).
To define (kn,cn) = CKD((kpar,cpar),n):
call I = HMACSHA512(Key=cpar, Data=kpar*G  n), where kpar*G is the public key corresponding to kpar,  is concatenation, and n is encoded as a 32 bits unsigned integer, most significant byte first. Split I into two 32byte sequences, IL and IR. kn is equal to IL*kpar. cn is equal to IR. We also define a version that operates on extended public keys instead of private ones: (Kn,cn) = CKD'((Kpar,cpar),n):
call I = HMACSHA512(Key=cpar, Data=Kpar  n), where n is encoded a 32 bits unsigned integer, most significant byte first. Split I into two 32byte sequences, IL and IR. Kn is equal to IL*Kpar. cn is equal to IR.
Suppose the "hot" machine of some main business wants to be able to automatically generate extended public keys (Kn,cn). It needs to store (Kpar,cpar) to do that. Suppose it computes the corresponding extended secret key (kn,cn) on a "cold" machine and hands it to the business' subbranch numbered n, so that the subbranch can work independently. Now, if the information (Kpar,cpar) stored on the main business' "hot" machine leaks then the subbranch can obtatin the main business master private key kpar by these computations:  I = HMACSHA512(Key=cpar, Data=Kpar  n)
 Split I into two 32byte sequences, IL and IR
 kpar = IL^(1)*kn (arithmetic in the finite field underlying secp256k1)
Conclusion: In a scenario where derived secret keys are handed over to subbranches, the derived public keys MUST not be generated on the fly on "hot" machines. Instead, even Kpar must be stored "cold". To some extend this contradicts the original idea of hierarchical deterministic wallets.





Pieter Wuille


October 02, 2012, 09:59:43 PM 

Conclusion: In a scenario where derived secret keys are handed over to subbranches, the derived public keys MUST not be generated on the fly on "hot" machines. Instead, even Kpar must be stored "cold". To some extend this contradicts the original idea of hierarchical deterministic wallets.
Thanks for noticing this. I must admit that I never considered this scenario.

aka sipa, core dev team
Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa



justusranvier


December 05, 2012, 05:43:09 PM 

I'm trying to understand the full implications of accidentally revealing a individual private key. Suppose I gave Mt Gox the extended public key m/0/0. They would then be able to generate m/0/0/0...k themselves in order to send each future BTC withdrawal to a unique address without further interaction from me. If I accidentally reveal private key m/0/1/42 this means they can generate all private keys in the m/0/1/0...k series as well. What does that mean for other branches like m/1, m/2, etc?




jgarzik


December 05, 2012, 05:46:47 PM 

In general, deterministic wallets (a) make life easier while (b) increasing the security threat (e.g. decreasing overall security). Before, if one private key was compromised, others were safe. Now, the picture is not so clear.
And if the seed is compromised, all keys are thus compromised.
If all private keys are covered by the same master key, then the security situation is largely unchanged, and the threat model focuses on protecting the seed (rather than a wallet full of keys).
However, private keys are not necessarily all tied together.

Jeff Garzik, bitcoin core dev team and BitPay engineer; opinions are my own, not my employer. Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj



justusranvier


December 05, 2012, 06:09:25 PM 

It seems like it should be possible to compartmentalize the risk. Accidentally revealing one private key will compromise the entire branch but it should be possible to limit the damage to that branch without affecting others.




nybble41


December 05, 2012, 06:20:35 PM 

+1 for type2 deterministic wallets
As currently proposed, if you have the master public key you can, in principle, iterate over the serial number to generate all possible addresses. However, there is no hard upper bound on the serial number, or the sizes of any gaps in the sequence of used addresses. Would it be possible to include some identifying informationin particular, the serial numberin the address itself, so that one could easily check whether a given address matches a known master public key without scanning through all possible serial numbers? Or is the address format too inflexible for that?




etotheipi


December 05, 2012, 08:54:47 PM 

It seems like it should be possible to compartmentalize the risk. Accidentally revealing one private key will compromise the entire branch but it should be possible to limit the damage to that branch without affecting others.
The difference in security model between deterministic and nondeterministic wallets is really quite tiny in practice. There's very few situations where that difference is the results in devastating compromise with a deterministic wallet, that wouldn't also be devastating to a randomized wallet. And then that is compounded by the fact that there's very few situations where an attacker would get one private key but not the others: they usually get nothing, or they get everything. In terms of users revealing private keys from their wallet  that is a practice that just shouldn't happen. If they are doing that, then yes, the deterministic wallet is less safe, but the user is exercising poor judgment and likely to compromise themselves other ways (they should be educated about this). The reason why the security difference is effectively small between a compromise of either system, is because existing BitcoinQt wallet behavior of pregenerating a pool of 100 addresses actually makes the two very similar. Sure, the BitcoinQt wallet "unsteals" itself after some amount of time, but that time may be very far in the future when the user actually gets through those 100 and starts generating more. Most of the coinstealing will occur with the coins already available in the wallet, since there's no guarantee that coins will be added or removed from the wallet in the future to risk losing them if the user spends them. Perhaps if the attacker knows some information about the user and knows they will be receiving coins in 3 months from now and want to wait for that to occur then the randomized wallet is preferred (for the user)... but then that is effectively a targeted attack, which is expected to be much more difficult to deal with, anyway. In reality, the biggest risk to the average user is not timestaggered wallet theft, but loss of coins from HDD loss or wallet corruption. The ability to make a single backup, ever, far outweighs so many other risks faced by regular users. That's not to say the randomized key model is inferior for all use cases, but the default very clearly should be deterministic one (let knowledgeable users who understand the various factors make the decision to change from the default).




justusranvier


December 05, 2012, 09:18:45 PM 

I'm still not sure about the answer to my original question. As BIP34 is currently written, if an attacker knows the chain code associated with m/0/0 and knows one of the private keys in the series m/0/0/0...k series can also he recover the private key of any other branch in the tree, or does m/1, m/2, etc use a different chain code that can't be derived from the m/0 chain code alone?




etotheipi


December 05, 2012, 09:22:26 PM 

I'm still not sure about the answer to my original question. As BIP34 is currently written, if an attacker knows the chain code associated with m/0/0 and knows one of the private keys in the series m/0/0/0...k series can also he recover the private key of any other branch in the tree, or does m/1, m/2, etc use a different chain code that can't be derived from the m/0 chain code alone?
If the attacker a single private key and the same key's chaincode, m/i/j/k, he can only determine m/i/j/k/X. You can't reverse the chain or get to other chains, or even determine "brothers" in the same chain. You can only traverse down a separate chain specific to that key (which is not ever used in BIP 32 wallets, by default)




justusranvier


December 05, 2012, 10:06:03 PM 

If the attacker a single private key and the same key's chaincode, m/i/j/k, he can only determine m/i/j/k/X. You can't reverse the chain or get to other chains, or even determine "brothers" in the same chain. You can only traverse down a separate chain specific to that key (which is not ever used in BIP 32 wallets, by default)
So what is this about? Conclusion: In a scenario where derived secret keys are handed over to subbranches, the derived public keys MUST not be generated on the fly on "hot" machines. Instead, even Kpar must be stored "cold". To some extend this contradicts the original idea of hierarchical deterministic wallets.
Thanks for noticing this. I must admit that I never considered this scenario. I understood this to mean if the attacker knows the extended public key (which includes the chain code) of a node, and any one of the associated private keys, then the attacker can also recover all the sibling private keys. Is this not correct?




thanke


December 06, 2012, 07:56:48 AM 

Conclusion: In a scenario where derived secret keys are handed over to subbranches, the derived public keys MUST not be generated on the fly on "hot" machines. Instead, even Kpar must be stored "cold". To some extend this contradicts the original idea of hierarchical deterministic wallets.
Thanks for noticing this. I must admit that I never considered this scenario. I understood this to mean if the attacker knows the extended public key (which includes the chain code) of a node, and any one of the associated private keys, then the attacker can also recover all the sibling private keys. Is this not correct? Correct. It is the chaincode that you gave away which determines (or limits) the "damage" that a leaked private key does. If you give away the chaincode of m/0/0 to someone then that person knows how all private keys below m/0/0 are linked to the private key of m/0/0. Consequently, if any private key below m/0/0 leaks to that person, say of m/0/0/42, then that person can compute the private key of m/0/0 and from that the private key of all m/0/0/x.. in the branch of m/0/0 including siblings of m/0/0/42. However, assuming you didn't give away other chaincodes, that person cannot compute the private key of m/0 or m/0/1. I don't think that type2 deterministic wallets should be the default in any client, because users have to think and care about what they export from their wallets (chaincodes, extended pubkeys, private keys) and how they secure the exported data. Type1 deterministic wallets seem to be a more suitable default. If type2 wallets were default then the average user should not be given the opportunity to export chaincodes. So there should be no "extended pubkeys" ("pub" suggesting that they can be exported) but only "extended privkeys". As far as key hierarchies go, do we have any significant application for it yet? I would really like to be convinced that we absolutely need them.




iddo


December 06, 2012, 09:20:56 AM 

Type1 deterministic wallets seem to be a more suitable default.
I think that there's some confusion here, type2 should always be more secure than type1, for any kind of user. With type1, the secret seed derives the actual privkeys, therefore if the secret seed is compromised then all of your privkeys leak. With type2, if the hash derivation function includes the secret seed as one of the concatenated inputs (as in the OP of this thread), then the secret seed in itself can only derive pubkeys, and unless the attacker also gains access to the additional (master) privkey secret, all your privkeys are still provably secure. The disadvantage of having the secret seed as one of the concatenated inputs of the derivation function is that the 3rdparty couldn't generate new pubkeys on its own, without knowing the secret seed. But the other advantages of type2 still hold, namely that the owner of the wallet can generate new pubkeys without accessing (decrypting) his privkeys, and that for backup purposes you only need to store your master privkey and secret seed (this is an advantage over the regular randomindependent wallet, not over type1 wallet). If BIP 0032 doesn't include an option to have a secret as one of the inputs of the hash derivation function, then I think that this kind of mode should be added to BIP 0032. This could even be the default, if we're worried about scenarios where users aren't careful and compromise a branch in their key hierarchy. We might wish to give users the option to have different secret seeds for particular branches in the key hierarchy, and store all these seeds in the wallet file (and warn the user that he needs to backup his wallet when he creates a new seed).




thanke


December 06, 2012, 09:51:10 AM 

Type1 deterministic wallets seem to be a more suitable default.
I think that there's some confusion here, type2 should always be more secure than type1, for any kind of user. Agree. With type2, if the hash derivation function includes the secret seed as one of the concatenated inputs (as in the OP of this thread), then the secret seed in itself can only derive pubkeys, and unless the attacker also gains access to the additional (master) privkey secret, all your privkeys are still provably secure.
"the secret seed in itself can only derive pubkeys" should be "the secret seed in itself can only derive relations (in the sense of differences) between pubkeys and relations between privkeys". "unless the attacker also gains access to the additional (master) privkey secret" should be "unless the attacker also gains access to a privkey (master or derived)". The disadvantage of having the secret seed as one of the concatenated inputs of the derivation function is that the 3rdparty couldn't generate new pubkeys on its own, without knowing the secret seed. But the other advantages of type2 still hold, namely that the owner of the wallet can generate new pubkeys without accessing (decrypting) his privkeys, [..]
Depends on how you see it. If I want to generate new pubkeys without accessing my privkeys it means that, securitywise, I want to treat my secret seed differently (i.e. less secure) than my privkeys. To me this is the same as having a 3rd party generate them (and having access to my secret seed). If BIP 0032 doesn't include an option to have a secret as one of the inputs of the hash derivation function, then I think that this kind of mode should be added to BIP 0032. This could even be the default, if we're worried about scenarios where users aren't careful and compromise a branch in their key hierarchy.
This mode could be a "selfseeded" mode, where the chaincode is not inherited from some parent key but is a hash of the privkey. Then it suffices to backup the privkey alone. And yes, this should probably be the default, and an inherited chaincode should not only be used on explicit request. We might wish to give users the option to have different secret seeds for particular branches in the key hierarchy, and store all these seeds in the wallet file (and warn the user that he needs to backup his wallet when he creates a new seed).
Maybe two seeds are enough, one inherited, one selfseed (=hash of privkey).




justusranvier


December 06, 2012, 10:07:41 AM 

As far as key hierarchies go, do we have any significant application for it yet? I would really like to be convinced that we absolutely need them.
I listed one in an earlier post. If I'm going to buy Bitcoins on an exchange I'd like to be able to give the exchange an extended public key so that they can automatically generate new withdrawal addresses without further interaction. Similar I'd like the exchange to give me an extended public key so that my HDaware client can automatically generate the next unique deposit address every time I want to add Bitcoins to my account. If Wikileaks wants to receive donations without allowing a third party to monitor how much they have received or who the donors are they could use an BIP32 HD wallet. Every visitor who requests a donation address gets an extended public key instead of a regular public key, so now the donor can generate his own unique donation addresses without needing to visit the Wikileaks web page every time. Clients that understand HD wallets could be configured to store a counter in the address book entry of each extended public key and to by default automatically send to a unique address when that entry is selected by the user.




jl2012
Legendary
Offline
Activity: 1134
Ignore


December 06, 2012, 10:08:24 AM 

I feel confused.
For deterministic wallets allowing generation of public keys without private keys, the chain code must be included in the watchonly wallet. Therefore, the chain code have to be kept online. In the following discussion, I assume the chain code(s) are known to the public.
In Armory, if someone knows the private key of sequence number x, he will be able to determine all private keys with sequence number > x, but not for those sequence number <x. This is guaranteed by the EC algorithm.
Here are my questions for BIP32:
Assuming all chain codes are known, if private key m/i/j is known, :
1. are every private keys under m/i/j known? (I think the answer is yes)
2. are every private keys under m/i/j+1 known? (The answer should be yes if it followed the Armory model)
3. are every private keys under m/i/j1 known? (The answer should be no if it followed the Armory model)
4. are every private keys under m/i known?
5. are every private keys under m/i+1 known?
6. are every private keys under m/i1 known?
7. is the m known?

Donation address: 1CiZPrEJdN4FJcqdLdgVLzT8tgCXxT5ion



thanke


December 06, 2012, 11:25:09 AM 

Here are my questions for BIP32:
Assuming all chain codes are known, if private key m/i/j is known, :
1. are every private keys under m/i/j known? (I think the answer is yes)
2. are every private keys under m/i/j+1 known? (The answer should be yes if it followed the Armory model)
3. are every private keys under m/i/j1 known? (The answer should be no if it followed the Armory model)
4. are every private keys under m/i known?
5. are every private keys under m/i+1 known?
6. are every private keys under m/i1 known?
7. is the m known?
Answer is yes to all of them. (Assuming that all pubkeys are also known, not only chaincodes, so in fact all extended pubkeys are known. I thought this is what you meant to ask.)




jl2012
Legendary
Offline
Activity: 1134
Ignore


December 06, 2012, 12:18:15 PM 

Here are my questions for BIP32:
Assuming all chain codes are known, if private key m/i/j is known, :
1. are every private keys under m/i/j known? (I think the answer is yes)
2. are every private keys under m/i/j+1 known? (The answer should be yes if it followed the Armory model)
3. are every private keys under m/i/j1 known? (The answer should be no if it followed the Armory model)
4. are every private keys under m/i known?
5. are every private keys under m/i+1 known?
6. are every private keys under m/i1 known?
7. is the m known?
Answer is yes to all of them. (Assuming that all pubkeys are also known, not only chaincodes, so in fact all extended pubkeys are known. I thought this is what you meant to ask.) Sorry, I mean private keys, not public keys

Donation address: 1CiZPrEJdN4FJcqdLdgVLzT8tgCXxT5ion



