Hi Oleg,

--001a113ea146d92ba0054c54113a--
From nobody Tue Apr 4 17:24:39 2017
Return-Path: thank you for the questions!

-- **
**

On Fri, Mar 3=
1, 2017 at 8:06 PM, Oleg Andreev <oleganza@gmail.com> 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 bi= t 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 se= ems to be the intention all along.

Our =
idea was to reject as few master secrets as possible, so we decided to clea=
r 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.

=C2=A0

We just tried to mimic the original BIP32 key derivation as much as possi=
ble. I am not sure I entirely understands the rationale behind your manipul=
ation with bytes of private key after you add up the hash output. Also, cou=
ld you elaborate on the notions of EdDSA public and private keys, which see=
m to complement public and private keys you derive in the scheme?

2. You choose 2^20 as a max depth level therefore leaving 2^230 bits for th= e 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. H= ave 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 s= ome implementations. I agree it is a minor issue.=C2=A0

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

The use cases we have s=
een 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 (ext=
ra wallet, extra connection, etc.), and thus it seems unlikely that this se=
t will be ever exhausted by any user.

=C2=A0

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 c= hain 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 sch= eme [1] I'm doing that and to stay fully compatible with EdDSA requirem= ent that prefix originally has 256 bits of entropy, add only one secret byt= e ("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.

Best regards,

Dmitry

=C2=
=A0

Thank you!

[1] Updated ChainKD: https://github.com/chain/chain/blob/chainkd-dh/docs/ protoc= ol/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=C2=A0 just before

> the CFRG meeting at the same place next day. It would be great if we c= ome

> up with some proposal to discuss it already there.

>

> The most recent version is

> https://drive.google.com/open?id=3D It has some0ByMtMw2hul0EMFJuNnZORDR2NDA

> 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 <phill@hallambaker.com

> > 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 =3D (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 refe= renced 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 po= ssibly 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 co= mbine two

> > keypairs by simply adding the corresponding public and private ke= ys. 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. Thi= s 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 <

> > phill@hallambaker.com> wrote:

> >

> >> I have just implemented Proxy Re-Encryption under Ed-25519 an= d Ed448. I

> >> think EdCurve Crypto is a good plan.

> >>

> >> Or we could do it on the Montgomery Curves and give the algor= ithm for

> >> point addition.

> >>

> >> On Tue, Mar 21, 2017 at 3:42 PM, Tony Arcieri <bascule@gmail.com> wrote:

> >>

> >>> Hierarchical key derivation (also sometimes described as = "semiprivate

> >>> keys" or "key blinding") is an increasingl= y popular technique for

> >>> generating unlinkable child keys from master public and p= rivate keys.

> >>>

> >>> The Tor Project has been exploring such an approach as th= e basis for

> >>> their next-generation hidden services design for several = years now[1],

> >>> during which time it has received security proofs[2]. The= ir latest

> >>> design[3] allegedly includes feedback from Dan Bernstein.=

> >>>

> >>> Application of hierarchical key derivation is perhaps mos= t notable in

> >>> the cryptocurrency space, where Bitcoin's BIP32[4] pr= ovided a means for

> >>> unlinkable single-use signature keys for the secp256k1 el= liptic curve.

> >>> There are several designs for applying the ideas from BIP= 32 to Ed25519,

> >>> including ones from Evernym[5] and Chain[6] (where I am a= n employee).

> >>>

> >>> The designs in [3], [5], and [6] are all highly similar a= nd accomplish

> >>> the same goals. Personally I would love to see a single s= tandard 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 <= a href=3D"http://moderncrypto.org" rel=3D"noreferrer" target=3D"_blank">mod= erncrypto.org

> >>> curves list:

> >>>

> >>> https://moderncrypto.= org/mail-archive/curves/2017/000858. html

> >>>

> >>> I'd be curious to know if anyone else would be intere= sted in

> >>> collaborating on a draft for such a standard, which can b= e a synthesis of

> >>> the existing work in this space.

> >>>

> >>> [1]: https://lists.torproje= ct.org/pipermail/tor-dev/2012-Sep

> >>> tember/004026.html

> >>> [2]: https://www-users.cs.umn.= edu/~hopper/basic-proof.pdf

> >>> [3]: https://gitweb.torproj= ect.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-readin= gs/ HDKey

> >>> s-Ed25519.pdf

> >>> [6]: https://chain.com/docs/=protocol/specifications/ chainkd

> >>>

> >>> --

> >>> Tony Arcieri

> >>>

> >>> _______________________________________________

> >>> Cfrg mailing list

> >>> Cfrg@irtf.org

> >>> https://www.irtf.org/mailman/listin= fo/cfrg

> >>>

> >>>

> >>

> >

> > _______________________________________________

> > Cfrg mailing list

> > Cfrg@irtf.org

> > https://www.irtf.org/mailman/listinfo/cfrg<= /a>

> >

> >

>

>

> --

> Best regards,

> Dmitry Khovratovich

Be=
st regards,

Dmitry Khovratovich

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?

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.

On 4 Apr 2017, at 02:40, Dmitry = Khovratovich <khovratovich@gmail.com> wrote:Hi Oleg,thank you for the questions!On Fri, = Mar 31, 2017 at 8:06 PM, Oleg Andreev <oleganza@gmail.com> 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=3D It has some0ByMtMw2hul0EMFJuNnZORDR2NDA

> 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 <phill@hallambaker.com

> > 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 =3D (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 <

>= > phill@hallambaker.com> 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 <bascule@gmail.com> 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

> = >>> Cfrg@irtf.org

> >>> https://www.irtf.org/mailman/listinfo/cfrg

> >>>

> >>>

> >>

> >

> > = _______________________________________________

> > Cfrg mailing list

> > Cfrg@irtf.org

> > https://www.irtf.org/mailman/listinfo/cfrg

> >

> = >

>

>

> --

>= Best regards,

> Dmitry Khovratovich--Best regards,Dmitry = Khovratovich

= --Apple-Mail=_10420D0E-E717-49E3-B0E4-CE5E7251C242-- From nobody Wed Apr 5 16:20:30 2017 Return-Path: