Pages:
Author

Topic: Deterministic wallets - page 6. (Read 48255 times)

member
Activity: 63
Merit: 10
Vires in Numeris
May 03, 2013, 07:33:33 PM
Wouldn't it just be simpler to add the base point incrementally? Why not just start out with a private and public key, store the private one securely, then just keep on adding the base point to the public key to get new addresses.
sr. member
Activity: 360
Merit: 251
May 03, 2013, 02:05:27 PM
Hello Pieter,

  • Is there a use case to allow updating keys without updating chain codes, that's worth breaking the current spec for?

The supposed use case is described in post #167,#172,#176 (edit: to be self-contained here, the use case is that A gives B some pubkey and the corresponding chaincode so that B could derive the subsequent pubkeys via type-2, then A creates a new keypair and gives the new pubkey to B, to be used with the same old chaincode, therefore there's no need to send a new chaincode via eavesdropping-resistant communication, but the communication still has to be authenticated otherwise anyone could impersonate A). I personally don't think that this use case resembles something that would arise frequently in practice, but even if thanke or anyone disagrees with my assessment, the following two issues remain: (1) we can support pretty much the same exact use case with BIP32, just with one extra session of secure communication between the two parties, in which a new chaincode is sent, and (2) so far we haven't come up with a way to achieve thanke's goal without losing other properties that are more desirable (except maybe if we bloat the wallet with two separate chaincodes for each key), namely type-1/type-2 mixing and the necessity to know the chaincode in addition to the privkey in order to derive its subtree.

It seems to me that the issues that thanke raised proved to be be a good sanity check that shows that the BIP32 design is good. Maybe thanke could improve on his ideas, but even if he does, the use case seems rather insignificant as far as I can see, and I believe that it's more important to finalize BIP32 as soon as possible.

  • Is there a reason to disallow secret derivation after public derivation?

