Re: [bitcoin-dev] An alternative to BIP 32?

From: vjudeu <vjudeu@gazeta•pl>
To: Tim Ruffing <crypto@timruffing•de>,
	"bitcoin-dev@lists•linuxfoundation.org"
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] An alternative to BIP 32?
Date: Mon, 22 Mar 2021 08:51:00 +0100	[thread overview]
Message-ID: <126012152-39f82455cdb5fc18203880bbba2d7b06@pmq7v.m5r2.onet> (raw)

> I can't really answer that question because it's not specified how "nonce" is obtained.

Nonce depends directly on your derivation path. By default, you can just start from 256-bit zero value and increment it if you want standard derivation path. But optionally it can be something else that is unique, for example username. So, if you have "0/0/0/0" derivation path, then you have four nonces with 256-bit zero each time. But if you have '0/"bitcointalk.org"/5321992/"coinlatte"' derivation path (as mentioned by the author of this scheme), then your first nonce is 256-bit zero value, your second nonce is SHA-256 of "bitcointalk.org", which is f245bd5620ee79314f48d9e9641a5406bd03745f6ac516e2801ef6ccbfe40ced, your third nonce is 0000000000000000000000000000000000000000000000000000000000513508 and your fourth nonce is 314870494d3a9136ba0a67ceb33534cbd438e982105d20cc076204c6fc99594d. There is an example in mentioned topic here: https://bitcointalk.org/index.php?topic=5321992.msg56503261#msg56503261

> the master private key is involved in the derivation of "nonce" (then "nonce" may be unpredictable)

It is impossible, because having some parent public key should be enough to derive child public keys. But even if you know the nonce, you have no idea what masterPublicKey was used in SHA-256 (that is the thing you are looking for if you try to link addresses together).

To see how difficult it is to get some parent key from some child key, you can try going up the tree in the mentioned example. SHA-256 empty string is e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855, but if used directly, that leads us to some key starting with 03 prefix, so we should negate it and get 1c4f3bbd6703e3eb65040b37669046da93009b024aad0cef1b3cc57157e388ec. Then, we have our child key 02 a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd and to break this scheme and prove that going to the parent key is possible, we have to find something like this:

masterPublicKey = attackerPublicKey + SHA256(attackerPublicKey || nonce)

02 a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd = attackerPublicKey + SHA-256(attackerPublicKey || 0000000000000000000000000000000000000000000000000000000000000000)

For me, it seems that finding attackerPublicKey here is impossible. Of course the absence of solution does not mean that it is secure, but I think it is a good example to show how strong this scheme is.

On 2021-03-21 22:45:19 user Tim Ruffing <crypto@timruffing•de> wrote:
> On Sat, 2021-03-20 at 21:25 +0100, vjudeu via bitcoin-dev wrote:
> > So, things have to be complicated to be secure?
> 
> Not at all. But we first need to spend some thoughts on what "secure"
> means before we can tell if something is secure.
> 
> >  By definition, using some private key, calculating some public key
> > from it and incrementing that key is secure (it is definitely no
> > worse than address reuse). 
> 
> If secure means that it does not hurt the unforgeability of ECDSA, then
> I believe you're right.
> 
> > The only problem with using "privKey", "(privKey+1) mod n",
> > "(privKey+2) mod n" and so on is that all of those public keys could
> > be easily linked together. If that is the only problem, then by
> > making offset deterministic but less predictable, it should be secure
> > enough, right? So, instead of simple incrementation, we would have
> > "privKey" (parent), "(privKey+firstOffset) mod n" (first child),
> > "(privKey+secondOffset) mod n" (second child) and so on. And as long
> > as this offset is not guessed by the attacker, it is impossible to
> > link all of those keys together, right?
> 
> I believe this intuition is also a good first approach. So let's have a
> look:  You say that offset = SHA256(masterPublicKey || nonce). Is this
> predictable by the attacker? 
> 
> I can't really answer that question because it's not specified how
> "nonce" is obtained.  Since this is supposed to be a deterministic
> scheme, I see two basic ways: Either the master private key is involved
> in the derivation of "nonce" (then "nonce" may be unpredictable) or
> it's not (then "nonce" is predictable).  
> 
> Another fact that may or not be a problem is that it may be possible to
> compute a parent private key from the a private key. Again, I can't
> tell because I don't know how nonce is obtained. 	
> 
> Taking a step back, BIP 32 addresses all of these concerns. I agree it
> could be simpler but I don't see a practical necessity to invent a new
> scheme. In any application where this proposal could potentially be
> used, BIP 32 could also be used and it's just good enough.
> 
> Tim 
> 
> 
> > 
> > > On 2021-03-20 11:08:30 user Tim Ruffing <crypto@timruffing•de>
> > > wrote:
> > > > On Fri, 2021-03-19 at 20:46 +0100, vjudeu via bitcoin-dev wrote:
> > > > > is it safe enough to implement it and use in practice?
> > > > 
> > > > This may be harsh but I can assure you that a HD wallet scheme
> > > > that can
> > > > be specified in 3 lines (without even specifying what the
> > > > security
> > > > goals are) should not be assumed safe to implement.
> > > > 
> > > > Tim 
> > > > 
> > > > 
> > > 
> > 
> > 
> > 
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists•linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
> 
> 