Subject: Re: [Cfrg] Questions regarding BIP32-Ed25519 (was: Interest in an "Ed25519-HD" standard?)

From: Dmitry Khovratovich <[email-masked]>
Date: Tue, 4 Apr 2017 11:40:28 +0200

Hi Oleg,

thank you for the questions!

On Fri, Mar 31, 2017 at 8:06 PM, Oleg Andreev <[email-masked]> wrote:

> Dmitry,
>
> Thanks for your with Jason paper on adopting BIP32 to Ed25519 and critique
> of ChainKD, very appreciated. I have a few questions about it:
>
> 1. Why do you impose requirements on the master secret to yield 3rd high
> bit to be zero, while you can simply set it to zero along with other 5
> bits. In two places you mention that you reject non-compliant master
> secret, but in Security section (F) you say "we set 6 bits", which is what
> seems to be the intention all along.
>

Our idea was to reject as few master secrets as possible, so we decided to
clear only one extra bit, thus rejecting half of master keys. By setting 6
bits I mean that we set three highest and three lowest bits.

>
> 2. You choose 2^20 as a max depth level therefore leaving 2^230 bits for
> the derived key. In your paper you round this down to whole number of bytes
> (28 bytes -> 2^224) while it's actually possible to slightly increase
> collision-resistance by taking 29 bytes instead and clearing top 2 bits.
> Have you considered that, and if yes, is there any issues with that?
>

Apart from clearing one more bit, the idea to take 28 bytes instead of 29
is to cut a 32-bit word, which could simplify some implementations. I agree
it is a minor issue.

>
> 3. What was the rationale for 2^20 as a depth limit? I myself don't have a
> good framework to decide which limit is the best, so I'm wondering if you
> have? :)
>

The use cases we have seen did not require hierarchy deeper than a few
dozen levels. I think 2^20 is a safe bound as long as every new level has
some real-world meaning (extra wallet, extra connection, etc.), and thus it
seems unlikely that this set will be ever exhausted by any user.

>
> 4. You effectively make xprv to be 96-byte string (32 bytes for the
> scalar, 32 bytes for the "prefix" used in nonce generation and 32 byte
> chain code), and use two HMAC calls to derive new chain code separately
> from the privkey. Have you considered expanding the 64-byte privkey (as
> defined by NaCl library) from the scalar itself? In my recent tweak to
> ChainKD scheme [1] I'm doing that and to stay fully compatible with EdDSA
> requirement that prefix originally has 256 bits of entropy, add only one
> secret byte ("pepper") that eats 8 bits from the chain code (which we call
> "salt"). This allows us to keep both xprv and xpub 64 bytes long and avoid
> double-HMAC when deriving public keys - single hash call produces a key
> component and another salt value.
>

We just tried to mimic the original BIP32 key derivation as much as
possible. I am not sure I entirely understands the rationale behind your
manipulation with bytes of private key after you add up the hash output.
Also, could you elaborate on the notions of EdDSA public and private keys,
which seem to complement public and private keys you derive in the scheme?

Best regards,
Dmitry