IMHO absolutely not, because I see practical use cases for doing it (posts #122, #203, #205), and I don't see any reason to disallow it.


Few last things before you finalize BIP32: If I understand correctly, the length extension attack on SHA2 is irrelevant here, because of the HMAC ? It could be an interesting idea to replace SHA2 with SHA3 anyway, depending on who you believe (link). And regarding the initial seed, I suppose that you could specify that the maximal entropy that makes sense is 512 bits.
legendary
Activity: 1072
Merit: 1170
May 03, 2013, 01:10:13 PM
Hey iddo & thanke,

I love how thoroughly you've been discussing this, though I must admit I haven't read the through entire discussion.

I've updated the specification to use addition instead of multiplication, but now I'd like to make the BIP32 specification final soon.

So my questions are:
  • Is there a use case to allow updating keys without updating chain codes, that's worth breaking the current spec for?
  • Is there a reason to disallow secret derivation after public derivation?

If not, I'd like the current version to be final.

Grau: The thread has progressed quite a bit since your comment, but I agree it makes sense to have a set of "guidelines for wallet behaviour" that will make working with these wallets easier, though in no way required.


sr. member
Activity: 360
Merit: 251
April 30, 2013, 10:41:10 AM
There can be reasonable scenarios where A and B know each other well, so A would trust B with a subtree that they'd both share. Also, another use case can be when A and B are the same person, i.e. we have only one person A who wishes to consider his full HD wallet as cold storage (savings account), but wishes to have a subtree of that wallet as hot storage (checking account), so he can transact with the hot storage privkeys as they'd be on his online machine. For example, MtGox claims to have 90%-95% of their bitcoins in cold storage. So for this use case, you will derive a child node via type-1 and treat that child as hot storage, meaning that leakage of any privkeys in your "hot storage wallet" won't affect your "cold storage wallet". Additionally, it'd be a nice feature if the client allows you to export a subtree as a new wallet.dat file, so that your hot wallet wouldn't reveal that it's connected to the full cold wallet.

There is no type-2 derivation needed at all here, is there? Or you mean to divide your hot storage into hot stored privkeys and even hotter watch only wallets?

There is. The default should always be type-2, since this way the user can have the client generate new receiving addresses (hashed pubkeys) for him, without decrypting his wallet in order to access his privkeys, and that's a safer behavior because users should access their privkeys only when it is absolutely needed. An important special case of receiving addresses is the addresses where the coin change goes to (see the internal keychain of BIP32).
Also, in the scenario of post #122 there's person C who is only allowed to generate pubkeys via type-2 in the subtree, for purposes like the ones described by ErebusBat in post #101

Do you agree that type-1 after type-2 is meaningless?

No, I don't. The idea of the "subaccounts" wallet layout is that it would be nice for users to have separate subtrees of unrelated operations. For example, one subaccount for personal finances and one subaccount for business expenditures/revenues. Now suppose that your "personal finances" subaccount becomes highly valuable because you received some large BTC payments there, and therefore you would like to separate this subaccount further, into hot storage and cold storage parts. You can do that via type-1 after type-2, so IMHO it's not meaningless. Of course, you could just start a whole new subaccount at depth 1 for that hot storage subtree that you wanted, but you would miss out on the potential "hierarchical" possibilities which some people could find useful in the way that they like to organize things. Moreover, for doing type-1 derivation at a node somewhere deep in the tree structure you only need to access the privkey of that particular node, rather than the privkey of the master node at depth 0, so this might be more secure (though not necessarily).
Another reason for type-1 after type-2 is the example with persons A,B,C in post #122
And maybe another reason is decoy subwallet for deniable encryption that starts at a node that's deeper than depth 1

That we don't confine? You wrote in #122:

As discussed, it's important to do the secret type-1 derivation from the master node (depth 0) to the subaccounts (depth 1), since if the master node leaks then the entire wallet leaks. So the derivation from depth 0 to depth 1 should be type-1 by default, and maybe if you wish to be extra safe (about preventing people from shooting themselves in the foot) then you should specify that type-2 derivation from depth 0 to depth 1 isn't allowed according to the BIP32 standard, and enforce that in the Satoshi client.

Yes, the confined version refers to posts #105 and #106, and the fully unconfined version is what BIP32 allows now. It's true that in post #122 I suggested to confine the current BIP32 a little bit by only allowing type-1 derivations from depth 0 to depth 1, so that (alternative) clients who state that they support BIP32 will have to disallow their users to shoot themselves in the foot. I think that we all agree that the Satoshi client should have type-1 from depth 0 to depth 1 by default, but perhaps we don't agree on whether type-2 from depth 0 to depth 1 should be strictly forbidden or not.
member
Activity: 104
Merit: 10
April 30, 2013, 08:49:23 AM
There can be reasonable scenarios where A and B know each other well, so A would trust B with a subtree that they'd both share. Also, another use case can be when A and B are the same person, i.e. we have only one person A who wishes to consider his full HD wallet as cold storage (savings account), but wishes to have a subtree of that wallet as hot storage (checking account), so he can transact with the hot storage privkeys as they'd be on his online machine. For example, MtGox claims to have 90%-95% of their bitcoins in cold storage. So for this use case, you will derive a child node via type-1 and treat that child as hot storage, meaning that leakage of any privkeys in your "hot storage wallet" won't affect your "cold storage wallet". Additionally, it'd be a nice feature if the client allows you to export a subtree as a new wallet.dat file, so that your hot wallet wouldn't reveal that it's connected to the full cold wallet.

There is no type-2 derivation needed at all here, is there? Or you mean to divide your hot storage into hot stored privkeys and even hotter watch only wallets?

Do you agree that type-1 after type-2 is meaningless? I understand type-2 after type-1 will occur because type-1 usually happens from depth 0 to depth 1.

And I tried to explain in post #122 why it can be useful that we don't confine ourselves to a wallet layout that allows type-1 derivations only from the (depth 0) master node to the (depth 1) subaccounts.


That we don't confine? You wrote in #122:

As discussed, it's important to do the secret type-1 derivation from the master node (depth 0) to the subaccounts (depth 1), since if the master node leaks then the entire wallet leaks. So the derivation from depth 0 to depth 1 should be type-1 by default, and maybe if you wish to be extra safe (about preventing people from shooting themselves in the foot) then you should specify that type-2 derivation from depth 0 to depth 1 isn't allowed according to the BIP32 standard, and enforce that in the Satoshi client. BTW, with the updated BIP32, I guess that there's no need to save the initial entropy S in wallet.dat ?

1.) Do secret derivation from any privkey without a separate chaincode, i.e. with implicit chaincode like in ki=HMAC(H(kpar),i).

