Protecting Hierarchical Deterministic Structures With Multiple Scrambled Levels

[CoinBeyond]

Hey guys,

I'm working with HDM structures and have been growing concerned about how to secure a master key.

HD is great, but if the master key is ever nabbed, you could lose everything.  The concept of how to secure the master key, or any non-hardened extended key, has been on my mind a lot lately.  Today I came up with something, and I'd like your feedback.

Something-like-an-abstract: The concept to protect your master key or extended keys by purposefully make your hierarchy complex and obscure with multiple layers and scrambled child indices.  So even if an attacker does form the master key, they have a more difficult time figuring out how to use it properly than randomly guessing a private key to an address.

Let me describe the scrambled child indices first:
In (I assume) normal hierarchical deterministic wallets that use a different address for each transaction, every transaction has change sent to a new address created using the next child index.  So they will start with an address derived from child index 0, do a transaction, and change will be sent to an address derived from child index 1.  If the child indices were scrambled, then they might start with an address derived from child index 617492810, do a transaction, and change will be sent to an address derived from child index 741109822.  At a simple level, this can be implemented with a simple table lookup:

TxIndex	ChildIndex
0	617492810
1	741109822
2	1840569824
3	1056489135

...

I imagine that you'd have one of these at every depth-level of your hierarchy and keep each of these secure.

Right away I thought that might be handy, but if someone were to get the private master/extended key to a tree of addresses, it would only slow them down slightly.  It wouldn't take long to fish for bitcoin for 2^31 keys.

But where I think this comes in handy is when there are multiple layers of the hierarchy. 

Say you have a master key where every child is a key for an address that you use to transact.  OK, not great.  Your tree has a depth of 2.  If someone steals your master key, you lost your funds because they'll iterate through 2^31 keys until they find your bitcoin. 

Now say you have a master key where every child has multiple children that have multiple children that ... that have have multiple children that might contain one of your transactions.  Your tree has a depth of D, with scrambled child index lookups at depth level.  So your first address with bitcoin might start with child index 1196412278 of child index 908842762 of child index 462865495 of child index 1386578953 of the master key.  When you do a transaction, your change address might be child index 33856490 of child index 2054789123 of child index 654982640 of child index 1445834988 of the master key.  Etc.

In the example just shown, with a depth layer of 5, there is a (2^31)^4 chance of guessing where the bitcoin are that this person has hidden in his 5-layer HD tree.  So even if a hacker gets this person's master key, they have an approximately 2.13 * 10^37 chance of finding that extended key that contains the private key to their funds.  One could have several more layers before things start to feel too slow.

One could have these layers being run by different servers accessible by different people. Because these tables would be vulnerable to leaking, and an attacker would know the layout of an entire scrambled layer(s) of the hierarchy, the values could be encrypted.  One could even go so far as to encrypt each row of a table with a key provided by a server running one level higher in the hierarchy, with each of these rows having a different encryption key.  So there'd be one more column to this child index scrambling table, ChildTableRowEncryptionKey. 

I really ought to go to bed though.  I'm waking up in 6 hours, with 4 hours of sleep last night.  Such is the life of a co-founder of CoinBeyond though.  We're trying hard to setup a system that customers will trust, or better yet, not have to trust, before we make the partnerships with card service companies.

What do you guys think?  Should I pursue this idea?

[jl2012]

So how would you store the sequence: {617492810, 741109822, 1840569824, 1056489135}?

If you consider this sequence as a secret, then it is essentially part of the root private key. If you could protect this sequence, you could protect your private key with the same level of security.

If you consider this sequence as public information, then it is essentially part of the root public key and you should assume it is known by everyone

Conclusion: your proposal brings no extra security.

[CoinBeyond]

So how would you store the sequence: {617492810, 741109822, 1840569824, 1056489135}?

If you consider this sequence as a secret, then it is essentially part of the root private key. If you could protect this sequence, you could protect your private key with the same level of security.

If you consider this sequence as public information, then it is essentially part of the root public key and you should assume it is known by everyone

Conclusion: your proposal brings no extra security.

Firstly, I appreciate your consideration of this system and value your feedback.

I think there may be some confusion on how it works, which is my fault. Let me try redescribing certain points.

The sequence is not stored. The key pair can be recomputed by following the path through the separate servers' separate database tables. The key pair is only good while funds are at that associated address, since all funds are moved to the next computed address by incrementing a row index that points to an encrypted random child index. So one sequence is not like part of the root private key. Each server only knows the next server's row to look up, the decryption key for that next row, and the extended key at its level. When a transaction is made, some layer after the customer layer increments its row index to the random encrypted child index, which tells it which child index to use for derivation at that layer and what the child server's row lookup index should be for the same actions.

It's also to protect from someone getting access to an extended key and being able to iterate through its derivations to find and retrieve funds trapped below that key. In this new system, an account's addresses are spread randomly through a subtree on many different extended keys. So access to a key lower in depth is needed to have a better chance of having an address with funds in its subtree, but then because there are several additional layers, iterating and finding those funds is not practical.

[jl2012]

Why could a hacker get access to the extended private key? If you can't keep the extended private key safe, how could you keep your index sequence safe? If you, with whatever method, can keep your index sequence very safe, why don't you simply do the same for your private key?

You mentioned using multiple servers. If you think multiple server could improve the security, why don't just use multisignature transactions, with each server having different keys?

Conclusion is still the same: it provides no extra security

(Side note: is your index sequence deterministic? If not, your wallet is not deterministic)

[oleganza]

The actual solution would be to use multisig. If your server stores someone's funds, then it's better to lock them up with 2-of-3 keys: one the server's, another one derived from user's password, and third is emergency key that belongs to the staff (in case user forgets his password). Your server will automate part of its job, but if it's compromised, users do not lose everything.