Is it feasible to derive the root key of an HD wallet from a large sample of child public keys?

Question

I'm considering the following architecture for a bitcoin-related service:

• A BIP 32 HD wallet is created that controls all of the account keys for the web service. The private key is kept in cold storage, and the public key is stored on the server and used to assign bitcoin addresses deterministically to new accounts by deriving child public keys from the root public key.

• Users can send money to the bitcoin address corresponding to their account in order to pay to use this service.

• Money deposited by users is signed to my business account using an offline process that has access to the cold storage containing the private key

It wouldn't be difficult for an attacker to gather a large sample of child public keys (either by looking at the blockchain after I consolidate all of the micro-deposits) or by signing up for a bunch of accounts.

My question is this: Would having a large pool of these child keys make it easier to derive the private root key (since they are computed deterministically), or would there be no statistical advantage over attempting to brute force one of the child private keys (which can then be used to derive the root key)?

Thanks in advance. My understanding is that this is still secure, but I wanted to check with some of the experts here.

Answer 1

According to Mastering Bitcoin chapter 4 Hardened child key derivation, the master key is protected.

As a best practice, the level-1 children of the master keys are always derived through the hardened derivation, to prevent compromise of the master keys.

So special care is made by wallets to protect that key specifically. Knowing the child indices, entropy, and child keys don't expose the master key as long as you keep the master key itself secure.

The chapter goes on to explain the normal child derivation's associated risks, but those are xprv keys.

Edit:

HMAC-SHA512

index   -->|HMAC-  |
master  -->|SHA512 |-->lt 256 bits --> + index + master --> child key
chain   -->|       |-->rt 256 bits -----------------------> chain

This is how I reimagined the diagram from chapter 4:

The parent public key, chain code, and the index number are combined and hashed with the HMAC-SHA512 algorithm to produce a 512-bit hash. The resulting hash is split into two halves. The right-half 256 bits of the hash output become the chain code for the child. The left-half 256 bits of the hash and the index number are added to the parent private key to produce the child private key.

This didn't show the resulting addresses, but the text describes their behavior as identical to random addresses.

Source Code

https://github.com/btcsuite/btcutil/blob/master/hdkeychain/extendedkey.go

170 starts comments describing how the IsPrivate flag is assigned. For a hardended child, it must derive from extended private key.

https://github.com/btcsuite/btcwallet/waddrmgr/wallet.go

2029 shows the BIP0044 HD structure being defined by using the 44 + hdkeychain.HardendKeyStart (upper 2^31 range) value

m/44'/<coin type>'/<account>'/<branch>/<address index>

https://github.com/btcsuite/btcwallet/blob/master/waddrmgr/address.go

316 newManagedAddressFromExtKey we know IsPrivate is true and calls newManagedAddress on 286 which generates the pub address using the same logic from public key at 301:

ripemd160( sha256( publickey ) )

where the publickey is elliptic-curve paired to prv

I believe the EC property is still what makes the resulting addresses irreversible. Looking at the identifier notation, you can make guesses about common values:

m/44'/0'/1'/1/1

Assuming this is a very common HD wallet identifier, the other inputs are the root seed and the pass phrase.

Collecting Significant Pool of Addresses

With the EC property, no amount of addresses collected can be reversed-hashed, then reversed-EC'd to obtain the private keys.

So then the work could be to iterate through all possible inputs (seed, pass-phrase) with the common BIP0044 HD identifiers, and compare results to the collected addresses. Not trivial task.

Another layer of protection I can see, is to fan out at the child of the index:

m/44'/0'/1'/1/1/<here>

Import that public key to the online wallet. At each branch, you are increasing the possible addresses by 2B. If the online wallet in turn generates a child per user, that person only ever "collects" addresses for his/her branch; 2B addresses and still they will not see addresses for a sibling user. Reversing here only reveals the public key, another deterrent.