As mentioned, I don't like this idea because it violates property (2) of post #181, which would mean that if one particular privkey leaks then its entire subtree immediately leaks as well. This would make one aspect of HD wallets significantly less secure than the currently used random-independent wallets.

Ok, got that.
sr. member
Activity: 360
Merit: 251
April 30, 2013, 06:03:20 AM
I am not convinced that we need a public derivation after a secret one. You are citing #122 for a use case:


it could give flexibility with scenarios that ErebusBat mentioned, something like person A giving person B that he trusts the ability to derive a branch (with privkeys) in his wallet, and then person B wishes to give an untrusted person C the ability to derive pubkeys in a sub-branch, so to enhance security he can break the homomophism link by doing type-1 derivation (person B couldn't have done the type-1 derivation if it was only possible at depth=1 of the "subaccounts", because he's not trustworthy enough to have access to that depth, and besides keeping the layout of extending the particular branch instead of starting a new subaccount could be useful for accounting and so on). Probably there would be more interesting use cases than this one, that I haven't thought of.

"Giving B the ability to derive a branch [by himself, on the fly] with privkeys" with type-2 is equivalent to handing A's privkey to B. Trusting someone should never go as far as handing over one's own privkey.

There can be reasonable scenarios where A and B know each other well, so A would trust B with a subtree that they'd both share. Also, another use case can be when A and B are the same person, i.e. we have only one person A who wishes to consider his full HD wallet as cold storage (savings account), but wishes to have a subtree of that wallet as hot storage (checking account), so he can transact with the hot storage privkeys as they'd be on his online machine. For example, MtGox claims to have 90%-95% of their bitcoins in cold storage. So for this use case, you will derive a child node via type-1 and treat that child as hot storage, meaning that leakage of any privkeys in your "hot storage wallet" won't affect your "cold storage wallet". Additionally, it'd be a nice feature if the client allows you to export a subtree as a new wallet.dat file, so that your hot wallet wouldn't reveal that it's connected to the full cold wallet.

That's not necessary either. Your case should be handled with type-1, giving B one derived privkey from which he can further derive whatever he wants.

Huh? Isn't that exactly the scenario that's discussed in post #122 ? And I tried to explain in post #122 why it can be useful that we don't confine ourselves to a wallet layout that allows type-1 derivations only from the (depth 0) master node to the (depth 1) subaccounts.

BTW, another reason not to confine the wallet layout is plausible deniability, meaning that when you reveal your decoy subwallet that you created via deniable encryption, it can have the same structure as the full wallet, i.e. the decoy wallet will have type-1 subaccounts of its own.

1.) Do secret derivation from any privkey without a separate chaincode, i.e. with implicit chaincode like in ki=HMAC(H(kpar),i).

As mentioned, I don't like this idea because it violates property (2) of post #181, which would mean that if one particular privkey leaks then its entire subtree immediately leaks as well. This would make one aspect of HD wallets significantly less secure than the currently used random-independent wallets.
member
Activity: 104
Merit: 10
April 30, 2013, 04:50:12 AM
Another general question: do we have any use cases for mixed trees? Should we even allow them?

The reason is security, when only type-2 is used we get that leakage of any one privkey somewhere in the wallet tree structure implies that all the other privkeys of the wallet also leak, see posts #105, #106, #122

I am not convinced that we need a public derivation after a secret one. You are citing #122 for a use case:


it could give flexibility with scenarios that ErebusBat mentioned, something like person A giving person B that he trusts the ability to derive a branch (with privkeys) in his wallet, and then person B wishes to give an untrusted person C the ability to derive pubkeys in a sub-branch, so to enhance security he can break the homomophism link by doing type-1 derivation (person B couldn't have done the type-1 derivation if it was only possible at depth=1 of the "subaccounts", because he's not trustworthy enough to have access to that depth, and besides keeping the layout of extending the particular branch instead of starting a new subaccount could be useful for accounting and so on). Probably there would be more interesting use cases than this one, that I haven't thought of.

"Giving B the ability to derive a branch [by himself, on the fly] with privkeys" with type-2 is equivalent to handing A's privkey to B. Trusting someone should never go as far as handing over one's own privkey. That's not necessary either. Your case should be handled with type-1, giving B one derived privkey from which he can further derive whatever he wants. Seems to me an all-type-1 scenario, not a mixed one.

After all, I'm not convinced that the two derivation types should be mixed in one tree. It complicates the matter of backup and encryption of chaincodes vs export of privkeys that you brought up in recent posts. Why not separate them:

1.) Do secret derivation from any privkey without a separate chaincode, i.e. with implicit chaincode like in ki=HMAC(H(kpar),i). Then the hierarchy is trivially possible without extended keys, without keeping track of chaincodes, etc. Secret derivation doesn't need to be part of BIP 32, whose focus is _hierarchical_ derivation, because the hierarchical property is trivial here.

2.) Do public derivation as before.

If you still want to mix them, and probably type-2 after type-1 is the only order that you need, then you can still turn a privkey into an extended one by self-seeding it: kpar -> (kpar,cpar=H(kpar)) and starting your type-2 derivation from there.

Any use case that is not covered?

About encryption of chaincodes (in type-2):
Since chaincodes are generally stored unencrypted, can the wallet tag each key that was type-2-derived and forbid export of its privkey?

member
Activity: 104
Merit: 10
April 30, 2013, 02:42:57 AM
A property that (seemingly) hasn't been discussed is the provability of the link. You want to be able to prove that a given child belongs to a give parent, without de-anonymizing the other children (the siblings), i.e. without revealing the chaincode. In current BIP 32 this can be done by revealing I_L. As you note, I_L is already a "second hash".

Right, BIP32 allows us to have this property.
So you're saying that if we wish to get this property with your scheme, we will have to use the extra hash i.e. K_i=hash2(c_i)*K_par, to prove that a child belongs to a parent by revealing hash2(c_i) ?
I'm not sure what the use case would be, and maybe the usefulness is only in terms of efficiency (instead of signing messages with k_par and k_i to prove that you own K_par and K_i) ?

Yes, if we did c_i=HMAC(cpar,i) then it would be advisable to do K_i=H(c_i)*Kpar instead of K_i=c_i*Kpar. "Proving the link" between K_par and K_i is a different thing (and might have a different purpose) than proving ownership of either of the privkeys. It proves that Kpar and K_i have the same owner, not that we are the owner. It's a feature (don't know a use case yet) that you don't need the privkeys for that. As you said, the required information is H(c_i) resp. I_L.
sr. member
Activity: 360
Merit: 251
April 29, 2013, 04:28:22 AM
There may be a different reason why you would want to use a "double-hash". The property of anonymity of children has been discussed: we want that a child cannot be linked to it's parent. In the strongest form: given two parents and a child of each of them, an attacker cannot determine the correspondence any better than guessing.

I didn't understand. If we agree that f_K(x)=x*K is a one-way function (where K is an elliptic curve point), then why would the extra hash be helpful in this regard?

BIP 32 is doing this just fine, no extra hash required because x is already a hash of the chaincode:
HMAC(cpar,i). This was just a thought experiment. If x was cpar+i for instance then we couldn't prove the link by revealing cpar+i without revealing cpar and de-anonymizing all siblings. If x was cpar+i you could still come up with a zero-knowledge proof that you know x. If anyone knows x with K'=x*K then we can be convinced that K' was derived from K. Again, just thought experiments.

Yes obviously c_par+i is terrible, not only because revealing/leakage of c_i implies leakage of its parent c_par, but also simply because the privkeys wouldn't be pseudorandom, so we could attack such a scheme by knowing just the public signatures (transactions).

But HMAC(cpar,i) isn't BIP32, it's your scheme where the keys and chaincodes are unlinked. With BIP32, even if you discover from K_par,K_i the x that solves K_i=x*K_par you still haven't obtained the chaincode, only I_L. With your scheme, if you discover x then you do obtain the chaincode, but since discovering x is ECDLP, we're still safe.

A property that (seemingly) hasn't been discussed is the provability of the link. You want to be able to prove that a given child belongs to a give parent, without de-anonymizing the other children (the siblings), i.e. without revealing the chaincode. In current BIP 32 this can be done by revealing I_L. As you note, I_L is already a "second hash".

