Bitcoin Forum
December 14, 2024, 05:01:38 AM *
News: Latest Bitcoin Core release: 28.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 [2]  All
  Print  
Author Topic: New HD wallet that tolerates leakage of some child private keys  (Read 3973 times)
Crowex
Member
**
Offline Offline

Activity: 111
Merit: 10


View Profile
January 08, 2015, 06:51:44 PM
 #21

Implement a "flat" or "simulated" hierarchy, meaning that the key m/x/y/z is a linear combination of the original n master keys d1,...,dn where the coefficients are derived from the hash of (x,y,z).  Note that a total of no more than n-1 private keys can be revealed from anywhere in the hierarchy.  That might seem bad but it's still an improvement on BIP32, where any one (non-hardened) private key from anywhere in the hierarchy can be combined with the master public key to break the wallet.

I'm not sure exactly how this scheme would work but it's also very easy to break the public key derivation property when you start using hashes for the coefficients.
It's one of those problems were, when you solve one thing you break something else. Smiley
ggutoski (OP)
Newbie
*
Offline Offline

Activity: 6
Merit: 0


View Profile
January 08, 2015, 07:43:25 PM
 #22

I'm not sure exactly how this ["flat" or "simulated"] scheme would work but it's also very easy to break the public key derivation property when you start using hashes for the coefficients.
It's one of those problems were, when you solve one thing you break something else. Smiley

We don't even really need a hash function for generating coefficients.  All we really need is some way to map a child index to a vector of coefficients in such a way that two distinct child indices are unlikely to map to the same coefficients.  Even if the coefficients are completely predictable, an adversary still has the problem of solving a system of t<m linear equations in m unknowns.  (See "Remark 1" at the end of the paper.)

This "flat" scheme is dumb anyway.  It really only applies when the master public keys are public knowledge, since they're always needed to generate descendants.  (Previous post edited to include this fact.)  In that case, all HD wallet trees are equivalent to a single-level tree in the sense that there's no significant difference between a depth-three child m/x/y/z and a depth-one child m/(xyz) where (xyz) is some way of encoding the three indices x,y,z into a single index.  (Hence the name "flat".)  In order for a multi-level hierarchy to be functionally distinct from a single-level hierarchy you need the property that each subtree can pretend to be its own separate tree and doesn't need to know anything about its ancestors (ie. the master public keys are no longer public knowledge).  But the "flat" scheme doesn't have this property.  I shouldn't have mentioned it.
ggutoski (OP)
Newbie
*
Offline Offline

Activity: 6
Merit: 0


View Profile
January 08, 2015, 08:21:10 PM
 #23

Your security argument rests on 1MDLP, but we actually use these keys in the context of ECDSA. Inability to solve the DLP (or 1MDLP) does not provably result in the security of ECDSA, and ECDSA reveals another (random) linear relationship with the keys in question; it's concealable that it could undermine the security of the scheme. For example, imagine if the nonce were secrete but constant.  Off the cuff, I do not see a reason that this is problematic for the security of your construction. Though in an abundance of caution we specifically constructed BIP32 to avoid constant any linear relationship out of concern for potential interactions with ECDSA which we were unable to prove did not exist.

If I understand correctly, you're worried about some problem introduced by the confluence of the facts that (i) our child private keys are constructed by linear combinations of the master private keys, and (ii) each ECDSA signature reveals a linear equation involving the private key.  But, as you say, the information revealed in an ECDSA signature is masked by the random nonce so it's hard to see how this could be a problem.  And if the nonce is "secret but constant" than you're screwed anyway.

What we do have is that recovering the wallet's signing keys without access to any signatures is as hard as the 1MDLP for elliptic curves.

Other than that, I'm not sure how to respond.  This concern could apply to any use of ECDSA in which the keys are not truly random.  I guess in order to address it one would need to prove a general reduction from cracking ECDSA with arbitrary keys to cracking ECDSA with constraints on key selection.

Thanks!  Thanks again to everyone for the feedback.  It's a shame we didn't get your feedback back when this paper was under review.  I guess in the future we should post to bitcointalk.org before submitting. Smiley
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4298
Merit: 8818



View Profile WWW
January 08, 2015, 11:29:33 PM
 #24

And if the nonce is "secret but constant" than you're screwed anyway.
It's actually okay to do this so long as your keys are truly unrelated you never reuse keys!  I ... don't know why you would ever do this! but there is some madman that appears to be doing this on the Bitcoin blockchain.

