[bitcoin-dev] An alternative to BIP 32?

[bitcoin-dev] An alternative to BIP 32?

[vjudeu]

[-- Attachment #1: Type: text/plain, Size: 674 bytes --]

I recently found some interesting and simple HD wallet design here: https://bitcointalk.org/index.php?topic=5321992.0
Could anyone see any flaws in such design or is it safe enough to implement it and use in practice?
If I understand it correctly, it is just pure ECDSA and SHA-256, nothing else:
masterPublicKey = masterPrivateKey * G
masterChildPublicKey = masterPublicKey + ( SHA-256( masterPublicKey || nonce ) mod n ) * G
masterChildPrivateKey = masterPrivateKey + ( SHA-256( masterPublicKey || nonce ) mod n )
Also, it has some nice properties, like all keys starting with 02 prefix and allows potentially unlimited custom derivation path by using 256-bit nonce.

[-- Attachment #2: Type: text/html, Size: 707 bytes --]

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

[Erik Aronesty]

use sha3-256.  sha256 suffers from certain attacks (length extension,
for example) that could make your scheme vulnerable to leaking info,
depending on how you concatenate things, etc.  better to choose
something where padding doesn't matter.

On Fri, Mar 19, 2021 at 7:28 PM vjudeu via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> I recently found some interesting and simple HD wallet design here: https://bitcointalk.org/index.php?topic=5321992.0
> Could anyone see any flaws in such design or is it safe enough to implement it and use in practice?
> If I understand it correctly, it is just pure ECDSA and SHA-256, nothing else:
>
> masterPublicKey = masterPrivateKey * G
> masterChildPublicKey = masterPublicKey + ( SHA-256( masterPublicKey || nonce ) mod n ) * G
> masterChildPrivateKey = masterPrivateKey + ( SHA-256( masterPublicKey || nonce ) mod n )
>
> Also, it has some nice properties, like all keys starting with 02 prefix and allows potentially unlimited custom derivation path by using 256-bit nonce.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Arik Sosman]

[-- Attachment #1: Type: text/plain, Size: 1769 bytes --]

Hi Erik,

Would sha256-hmac(nonce, publicKeyPoint) still be a suitable/safe alternative without relying on sha3? That should at the very least eliminate length extension attacks.

Best,
Arik

> On Mar 19, 2021, at 6:32 PM, Erik Aronesty via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> use sha3-256.  sha256 suffers from certain attacks (length extension,
> for example) that could make your scheme vulnerable to leaking info,
> depending on how you concatenate things, etc.  better to choose
> something where padding doesn't matter.
> 
> On Fri, Mar 19, 2021 at 7:28 PM vjudeu via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
>> 
>> I recently found some interesting and simple HD wallet design here: https://bitcointalk.org/index.php?topic=5321992.0
>> Could anyone see any flaws in such design or is it safe enough to implement it and use in practice?
>> If I understand it correctly, it is just pure ECDSA and SHA-256, nothing else:
>> 
>> masterPublicKey = masterPrivateKey * G
>> masterChildPublicKey = masterPublicKey + ( SHA-256( masterPublicKey || nonce ) mod n ) * G
>> masterChildPrivateKey = masterPrivateKey + ( SHA-256( masterPublicKey || nonce ) mod n )
>> 
>> Also, it has some nice properties, like all keys starting with 02 prefix and allows potentially unlimited custom derivation path by using 256-bit nonce.
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

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

[Tim Ruffing]

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 

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

[Erik Aronesty]

yes that would be fine.    not sure what your objection to sha3 is tho
(more provably secure) - i guess sticking with bitcoin-lib stuff tho.

On Fri, Mar 19, 2021 at 10:08 PM Arik Sosman <me@arik.io> wrote:
>
> Hi Erik,
>
> Would sha256-hmac(nonce, publicKeyPoint) still be a suitable/safe alternative without relying on sha3? That should at the very least eliminate length extension attacks.
>
> Best,
> Arik
>
> > On Mar 19, 2021, at 6:32 PM, Erik Aronesty via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> > use sha3-256.  sha256 suffers from certain attacks (length extension,
> > for example) that could make your scheme vulnerable to leaking info,
> > depending on how you concatenate things, etc.  better to choose
> > something where padding doesn't matter.
> >
> > On Fri, Mar 19, 2021 at 7:28 PM vjudeu via bitcoin-dev
> > <bitcoin-dev@lists.linuxfoundation.org> wrote:
> >>
> >> I recently found some interesting and simple HD wallet design here: https://bitcointalk.org/index.php?topic=5321992.0
> >> Could anyone see any flaws in such design or is it safe enough to implement it and use in practice?
> >> If I understand it correctly, it is just pure ECDSA and SHA-256, nothing else:
> >>
> >> masterPublicKey = masterPrivateKey * G
> >> masterChildPublicKey = masterPublicKey + ( SHA-256( masterPublicKey || nonce ) mod n ) * G
> >> masterChildPrivateKey = masterPrivateKey + ( SHA-256( masterPublicKey || nonce ) mod n )
> >>
> >> Also, it has some nice properties, like all keys starting with 02 prefix and allows potentially unlimited custom derivation path by using 256-bit nonce.
> >> _______________________________________________
> >> bitcoin-dev mailing list
> >> bitcoin-dev@lists.linuxfoundation.org
> >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

[vjudeu]

> 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
> 
> 
> 

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

[Tim Ruffing]

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

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

[vjudeu]

So, things have to be complicated to be 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). 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?

> 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 
> > 
> > 
> 

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

[vjudeu]

How length extension attack is possible here? The input of SHA-256 has constant length of 512 bits in this scheme. And if someone will get some child public key, there is still no way to reverse it to the parent public key, because even if the second block of SHA-256 is the same all the times, the attacker still does not know the outcome of SHA-256, so the last round of SHA-256 is unknown and doing calculations backwards seems to be impossible.

> On 2021-03-20 03:08:39 user Arik Sosman <me@arik.io> wrote:
> > Hi Erik,
> > 
> > Would sha256-hmac(nonce, publicKeyPoint) still be a suitable/safe alternative without relying on sha3? That should at the very least eliminate length extension attacks.
> > 
> > Best,
> > Arik
> > 
> > > On Mar 19, 2021, at 6:32 PM, Erik Aronesty via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > > 
> > > use sha3-256.  sha256 suffers from certain attacks (length extension,
> > > for example) that could make your scheme vulnerable to leaking info,
> > > depending on how you concatenate things, etc.  better to choose
> > > something where padding doesn't matter.
> > > 
> > > On Fri, Mar 19, 2021 at 7:28 PM vjudeu via bitcoin-dev
> > > <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > >> 
> > >> I recently found some interesting and simple HD wallet design here: https://bitcointalk.org/index.php?topic=5321992.0
> > >> Could anyone see any flaws in such design or is it safe enough to implement it and use in practice?
> > >> If I understand it correctly, it is just pure ECDSA and SHA-256, nothing else:
> > >> 
> > >> masterPublicKey = masterPrivateKey * G
> > >> masterChildPublicKey = masterPublicKey + ( SHA-256( masterPublicKey || nonce ) mod n ) * G
> > >> masterChildPrivateKey = masterPrivateKey + ( SHA-256( masterPublicKey || nonce ) mod n )
> > >> 
> > >> Also, it has some nice properties, like all keys starting with 02 prefix and allows potentially unlimited custom derivation path by using 256-bit nonce.
> > >> _______________________________________________
> > >> bitcoin-dev mailing list
> > >> bitcoin-dev@lists.linuxfoundation.org
> > >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> > > _______________________________________________
> > > bitcoin-dev mailing list
> > > bitcoin-dev@lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> > 
> > 
> 
> 
> 
>