Right, BIP32 allows us to have this property.
So you're saying that if we wish to get this property with your scheme, we will have to use the extra hash i.e. K_i=hash2(c_i)*K_par, to prove that a child belongs to a parent by revealing hash2(c_i) ?
I'm not sure what the use case would be, and maybe the usefulness is only in terms of efficiency (instead of signing messages with k_par and k_i to prove that you own K_par and K_i) ?
member
Activity: 104
Merit: 10
April 29, 2013, 02:07:53 AM
There may be a different reason why you would want to use a "double-hash". The property of anonymity of children has been discussed: we want that a child cannot be linked to it's parent. In the strongest form: given two parents and a child of each of them, an attacker cannot determine the correspondence any better than guessing.

I didn't understand. If we agree that f_K(x)=x*K is a one-way function (where K is an elliptic curve point), then why would the extra hash be helpful in this regard?

BIP 32 is doing this just fine, no extra hash required because x is already a hash of the chaincode:
HMAC(cpar,i). This was just a thought experiment. If x was cpar+i for instance then we couldn't prove the link by revealing cpar+i without revealing cpar and de-anonymizing all siblings. If x was cpar+i you could still come up with a zero-knowledge proof that you know x. If anyone knows x with K'=x*K then we can be convinced that K' was derived from K. Again, just thought experiments.

sr. member
Activity: 360
Merit: 251
April 28, 2013, 03:12:49 PM
There may be a different reason why you would want to use a "double-hash". The property of anonymity of children has been discussed: we want that a child cannot be linked to it's parent. In the strongest form: given two parents and a child of each of them, an attacker cannot determine the correspondence any better than guessing.

I didn't understand. If we agree that f_K(x)=x*K is a one-way function (where K is an elliptic curve point), then why would the extra hash be helpful in this regard?
sr. member
Activity: 360
Merit: 251
April 28, 2013, 01:55:51 PM
IMHO having type-1 subaccounts in BIP32 is a great feature that enhances the security of average users, but I'm still a little worried about users who will store the wallet file on the cloud (e.g. dropbox) with all the chaincodes exposed.

What's your assumption here? That a user stores his full wallet in the cloud, including privkeys, in encrypted form? Is the worry just about deniability?

As Pieter said in post #103, the encrypted wallet.dat should only encrypt the privkeys. We currently advise users to add another layer of symmetric encryption (e.g. with GPG or 7zip) before storing the wallet on the cloud, because of privacy concerns (otherwise your total wallet balance and addresses will be exposed). Still for example after the wallet non-encryption bug was discovered (CVE-2011-4447), IIRC there were claims of stolen coins from wallet.dat files that were stored on dropbox (possibly by dropbox administrators), etc., meaning that users do store wallet.dat files in public places, without the advised extra layer of encryption.

My suggestion is to have deniable encryption in order to incentivize users to be prudent, by offering them a desirable feature which would be built into the client.
sr. member
Activity: 360
Merit: 251
April 28, 2013, 01:40:00 PM
No, solving K_i=x*K_par for x is the discrete log problem.

Oops, you're right, apologies.
And it will still be DLP even if you use the additive variant: K_i=K_par+G*c_i
member
Activity: 104
Merit: 10
April 28, 2013, 12:46:15 PM
IMHO having type-1 subaccounts in BIP32 is a great feature that enhances the security of average users, but I'm still a little worried about users who will store the wallet file on the cloud (e.g. dropbox) with all the chaincodes exposed.

What's your assumption here? That a user stores his full wallet in the cloud, including privkeys, in encrypted form? Is the worry just about deniability?
member
Activity: 104
Merit: 10
April 28, 2013, 12:40:07 PM
thanke: regarding your scheme and use case where the chaincodes and keys are unlinked, we should have noticed that if c_i=hash(c_par,i) and K_i=c_i*K_par then anyone could take the pubkeys K_par,K_i and solve x*K_par=K_i to discover the supposedly secret chaincode x=c_i, meaning that all the chaincodes would leak trivially.

No, solving K_i=x*K_par for x is the discrete log problem.