>
> Thank you!
>
> [1] Updated ChainKD: https://github.com/chain/chain/blob/chainkd-dh/docs/
> protocol/specifications/chainkd.md
>
>
>
> > Being a co-author of [5], I am ready to contribute to such a document. I
> > will present our own proposal at
> > http://prosecco.gforge.inria.fr/ieee-blockchain2016/ in Paris  just
> before
> > the CFRG meeting at the same place next day. It would be great if we come
> > up with some proposal to discuss it already there.
> >
> > The most recent version is
> > https://drive.google.com/open?id=0ByMtMw2hul0EMFJuNnZORDR2NDA It has
> some
> > critique of [6], hopefully not too offensive:)
> >
> > Our motivation in [5] was to generate private keys satisfying the
> > Curve25519 requirements too so that the code can be reused, even if in
> the
> > signature setting some attacks would not apply. But it would be great to
> > have comments from the community as well.
> >
> > Best regards,
> > Dmitry
> >
> > On Wed, Mar 22, 2017 at 5:00 AM, Phillip Hallam-Baker <
> [email-masked]
> > > wrote:
> >
> > > You can do hierarchical key derivation in Montgomery without the need
> for
> > > an add.
> > >
> > > Say your master key is x. To generate a key for site 'example.com' we
> > > take
> > >
> > > xs = (x + H('example.com')) mod q
> > >
> > > Where q is the sub group order.
> > >
> > > In fact that isn't really using any EC relevant operation at all.
> Perhaps
> > > I am not understanding the full requirements for the scheme.
> > >
> > >
> > > I don't follow the argument about small subgroups in the referenced
> post.
> > > With Curve25519 and Ed25519 we have chosen the curve cofactor and the
> > > generator point. So there is only one group that our point can
> possibly be
> > > in regardless of whether our private key is (x mod q) or (x mod q +
> nq). We
> > > are going to arrive at the same set of points regardless.
> > >
> > >
> > > I do very much prefer the Edwards curves though because we can combine
> two
> > > keypairs by simply adding the corresponding public and private keys.
> That
> > > allows us to do the co-generation trick I showed a while back.
> > >
> > > We can also split the key, give one part to a recryption service and
> > > encrypt the other half under the public key of the recipient. This
> allows
> > > us to support group messaging through proxy re-encryption.
> > >
> > > Some applications of that are encumbered (possibly) under a soon to
> expire
> > > patent.
> > >
> > >
> > >
> > > On Tue, Mar 21, 2017 at 8:34 PM, Phillip Hallam-Baker <
> > > [email-masked]> wrote:
> > >
> > >> I have just implemented Proxy Re-Encryption under Ed-25519 and Ed448.
> I
> > >> think EdCurve Crypto is a good plan.
> > >>
> > >> Or we could do it on the Montgomery Curves and give the algorithm for
> > >> point addition.
> > >>
> > >> On Tue, Mar 21, 2017 at 3:42 PM, Tony Arcieri <[email-masked]>
> wrote:
> > >>
> > >>> Hierarchical key derivation (also sometimes described as "semiprivate
> > >>> keys" or "key blinding") is an increasingly popular technique for
> > >>> generating unlinkable child keys from master public and private keys.
> > >>>
> > >>> The Tor Project has been exploring such an approach as the basis for
> > >>> their next-generation hidden services design for several years
> now[1],
> > >>> during which time it has received security proofs[2]. Their latest
> > >>> design[3] allegedly includes feedback from Dan Bernstein.
> > >>>
> > >>> Application of hierarchical key derivation is perhaps most notable in
> > >>> the cryptocurrency space, where Bitcoin's BIP32[4] provided a means
> for
> > >>> unlinkable single-use signature keys for the secp256k1 elliptic
> curve.
> > >>> There are several designs for applying the ideas from BIP32 to
> Ed25519,
> > >>> including ones from Evernym[5] and Chain[6] (where I am an employee).
> > >>>
> > >>> The designs in [3], [5], and [6] are all highly similar and
> accomplish
> > >>> the same goals. Personally I would love to see a single standard
> design for
> > >>> producing Ed25519 signatures from hierarchically derived keys,
> notably one
> > >>> which produces signatures that can be verified by any off-the-shelf
> RFC
> > >>> 8032-compatible Ed25519 implementation.
> > >>>
> > >>> There's already been some discussion of this on the moderncrypto.org
> > >>> curves list:
> > >>>
> > >>> https://moderncrypto.org/mail-archive/curves/2017/000858.html
> > >>>
> > >>> I'd be curious to know if anyone else would be interested in
> > >>> collaborating on a draft for such a standard, which can be a
> synthesis of
> > >>> the existing work in this space.
> > >>>
> > >>> [1]: https://lists.torproject.org/pipermail/tor-dev/2012-Sep
> > >>> tember/004026.html
> > >>> [2]: https://www-users.cs.umn.edu/~hopper/basic-proof.pdf
> > >>> [3]: https://gitweb.torproject.org/torspec.git/tree/proposal
> > >>> s/224-rend-spec-ng.txt#n1979
> > >>> [4]: https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
> > >>> [5]: https://github.com/WebOfTrustInfo/rebooting-the-web-of-
> > >>> trust-fall2016/blob/master/topics-and-advance-readings/HDKey
> > >>> s-Ed25519.pdf
> > >>> [6]: https://chain.com/docs/protocol/specifications/chainkd
> > >>>
> > >>> --
> > >>> Tony Arcieri
> > >>>
> > >>> _______________________________________________
> > >>> Cfrg mailing list
> > >>> [email-masked]
> > >>> https://www.irtf.org/mailman/listinfo/cfrg
> > >>>
> > >>>
> > >>
> > >
> > > _______________________________________________
> > > Cfrg mailing list
> > > [email-masked]
> > > https://www.irtf.org/mailman/listinfo/cfrg
> > >
> > >
> >
> >
> > --
> > Best regards,
> > Dmitry Khovratovich
>

-- 
Best regards,
Dmitry Khovratovich

---

From: Oleg Andreev <[email-masked]>
Date: Tue, 4 Apr 2017 17:24:32 -0700

Thanks for the detailed reply.

> 1. Why do you impose requirements on the master secret to yield 3rd high bit to be zero, while you can simply set it to zero along with other 5 bits. In two places you mention that you reject non-compliant master secret, but in Security section (F) you say "we set 6 bits", which is what seems to be the intention all along.
> 
> Our idea was to reject as few master secrets as possible, so we decided to clear only one extra bit, thus rejecting half of master keys. By setting 6 bits I mean that we set three highest and three lowest bits.

I probably did not phrase my question clearly in the first place. I meant, why don't you reject _none_ of the master secrets by simply setting 6 bits as required? If the third highest bit happen to be not zero, instead of rejecting the master secret, simply set it to zero? What'd be wrong with that?

> 2. You choose 2^20 as a max depth level therefore leaving 2^230 bits for the derived key. In your paper you round this down to whole number of bytes (28 bytes -> 2^224) while it's actually possible to slightly increase collision-resistance by taking 29 bytes instead and clearing top 2 bits. Have you considered that, and if yes, is there any issues with that?
> 
> Apart from clearing one more bit, the idea to take 28 bytes instead of 29 is to cut a 32-bit word, which could simplify some implementations. I agree it is a minor issue.

Oh, it's 32-bit aligned then, I see. Thanks!

>  
> 3. What was the rationale for 2^20 as a depth limit? I myself don't have a good framework to decide which limit is the best, so I'm wondering if you have? :)
> 
> The use cases we have seen did not require hierarchy deeper than a few dozen levels. I think 2^20 is a safe bound as long as every new level has some real-world meaning (extra wallet, extra connection, etc.), and thus it seems unlikely that this set will be ever exhausted by any user.

