Bitcoin Forum
November 22, 2017, 07:21:54 PM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Protecting Hierarchical Deterministic Structures With Multiple Scrambled Levels  (Read 485 times)
CoinBeyond
Newbie
*
Offline Offline

Activity: 12


View Profile
May 02, 2014, 06:50:57 AM
 #1

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:
TxIndexChildIndex
0617492810
1741109822
21840569824
31056489135
...

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?
1511378514
Hero Member
*
Offline Offline

Posts: 1511378514

View Profile Personal Message (Offline)

Ignore
1511378514
Reply with quote  #2

1511378514
Report to moderator
Join ICO Now Coinlancer is Disrupting the Freelance marketplace!
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1511378514
Hero Member
*
Offline Offline

Posts: 1511378514

View Profile Personal Message (Offline)

Ignore
1511378514
Reply with quote  #2

1511378514
Report to moderator
1511378514
Hero Member
*
Offline Offline

Posts: 1511378514

View Profile Personal Message (Offline)

Ignore
1511378514
Reply with quote  #2

1511378514
Report to moderator
1511378514
Hero Member
*
Offline Offline

Posts: 1511378514

View Profile Personal Message (Offline)

Ignore
1511378514
Reply with quote  #2

1511378514
Report to moderator
jl2012
Legendary
*
Offline Offline

Activity: 1722


View Profile
May 02, 2014, 07:47:23 AM
 #2

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.

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
CoinBeyond
Newbie
*
Offline Offline

Activity: 12


View Profile
May 02, 2014, 09:59:15 AM
 #3

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
Legendary
*
Offline Offline

Activity: 1722


View Profile
May 02, 2014, 10:57:09 AM
 #4

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)

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
oleganza
Full Member
***
Offline Offline

Activity: 200


Software design and user experience.


View Profile WWW
May 02, 2014, 01:47:22 PM
 #5

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.

Bitcoin analytics: blog.oleganza.com / 1TipsuQ7CSqfQsjA9KU5jarSB1AnrVLLo
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!