Though it's not an irreconcilable issue, simply take any OWF hash2 and derive the child key via K_i=hash2(c_i)*K_par, just note that the added complexity of hash2 cannot be avoided.
Obviously BIP32 was also designed to prevent this issue, and when discussing the additive variant with Pieter we considered the closely related issue of whether the leakage of I_L*G could be exploited (the answer appears to be "no" even if I_L itself leaks).

There may be a different reason why you would want to use a "double-hash". The property of anonymity of children has been discussed: we want that a child cannot be linked to it's parent. In the strongest form: given two parents and a child of each of them, an attacker cannot determine the correspondence any better than guessing.

A property that (seemingly) hasn't been discussed is the provability of the link. You want to be able to prove that a given child belongs to a give parent, without de-anonymizing the other children (the siblings), i.e. without revealing the chaincode. In current BIP 32 this can be done by revealing I_L. As you note, I_L is already a "second hash".
sr. member
Activity: 360
Merit: 251
April 28, 2013, 06:34:29 AM

This is even nicer than I first realized, because the GUI can let the user choose a minimal desired strength, and it'd work by dismissing all seed attempts that fall below the desired strength. So for example if the user chooses minimal strength of 15 leading 0 bits, then it will defeat attackers who only try to brute-force seeds that have up to 14 leading 0 bits.

Maybe the client should benchmark the CPU (GPU?) speed to derive the maximal cutoff strength and minimal recommended strength, and allow the user to override the minimal/maximal strengths if he wishes to obtain greater security.

I guess that the dictionary shouldn't be hardcoded, so users could plug in different dictionaries instead of the default dictionary, which would give security through obscurity (e.g. dictionaries in different languages).

BTW these self-descriptive strengthened keys should probably also be used with the AES wallet encryption that we have now, not just for HD brainwallets. Though maybe the client should have an hidden option to disable it (i.e. both when encrypting and when decrypting the wallet), to be backward compatible with previously encrypted wallets, and for (advanced? dumb?) users who don't want to memorize the dictionary postfix.
sr. member
Activity: 360
Merit: 251
April 27, 2013, 07:10:19 AM
IMHO having type-1 subaccounts in BIP32 is a great feature that enhances the security of average users, but I'm still a little worried about users who will store the wallet file on the cloud (e.g. dropbox) with all the chaincodes exposed. One possible remedy (external to BIP32) is to encourage users to do the right thing by offering a GUI menu option that backups the entire wallet with deniable encryption, and recommend to the user to put only this kind of backup in public places. This can be implemented by creating a designated subaccount at depth 1 for this purpose, e.g. with index 0, and encrypting the secondary wallet with decoy passphrase by having this subaccount as its root node. Another way to select the fake root is by traversing the wallet tree structure via random walk until we reach a subtree that holds less coins than some threshold, but then we might need to somehow tag this subtree's root node in the real wallet, otherwise many more coins could be transferred to this subtree in the future.
sr. member
Activity: 360
Merit: 251
April 26, 2013, 09:21:06 PM
thanke: regarding your scheme and use case where the chaincodes and keys are unlinked, we should have noticed that if c_i=hash(c_par,i) and K_i=c_i*K_par then anyone could take the pubkeys K_par,K_i and solve x*K_par=K_i to discover the supposedly secret chaincode x=c_i, meaning that all the chaincodes would leak trivially. Though it's not an irreconcilable issue, simply take any OWF hash2 and derive the child key via K_i=hash2(c_i)*K_par, just note that the added complexity of hash2 cannot be avoided.
Obviously BIP32 was also designed to prevent this issue, and when discussing the additive variant with Pieter we considered the closely related issue of whether the leakage of I_L*G could be exploited (the answer appears to be "no" even if I_L itself leaks).
sr. member
Activity: 360
Merit: 251
April 26, 2013, 04:51:06 AM
(one of the chaincodes can replace the privkey as in #180, so it would still be a pair, not a triple)

But if it's a pair then property (2) of post #181 fails.
sr. member
Activity: 360
Merit: 251
April 26, 2013, 04:43:08 AM
Another general question: do we have any use cases for mixed trees? Should we even allow them?

The reason is security, when only type-2 is used we get that leakage of any one privkey somewhere in the wallet tree structure implies that all the other privkeys of the wallet also leak, see posts #105, #106, #122
Pages:
Jump to: