Quote from: Pieter Wuille on May 03, 2013, 05:10:13 PM

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

A few remarks before finalization, taking into account and drawing from the long discussion with iddo:

1. Can we reserve more than one bit of the number i for different kind of derivations, not only the highest bit? This would allow addition other kinds of derivations or tweaks of existing ones in the future.

2. Additive vs multiplicative: I don't know what your status is regarding constant-time implementations. But unless timing attacks discredit the multiplicative variant, I would stay with it because of the issue raised in #155. Note that #155 is a non-issue as long as you can guarantee that no I_L is ever reused. If you can't guarantee that, in particular if you wanted to allow the re-use of chaincodes, then multiplicative would be mandatory.

3. I am having an issue with the type-1 derivation. In current BIP 32 both types of derivation first produce an I_L in their own way and then set k_i := I_L * k_par (or + instead of *). For type-1 I_L depends on k_par. Isn't it cleaner for type-1 if k_i is the direct output of a HMAC? Why the additional multiplication with k_par? This is unnecessarily complicated compared to setting (k_i,c_i) := HMAC(kpar,cpar,i). iddo phrased the desired property for type-1: "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". It is counter-intuitive to this property that a number I_L with k_i = I_L * k_par is even computed. Besides k_i and k_par, I_L is one more (unnecessary) thing that an implementation has to prevent from being swapped out to disk.

4. A further suggestion for type-1 on top of 3.: (k_i,c_i) := HMAC(S,i) where S := HMAC(kpar,cpar). This achieves that k_i=func(kpar,cpar,i) as before. Plus it has the following properties:
- storing S there is no need to decrypt kpar when deriving children (the new advantage of this)
- children cannot be derived from kpar alone (iddo insisted on this property)
- children cannot be derived from cpar alone (we assume cpar is stored unencrypted)
Storing S is of course optional. The common (default) use would be just to recompute it each time.

5. It is certainly possible to do everything with HMAC-SHA256 alone. For instance, if you need two values like (I_L,I_R) you can do I_L=HMAC(secret,0) and I_L=HMAC(secret,1). The question is, does it reduce dependencies of the code, code review, etc. to be worthwhile? Or does it matter here that SHA256 has by now become the best-tested hash function in the world?

6. BIP 32 should, for each derivation type, explicitly list all properties that it claims to achieve. So that wallet implementers can rely on these properties instead of digging into the details of the definitions.

7. I understand that it is not the concern of BIP 32 to specify how clients handle extended pubkeys. However, since this is important for security there should be some guidelines, possibly in a separate document. For example, I am thinking of an "export bit" for extended keys. A type-2 derived extended key would get this bit set for lifetime, and it would prohibit the export of its privkey.

Quote from: iddo on May 03, 2013, 06:05:27 PM

Quote from: Pieter Wuille on May 03, 2013, 05:10:13 PM

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

Let me elaborate on this use case. Think of many B's, for example A is a telcom corp and the B's are millions of dealers in every village on the planet. Each B knows its I_L which is considered as B's random name, issued by A, used to identify B. Now if A publishing a (signed) new root pubkey, this is a single, identical piece of information required by all B's. No individual piece of information is required to be exchanged with each B. The scenario is mainly intended for when the new root pubkey is completely unrelated to the old root pubkey, for example if a new owner takes over A. Think of A's root pubkey being published in a certificate of some PKI. Then each B can download it from keyservers. Regardless of encryption, this is a significantly different kind of communication than of each node in the tree getting updated from its parent.

After all, I am still in favor of type-2 in the form of (I_L,I_R) := HMAC(c_par,i), k_i := I_L*k_par, c_i := I_R. The two reasons are: 1) it allows something new without breaking anything old, 2) it simplifies the definition.

Quote from: iddo on May 03, 2013, 06:05:27 PM

Quote from: Pieter Wuille on May 03, 2013, 05:10:13 PM

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.

I think iddo is right. Secret derivation after public derivation allows a wallet implementation to be absolutely strict about the export bit. Because if the user desires to export the privkey of a type-2 derived extended key, then the wallet would just do a secret derivation and export the privkey of the result of that.