I thought along the same lines, but I can imagine an immense scope for bikeshedding around that number (unfortunately). The 2^20 depth seems fine by me, but there are over 9000 opinions waiting to enter that territory and I'd love to figure out a good story defending any particular decision to avoid wasting a lot of time on it :-) 

> 4. You effectively make xprv to be 96-byte string (32 bytes for the scalar, 32 bytes for the "prefix" used in nonce generation and 32 byte chain code), and use two HMAC calls to derive new chain code separately from the privkey. Have you considered expanding the 64-byte privkey (as defined by NaCl library) from the scalar itself? In my recent tweak to ChainKD scheme [1] I'm doing that and to stay fully compatible with EdDSA requirement that prefix originally has 256 bits of entropy, add only one secret byte ("pepper") that eats 8 bits from the chain code (which we call "salt"). This allows us to keep both xprv and xpub 64 bytes long and avoid double-HMAC when deriving public keys - single hash call produces a key component and another salt value.
> 
> We just tried to mimic the original BIP32 key derivation as much as possible. I am not sure I entirely understands the rationale behind your manipulation with bytes of private key after you add up the hash output. Also, could you elaborate on the notions of EdDSA public and private keys, which seem to complement public and private keys you derive in the scheme?

The main problem I see is that extended private key in BIP32-Ed25519 paper becomes pretty long - 96 bytes (also not symmetrical with xpub which is 64-byte). It has 32 bytes for the scalar, 32 bytes for the secret "prefix" (from where the nonce is derived) and 32 bytes for the chain code. In EdDSA both the scalar and the "prefix" are derived from a 256-bit secret, so my suggestion is to derive the "prefix" from the scalar, but since the scalar only has 250 bits of entropy, we can throw in extra 6 bits by using a "pepper" byte to be 100% safe :-) In other words, the full 64-byte "private key" as expected by NaCl has shape: <scalar><Hash(scalar || pepper)> so we do not explode the size of xprv to carry additional 32 bytes.
 
I justify that decision by RFC6979 behavior which is effectively doing the same: the source of entropy for the nonce is the signing key (32-byte), not the 32-byte key + some additional secret 32 bytes of entropy. In EdDSA it's the same - both are derived from a master 32-byte buffer (which, of course, we cannot use because of need for linear non-hardened derivation). I'm curious is there a concern regarding such space optimization?

---

From: Oleg Andreev <[email-masked]>
Date: Wed, 5 Apr 2017 14:20:24 -0700

A quick follow-up: I have simplified our spec a little to pack additional bits on entropy to the private key part (instead of borrowing one byte from the chain code), and renamed "salt" / "chain code" to a "derivation key" because it enables derivation and proofs of linkage. I've also clarified what EdDSA public and private keys are in the glossary. Curious if that's more easy to follow now.

https://github.com/chain/chain/blob/chainkd-dh/docs/protocol/specifications/chainkd.md

