Very nice, I like your BIP32 modifications with type-1/type-2 derivation according to the highest bit of the index. 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.

I suppose that with this updated BIP32, some of the complexity will be transferred to the people who should do GUI design for wallet layouts

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 ?

Huh? Why would regular backups be needed? The major advantage of deterministic wallets is that backups aren't needed (see here).

Can someone precisely specify the additive variant of the CKD function?  I'm fairly certain I know, but I don't want to end up missing a detail and evaluating something else.

We actually just had a discussion about this, and I'm in favor of changing this. The proposal would be:

• k_i = k_par + I_L
• K_i = K_par + I_L*G

I've been holding back on changing this, as speed wasn't a priority really. However, it is a lot easier to do the required operations for public derivation in constant time, than for the multiplicative case, which means it's easier to secure against timing attacks (and we are, very intensively, dealing with private material here). Also, it means you only need almost the same primitives as needed for ECDSA in the first place.

It is not less secure, as you still need to solve the ECDLP to find I_L from I_L*G (=the public key, which is exposed). Assuming a weaker version of the scheme, where it's just K_i = K_par + (i*c_par)*G, and assuming there is a transaction with inputs corresponding to i values i1 and i1+1, and a transaction with values i2 and i2+1, an attacker could detect these were created by someone using the same chain code twice. This would not be possible in the multiplicative version, and also not in the real scheme where the 'tweak' I_L is computed using an HMAC.

Anyone objects to changing this?

Nothing, timing coincidence.


OpenSSL's ECDSA_sign probably guarantees this (I haven't verified), but as generic EC multiplication isn't required by ECDSA_sign (only by ECDSA_verify), it's not guaranteed to have a constant-time version (and a variant-time one is certainly faster).

As Pieter mentioned in the link that I gave you, it should be very practical to scan in mostly all cases of wallet layouts, the branching factor and depth are quite tiny.

Can you specify what information your are assuming your attacker has? Does he know c_par and is just scanning all pubkeys he gets to see for a difference of c_par*G? Or how does his "detection" work?
[/quote]

Sure. I assume the attacker can only observe the blockchain. For any transaction with multiple inputs, he subtracts the pubkeys used in any pair of inputs. If he finds two transactions that result in the same difference, they are very likely keys that are generated from the same extended parent (the difference would be (i-i')*c_par*G. Note that he can't find c_par or i or i' itself, just a likelyhood that c_par is the same. Also note that this doesn't work in the real scheme as not i*c_par but HMAC-SHA512(key=c_par, msg=K_par || i) is used, which guarantees no tweak will be reused.

This was just a thought experiment to see how much we'd have to weaken the construction before the add-vs-multiply makes any difference.

Why does constant time public derivation give security against timing attacks? Isn't it the case that public derivation doesn't use the privkeys, and therefore cannot leak privkeys? Maybe you meant security against leakage of just the chaincodes? I probably simply misunderstood what you're saying there, so it'd be helpful if you explain where exactly we need protection from timing attacks.

Yes, obviously with a variant that uses K_i=K_par+(i*c_par)*G you could detect c_par*G from the sub-branch with i1,i1+2 compared to the sub-branch with i2,i2+1, and maybe you could do much worse stuff as well. The OP also uses the safe version with hash(seed|i) to derive the next values. You can see that the formal proof in post #62 fails for K_i=K_par+(i*c_par)*G because we wouldn't claim that the r_i that's used for (sk_i,pk_i)=keygen(r_i) is pseudorandom. As you mentioned in post #103, if the attacker learns I_L then it doesn't seem like such a big deal, and as mentioned here the attacker needs to solve ECDLP to learn even just I_L, so the additive variant appears to be provably secure, as far as I can see. But of course it wouldn't hurt to show the finalized BIP32 to some elliptic curves crypto experts and ask for more peer review, before including it in the Satoshi client.

The assumption there is that if a key with a sequence number is not on the block chain, then higher sequences were not used, right?

I think that would not hold. A shop usually offers unique addresses to receive payment for individual orders. Some orders never get paid, therefore their key will not be present in the block chain, however keys with higher sequence number might be. A reconstruction of the wallet would fail at such a gap.

I was wrong about this, as the problem of key exposure doesn't really exist for public key derivation, where these operations are required. It doesn't hold for chaincodes either, as these aren't tweaked.

This makes me wonder whether it's still worth changing, though the implementation complexity argument still holds.