(well, okay, I can give an example of why you might do this:  If I don't have to compute kG, I can do a signing operation in under 1 microsecond, or about 100x faster.  But its still darwin award grade stupid.)

The reason I brought it up is that it just to illustrate that the reduction argument wasn't complete. It's probably not possible to make it complete given the shortcomings for provable security for ECDSA in general, I wouldn't fault your paper for it; only to note that risk isn't _completely_ eliminated by the proof.
iddo
Sr. Member
****
Offline Offline

Activity: 360
Merit: 251


View Profile
January 29, 2015, 10:39:36 AM
 #25

  • If you really want to give each child a,b,c,... ability to reveal up to na,nb,nc,... private keys then you need at least 1+na+nb+nc+... master private keys.  This isn't a problem if you're the top-level admin because you can generate the private keys deterministically.  But if you're an auditor (who is only allowed to know the master public keys and needs to store them explicitly) then you could run into an exponential blow-up of public key size: if you want each node in a k-ary tree of depth d to be able to reveal up to n keys then you need something like (kn)O(d) master keys.

You could follow BIP32 design and derive, for each child, m different tuples of coefficients hash(chaincode,i,j)=(a_{i,j,1},a_{i,j,2},...,a_{i,j,m}) where i is the index (i.e., tree path), and j runs from 1 to m too. This way we obtain m different pubkeys Q_i_1,Q_i_2,...,Q_i_m from the m pubkeys of the parent node Q_parent_1,Q_parent_2,...,Q_parent_m, for example Q_i_1 is a linear combination of the Q_parent_i pubkeys with (a_{i,1,1},a_{i,1,2},...,a_{i,1,m}) coefficients. Similarly to BIP32, you can use hash(chaincode,i,Q_parent_j) instead of hash(chaincode,i,j) to have more entropy.

This would mean that the granularity at each branch of the HD wallet is in multiplies of m, which would be a disadvantage with small branches and large m.

But the more important thing is that in practice it probably doesn't really accomplish anything, because if there's a security breach and some privkey of node i leaks, then most probably all the m privkeys at that node i leaked along with it. You could argue e.g. that against a theoretical crypto attack that computes a privkey from the pubkey in t time, you'll need to execute an attack of mt total time instead of t time, for a complete break of the HD wallet, but that isn't really interesting.

So I think that your original non-hierarchical secret sharing variant makes more sense, relative to hierarchical variants. One of the most common use-cases of BIP32 is just a personal wallet where you don't need to decrypt your privkeys to derive more public addresses, and there the non-hierarchical variant is fine.

So I think it would be an obvious improvement and might well be worth an increase in the resulting master public key size just for additional robustness, I don't know that in practise it would safely permit intentional use of it.

To say that public key size is the problem here seems kind of vague, I think that the main deficiency is that you need to perform m elliptic curve exponentations to derive the next pubkey, instead of a single exponentation. So I'm not sure if the tradeoff between the extra complexity versus the supposed better security makes sense (with non-hierarchical variant), it depends on whether the security improvement is significant in practical scenarios.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4298
Merit: 8818



View Profile WWW
January 29, 2015, 01:39:23 PM
 #26

So I think it would be an obvious improvement and might well be worth an increase in the resulting master public key size just for additional robustness, I don't know that in practise it would safely permit intentional use of it.

To say that public key size is the problem here seems kind of vague, I think that the main deficiency is that you need to perform m elliptic curve exponentations to derive the next pubkey, instead of a single exponentation. So I'm not sure if the tradeoff between the extra complexity versus the supposed better security makes sense (with non-hierarchical variant), it depends on whether the security improvement is significant in practical scenarios.
You use multi-exp which is not N times slower, and wnaf with some big tables on each of your points, so it's only a couple adds even if your coefficients are big. libsecp256k1 on a fast laptop does something like 70k ecdsa verifies per second, and that involves a multiexp on two points (and a number of other expensive operations: a modinv for s and a sqrt to recover the pubkey). So, I don't see why you'd consider that an issue even with hundreds of points.  The reason I cited size is that the advantage of the homomorphic derivation over independent keys at all is size, and having to grow the pubkey linearly in use (to be secure in the worst case) erodes that improvement.
Crowex
Member
**
Offline Offline

Activity: 111
Merit: 10


View Profile
January 29, 2015, 05:54:28 PM
 #27

So I think that your original non-hierarchical secret sharing variant makes more sense, relative to hierarchical variants. One of the most common use-cases of BIP32 is just a personal wallet where you don't need to decrypt your privkeys to derive more public addresses, and there the non-hierarchical variant is fine.

I don't understand what non-hierarchical variant you are talking about? Everything in the abstract and the OP refers to a hierarchical (HD) wallet.

iddo
Sr. Member
****
Offline Offline

Activity: 360
Merit: 251


View Profile
January 29, 2015, 06:35:58 PM
 #28

So I think that your original non-hierarchical secret sharing variant makes more sense, relative to hierarchical variants. One of the most common use-cases of BIP32 is just a personal wallet where you don't need to decrypt your privkeys to derive more public addresses, and there the non-hierarchical variant is fine.
I don't understand what non-hierarchical variant you are talking about? Everything in the abstract and the OP refers to a hierarchical (HD) wallet.

The title of the short paper says "hierarchical", but it actually only specifies the non-hierarchical variant of the OP of the 2011 thread (https://bitcointalk.org/index.php?topic=19137.0), without chaincodes.
With an hierarchical variant you can delegate the root of a sub-tree of the wallet's hierarchy to a third party, without giving this third party access to the other branches of the tree.
iddo
Sr. Member
****
Offline Offline

Activity: 360
Merit: 251


View Profile
January 29, 2015, 06:57:01 PM
 #29

So I think it would be an obvious improvement and might well be worth an increase in the resulting master public key size just for additional robustness, I don't know that in practise it would safely permit intentional use of it.

To say that public key size is the problem here seems kind of vague, I think that the main deficiency is that you need to perform m elliptic curve exponentations to derive the next pubkey, instead of a single exponentation. So I'm not sure if the tradeoff between the extra complexity versus the supposed better security makes sense (with non-hierarchical variant), it depends on whether the security improvement is significant in practical scenarios.
You use multi-exp which is not N times slower, and wnaf with some big tables on each of your points, so it's only a couple adds even if your coefficients are big. libsecp256k1 on a fast laptop does something like 70k ecdsa verifies per second, and that involves a multiexp on two points (and a number of other expensive operations: a modinv for s and a sqrt to recover the pubkey). So, I don't see why you'd consider that an issue even with hundreds of points.  The reason I cited size is that the advantage of the homomorphic derivation over independent keys at all is size, and having to grow the pubkey linearly in use (to be secure in the worst case) erodes that improvement.

Hmm wnaf="window non-adjacent form", some more efficient representation it seems, I had to google that... I wasn't aware of these fast multi-exp methods, cool.

I'm trying to see if I understand why you say that the pubkey size needs to grow: with an efficient multi-exp as you suggest, we can for example extend BIP32 to make a new child node in the tree hierarchy so that the branch that starts at this child is a non-hierarchical variant with secret sharing of m keys, so that if one (or several) privkeys leak in this branch then all the other privkeys are still secure. But for this we'll need to store m pubkeys at this new child node, which implies the size growth? That's the idea? Maybe that's still a nice extension, because it'd be optional, and even if you prune these m pubkeys they can still be re-derived later from the master privkey, just like non-homomorphic type-1 "subaccounts" can be re-derived from the master privkey.

Crowex
Member
**
Offline Offline

Activity: 111
Merit: 10


View Profile
January 29, 2015, 07:15:28 PM
 #30

So I think that your original non-hierarchical secret sharing variant makes more sense, relative to hierarchical variants. One of the most common use-cases of BIP32 is just a personal wallet where you don't need to decrypt your privkeys to derive more public addresses, and there the non-hierarchical variant is fine.
I don't understand what non-hierarchical variant you are talking about? Everything in the abstract and the OP refers to a hierarchical (HD) wallet.

The title of the short paper says "hierarchical", but it actually only specifies the non-hierarchical variant of the OP of the 2011 thread (https://bitcointalk.org/index.php?topic=19137.0), without chaincodes.
With an hierarchical variant you can delegate the root of a sub-tree of the wallet's hierarchy to a third party, without giving this third party access to the other branches of the tree.

The paper quite clearly claims to introduce a new hierarchical wallet. It claims to solve problems that other hierarchical wallets have.
I agree with you that the paper doesn't actually specify a hierarchical wallet.
dabura667
Sr. Member
****
Offline Offline

Activity: 475
Merit: 252


View Profile
February 19, 2015, 06:07:07 PM
 #31

ggutoski>

https://gist.github.com/dabura667/875bb2c159b219c18885

What about something like this?

Using convention, 2 keys are all that is needed to prevent leakage from a nearly unlimited amount of leaked keys.

Please give me any feedback. I am currently working on implementing in Python.

My Tip Address:
1DXcHTJS2DJ3xDoxw22wCt11FeAsgfzdBU
Pages: « 1 [2]  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!