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

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.

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.

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).

Nice video, thanks.

4JxxqiEiQFebV6SoPJdTkBNaLYVdPx2NaY
thanks

But if it's a pair then property (2) of post #181 fails.

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 don't see how the answer is "yes" if the property that we are trying to obtain with type-1 derivation is: assuming that all the chaincodes of the wallet are public, and the privkey k_i leaks, the attacker still cannot find the privkey k_par
This property holds for BIP32 type-1 derivation, but if you suggest here that c_i=hash(c_par,i) and k_i=f(c_i)*k_par then the attacker can solve k_i=f(c_i)*x and discover x=k_par (which he cannot do with BIP32, that's the whole point behind supporting type-1 derivation, see the discussion starting at post #104).
If the answer is "no", then I'm not sure whether your use case still applies.

I guess that (a) is similar to what I'm asking, it's not about post #112, it refers to the issues raised in post #168 in response to post #167.
I was trying to understand your latest proposal better by asking specific well-defined questions, the question was whether your scheme allows replacing just the master privkey and retain the entire wallet tree structure, so that all the old chaincodes remain intact, while supporting both type-1 and type-2 derivations? The answer to this question was "yes" with a scheme that supports only type-2 derivation.

I recommended that you write your full scheme in the wiki, because it's easier to make tweaks there than in forum posts.

thanke: the two properties that we were discussing are:

(1) deriving the chaincodes independently of the keys (in order to achieve the minor benefitial property in your use case), so for example you could replace the privkey in the master (root) node and still retain your old wallet layout with all your old chaincodes intact, just with new keys. Do you now agree with me that your proposal doesn't achieve this property when you also support type-1 derivation? Or do you still claim that with your scheme you can replace only the master key and retain the same exact tree structure with all the old chaincodes intact? You continue to tweak your proposal, which is good, but it makes it a little difficult for me to see what exactly your latest proposal achieves, especially in terms of practical use cases. If you agree with me regarding this property, then wouldn't you also agree that BIP32 is better simply because BIP32 uses all the available entropy and you use only some of the available entropy? Isn't it true that your type-1 derivation is essentially the same as the type-1 derivation in BIP32?

(2) whether leakage of one particular privkey (e.g. the attacker received one pubkey and managed to break it and discover the corresponding privkey) implies that the entire sub-tree rooted at this privkey also leaks, or the attacker must also obtain some private seed/chaincode to derive the sub-tree. With BIP32 you'd need the pubkey and chaincode to do type-2 derivations and compute all the pubkeys/chaincodes in the sub-tree, and you'd need the privkey and chaincode to derive the entire sub-tree. What is your claim regarding this property?

Maybe you should start a new page on the wiki and decribe your scheme with full details there?


Yes, the privkeys of intermediate nodes are also used. See for example the picture with default wallet layout in the BIP32 wiki page, where the subaccounts at depth 1 get extended as unbounded linear paths.

thanke, let's see if I understand correctly the outlining dependencies when we compare BIP32 with your latest proposal:

BIP32 type-2 derivation:

BIP32 type-1 derivation:

Your proposed type-2 derivation:

Your proposed type-1 derivation:

As we discussed in post #75 and #76, I don't like your type-1 derivation here because it doesn't depend on the additional secret chaincode (a.k.a. seed), which means that if one particular privkey leaks while the rightful owner of that privkey derived child keys via type-1, then the attacker will also know the entire sub-tree that's rooted at that particular privkey.
If you change your proposal so that type-1 derivation also depends on c_par, then the type-1 derivation will become similar to BIP32, and we will be left with considering why your type-2 derivation is supposed to be superior to BIP32 in that case.
That's probably not the only issue that should be examined, just the issue that I noticed first.

Nice. If I understand the proposal correctly, a particular seed that the user chooses all by himself would have a low probability to work in this scheme, so the computer will try to generate dictionary-style seeds for the user, and after less than 256 attempts on average a suitable seed will be found, and it'd have the nice checksum and variable-strength properties. BTW, if you're not convinced that scrypt is a good idea here, see casascius' 10 BTC 4 U 2 STEAL thread.

With regard to seeds for HD wallets (and elsewhere), obviously if the computer alone just generates the dictionary-style seeds then it will be a total disaster, because the attackers will also let the computer generate these seeds and thereby steal brainwallets. So the option in the Satoshi client should let the user input his my_very_long_and_secure_passphrase, and then concatenate the dictionary-style attempts to create the resulting checksum/varstrength seed. This means that the user will have to memorize the my_very_long_and_secure_passphrase+dictionary_style_postfix string if he wishes to restore his HD brainwallet from memory. This option will also take care of my previous suggestion to allow 'security through obscurity' by letting advanced users create the seed by running their secret hashing algorithm, for example scrypt(md5(md5(passphrase)), #9876 iterations) or whatever, because they could use their hashed output as the my_very_long_and_secure_passphrase input for this scheme.

I suppose that by default the Satoshi client should just create a new HD wallet (without asking the user anything) from truly random entropy, and then advise the user to encrypt and backup the wallet.dat file. I recommend that the option to create an HD brainwallet should be enabled only via an obscure command-line argument, to minimize the probability of users shooting themselves in the foot.

Another issue that's external to BIP32, but related to users shooting themselves in the foot, is how the initial entropy S can be created. Obviously, by default it's very important that S would be created from random bits, but we should consider whether to also allow users to input a string/passphrase and derive the master node from it. That implies that the user could restore his entire HD wallet via a passphrase, and advanced users could choose for example scrypt(passphrase, #iterations) as input for deriving the master node. Maybe this should be an advanced option that's hidden by default (maybe you'd even have to patch and recompile the client for it), otherwise attackers could attempt dictionary attacks and steal coins. However, if the Satoshi client won't allow this option at all then it's likely that sooner or later someone else will create a modified version of the client (similarly to the version without mandatory transaction fees) and call it "HD Brainwallet 2.0" or something, so I think that it's a good idea to consider what's the safest way to include this option in the Satoshi client. Maybe the best way is a hidden option that can be activated via a command-line argument, where the user may input a string of minimum #chars (for example 64 hex chars is the output size of sha256sum), which means that this way different users will choose different hashing algorithms (instead of using a single algorithm that the client would provide), so the attackers' task will be more difficult. Note that using the AES wallet encryption passphrase as the passphrase for deriving the master node should be highly discouraged, because attackers don't need to have access to the wallet.dat file in order to do dictionary attacks on HD wallet passphrases.

thanke, the only reason to unlink the chaincodes from the keys is to avoid the secure communication needed for sending another chaincode in the use case that you described, or do you have other use cases as well? If that's the only reason then it isn't much, as chaincode leakage without privkey leakage gives nothing to the attacker (e.g. you even said in post #76 that if chaincode is given to 3rd-party to generate new pubkeys then you don't regard the chaincode as sensitive data), and we opted to deal with possible leakage of privkeys by allowing type-1 derivation to break the homomorphism link. Anyhow, establishing secure communication to send a new chaincode in your use case isn't such a big deal, unless you demonstrate how to wrap this use case in some system that requires intensive use of re-transmiting encrypted chaincodes, or something else along these lines?

I see, though maybe he wishes to inject the new keypair as a parallel path that would co-exist in the wallet, instead of overwriting the old keypair, meaning that all the previous keys will still be retained. In other words, we can regard this injection as creating a fresh master privkey somewhere in the middle of the tree structure (which implies that we now must backup the wallet), and use the old chaincodes with this fresh master privkey too.

Well, one argument why we should depend on K_par is that with the updated BIP32 we allow either type-1
 or type-2 derivation from the current node.
With your proposal we will have a tree of hashchains c_i=hash(c_par,i) where you derive deterministically the keypair (k_i,K_i) from each c_i (BTW I'm not sure why you'd want to split I to I_L and I_R instead of having single 256-bits I that's used both for deriving the current keypair and the next chaincode), so indeed it gives the benefit over the OP because you can share some c_i in the middle of the hashchain with another person.
But if you unlink the chaincodes and from the keys, then you canot disallow type-2 derivation when the input to the CKD is just the pseudorandom hash value c_i, meaning that logically k_i=CKD(k_par,c_i), unless you could tag c_i somehow, or enforce the derivation type via CKD(k_par,c_par,i) as BIP32 does now, but then the property that the chaincodes and keys are unlinked becomes problematic.
In general, if the chaincodes and keys are unlinked then you could prepare an entire wallet layout starting from a master chaincode without any keys, and then for each master privkey that you plug in you would get different keys in the tree. I'm not so sure whether having the ability to do such things is a good idea.


I still don't see how exactly it could be that "A creates a new K'par" and follow the same old hashchain of chaincodes with the new K'par, since if we use (say) the multiplicative variant then there's a correspondence between the keys and chaincodes, so the chaincode that created Kpar doesn't create K'par, and if K'par is created with a different chaincode then the subsequent hashchain would also be different. I think that your proposal is simply missing the relevant details on how wallet structures can be created. If you fully specify what exactly is allowed to be created in wallet.dat, and then show how your practical use case applies, then it'd be easier for us to consider your ideas.

What do you mean by "A creates a new K'_par and sends it to B" ?
Do you mean that A uses c_parpar to compute HMAC-SHA512(c_parpar,i') to get I_L' and I_R' and derive K'_par from I_L' ? If so, B wouldn't have I_L' and I_R', so the encrypted I_R' has to be sent to B ? If I misunderstood then please try to explain it a bit more clearly?
Also, what you're describing isn't exactly a "use case", could you please elaborate on the practical objective that we'd achieve here?

Sure, but I was talking about the default wallet layout, with consecutive indices (1,2,3,...) for each subaccount.
And I believe that other layouts that users might choose to use would be just as easy to scan.

Where does the 2^32 figure come from? I thought that we're talking about a user who has a backup of the master node, and he just needs to scan his subaccount (depth 1) branches to a reasonable depth (say 10000 or 100000 or 1000000 payment addresses in each subaccount, assuming that the user didn't have more than 1 million customers). Why would such a task take 2^32 time?