BIP32 adventures

bip32-adventures.md

Combining BIP32 keys for fun and profit

We only consider non-hardened children here.

Private parent key → private child key

CKDpriv((kpar, cpar), i) → (ki, ci) computes a child extended private key from the parent extended private key:

• I = HMAC-SHA512(cpar, serP(point(kpar)) || ser32(i))
• IL = I[0:32]
• IR = I[33:64]
• ki = parse256(IL) + kpar (mod n)
• ci = IR

Public parent key → public child key

CKDpub((Kpar, cpar), i) → (Ki, ci) computes a child extended public key from the parent extended public key:

• I = HMAC-SHA512(cpar, serP(Kpar) || ser32(i))
• IL = I[0:32]
• IR = I[33:64]
• Ki = point(parse256(IL)) + Kpar
• ci = IR

Retrieving parent private key

If we have access to (Kpar, cpar), i, ki and ci we can compute kpar:

• we can recompute I = HMAC-SHA512(cpar, serP(Kpar) || ser32(i))
• ki = parse256(IL) + kpar (mod n)
• kpar = ki - parse256(IL)

Combining multiple xpubs

Alice has (kpar1, cpar1) and (kpar2, cpar2). She gives (Kpar1, cpar1) and (Kpar2, cpar2) to Bob. Bob can derive (Ki1, ci1) and (Ki2, ci2). Alice then reveals ki1 + ki2.

Bob is now able to compute:

• I1 = HMAC-SHA512(cpar1, serP(Kpar1) || ser32(i))
• I2 = HMAC-SHA512(cpar2, serP(Kpar2) || ser32(i))
• ki1 + ki2 = parse(I1[0:32]) + parse(I2[0:32]) + kpar1 + kpar2 (mod n)
• Bob can thus obtain kpar1 + kpar2
• Bob cannot extract kpar1 or kpar2 from the sum
• But Bob can compute kj1 + kj2 = parse256(HMAC-SHA512(cpar1, serP(Kpar1) || ser32(j)))[0:32] + parse256(HMAC-SHA512(cpar2, serP(Kpar2) || ser32(j)))[0:32] + kpar1 + kpar2 (mod n)

So Bob is able to derive the private keys for all future derivations. Game over.

Combining multiple xpubs less naively

Alice has (kpar1, cpar1) and (kpar2, cpar2). She gives (Kpar1, cpar1) and (Kpar2, cpar2) to Bob. Bob can derive (Ki1, ci1), (Ki2, ci2) and Pi = Ki1 + SHA256("bip32-tweak" || ser32(i)) * Ki2. Alice will then reveal pi = ki1 + SHA256("bip32-tweak" || ser32(i)) * ki2.

Bob is now able to compute:

• I1 = HMAC-SHA512(cpar1, serP(Kpar1) || ser32(i))
• I2 = HMAC-SHA512(cpar2, serP(Kpar2) || ser32(i))
• kpar1 + SHA256("bip32-tweak" || ser32(i)) * kpar2 = pi - parse(I1[0:32]) + parse(I2[0:32]) (mod n)
• Bob cannot extract kpar1 or kpar2 from the sum

If Bob receives another child private key pj = kj1 + SHA256("bip32-tweak" || ser32(j)) * kj2:

• Ii1 = HMAC-SHA512(cpar1, serP(Kpar1) || ser32(i))
• Ii2 = HMAC-SHA512(cpar2, serP(Kpar2) || ser32(i))
• Ij1 = HMAC-SHA512(cpar1, serP(Kpar1) || ser32(j))
• Ij2 = HMAC-SHA512(cpar2, serP(Kpar2) || ser32(j))
• kpar1 + SHA256("bip32-tweak" || ser32(i)) * kpar2 = pi - parse(Ii1[0:32]) + parse(Ii2[0:32]) (mod n)
• kpar1 + SHA256("bip32-tweak" || ser32(j)) * kpar2 = pj - parse(Ij1[0:32]) + parse(Ij2[0:32]) (mod n)

Bob has two equations with two unknowns, so he can retrieve kpar1 and kpar2. Game over.

Impossibility result

It's simply not possible to satisfy the following requirements:

• Bob can derive an arbitrary number of child public keys
• Bob can safely learn child private keys without learning the master private keys

The only way Bob can derive child public keys from N master public keys is by creating a linear combination over these master public keys. Whenever Bob learns a child private key, he learns the same linear combination over the master private keys. Once Bob has learnt N child private keys, he has N linear equations with N unknowns, so he's able to recover the master private keys.

I don't think it's possible to work around this limitation on standard elliptic curves like secp256k1.