> On 4 Apr 2017, at 02:40, Dmitry Khovratovich <[email-masked]> wrote:
> 
> Hi Oleg,
> 
> On Fri, Mar 31, 2017 at 8:06 PM, Oleg Andreev <[email-masked] <mailto:[email-masked]>> wrote:
> Dmitry,
> 
> Thanks for your with Jason paper on adopting BIP32 to Ed25519 and critique of ChainKD, very appreciated. I have a few questions about it:
> 
> [1] Updated ChainKD: https://github.com/chain/chain/blob/chainkd-dh/docs/protocol/specifications/chainkd.md <https://github.com/chain/chain/blob/chainkd-dh/docs/protocol/specifications/chainkd.md>
> 
> 
> 
> > http://prosecco.gforge.inria.fr/ieee-blockchain2016/ <http://prosecco.gforge.inria.fr/ieee-blockchain2016/> in Paris  just before
> > https://drive.google.com/open?id=0ByMtMw2hul0EMFJuNnZORDR2NDA <https://drive.google.com/open?id=0ByMtMw2hul0EMFJuNnZORDR2NDA> It has some
> > Curve25519 requirements too so that the code can be reused, even if in the
> > On Wed, Mar 22, 2017 at 5:00 AM, Phillip Hallam-Baker <[email-masked] <mailto:[email-masked]>
> > > wrote:
> >
> > > You can do hierarchical key derivation in Montgomery without the need for
> > > an add.
> > >
> > > Say your master key is x. To generate a key for site 'example.com <http://example.com/>' we
> > > take
> > >
> > > xs = (x + H('example.com <http://example.com/>')) mod q
> > >
> > > In fact that isn't really using any EC relevant operation at all. Perhaps
> > > I don't follow the argument about small subgroups in the referenced post.
> > > generator point. So there is only one group that our point can possibly be
> > > in regardless of whether our private key is (x mod q) or (x mod q + nq). We
> > > I do very much prefer the Edwards curves though because we can combine two
> > > keypairs by simply adding the corresponding public and private keys. That
> > > encrypt the other half under the public key of the recipient. This allows
> > > Some applications of that are encumbered (possibly) under a soon to expire
> > > patent.
> > >
> > >
> > >
> > > [email-masked] <mailto:[email-masked]>> wrote:
> > >
> > >> I have just implemented Proxy Re-Encryption under Ed-25519 and Ed448. I
> > >> On Tue, Mar 21, 2017 at 3:42 PM, Tony Arcieri <[email-masked] <mailto:[email-masked]>> wrote:
> > >>
> > >>> their next-generation hidden services design for several years now[1],
> > >>> the cryptocurrency space, where Bitcoin's BIP32[4] provided a means for
> > >>> unlinkable single-use signature keys for the secp256k1 elliptic curve.
> > >>> There are several designs for applying the ideas from BIP32 to Ed25519,
> > >>> The designs in [3], [5], and [6] are all highly similar and accomplish
> > >>> the same goals. Personally I would love to see a single standard design for
> > >>> producing Ed25519 signatures from hierarchically derived keys, notably one
> > >>> which produces signatures that can be verified by any off-the-shelf RFC
> > >>> There's already been some discussion of this on the moderncrypto.org <http://moderncrypto.org/>
> > >>> curves list:
> > >>>
> > >>> https://moderncrypto.org/mail-archive/curves/2017/000858.html <https://moderncrypto.org/mail-archive/curves/2017/000858.html>
> > >>>
> > >>> collaborating on a draft for such a standard, which can be a synthesis of
> > >>> [1]: https://lists.torproject.org/pipermail/tor-dev/2012-Sep <https://lists.torproject.org/pipermail/tor-dev/2012-Sep>
> > >>> tember/004026.html
> > >>> [2]: https://www-users.cs.umn.edu/~hopper/basic-proof.pdf <https://www-users.cs.umn.edu/~hopper/basic-proof.pdf>
> > >>> [3]: https://gitweb.torproject.org/torspec.git/tree/proposal <https://gitweb.torproject.org/torspec.git/tree/proposal>
> > >>> [4]: https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki <https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki>
> > >>> [5]: https://github.com/WebOfTrustInfo/rebooting-the-web-of- <https://github.com/WebOfTrustInfo/rebooting-the-web-of->
> > >>> [6]: https://chain.com/docs/protocol/specifications/chainkd <https://chain.com/docs/protocol/specifications/chainkd>
> > >>>
> > >>> --
> > >>> Tony Arcieri
> > >>>
> > >>> [email-masked] <mailto:[email-masked]>
> > >>> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>
> > >>>
> > >>>
> > >>
> > >
> > > [email-masked] <mailto:[email-masked]>
> > > https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>
> > >
> > >
> >
> >
> > --
> > Best regards,
> > Dmitry Khovratovich
> 
> 
> 
> -- 
> Best regards,
> Dmitry Khovratovich