Subject: [Cfrg] Interest in an "Ed25519-HD" standard?

From: Tony Arcieri <[email-masked]>
Date: Tue, 21 Mar 2017 12:42:10 -0700

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-September/004026.html
[2]: https://www-users.cs.umn.edu/~hopper/basic-proof.pdf
[3]:
https://gitweb.torproject.org/torspec.git/tree/proposals/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/HDKeys-Ed25519.pdf
[6]: https://chain.com/docs/protocol/specifications/chainkd

-- 
Tony Arcieri

---

From: Aaron Zauner <[email-masked]>
Date: Wed, 22 Mar 2017 01:24:27 +0100

Hi,

> On 21 Mar 2017, at 20:42, 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:
> 
> 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.

I feel this is a useful input to CFRG and would be willing to review such a document. I think it's also a good idea if you talk to the original authors of the design documents you've linked to for collaboration.

Aaron

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 21 Mar 2017 20:34:58 -0400

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.
>
> [1]: https://lists.torproject.org/pipermail/tor-dev/2012-
> September/004026.html
> [3]: https://gitweb.torproject.org/torspec.git/
> tree/proposals/224-rend-spec-ng.txt#n1979
> [5]: https://github.com/WebOfTrustInfo/rebooting-the-
> web-of-trust-fall2016/blob/master/topics-and-advance-
> readings/HDKeys-Ed25519.pdf
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 22 Mar 2017 00:00:43 -0400

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:

> Or we could do it on the Montgomery Curves and give the algorithm for
> point addition.
>
>> 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.
>>
>> 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
>> 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
>> [3]: https://gitweb.torproject.org/torspec.git/tree/
>> proposals/224-rend-spec-ng.txt#n1979
>> [5]: https://github.com/WebOfTrustInfo/rebooting-the-web-of-
>> trust-fall2016/blob/master/topics-and-advance-readings/HDKeys-Ed25519.pdf

---

From: Dmitry Khovratovich <[email-masked]>
Date: Wed, 22 Mar 2017 12:25:39 +0100

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]

> In fact that isn't really using any EC relevant operation at all. Perhaps
> I am not understanding the full requirements for the scheme.
>
>
> On Tue, Mar 21, 2017 at 8:34 PM, Phillip Hallam-Baker <
> [email-masked]> wrote:
>
>>> Application of hierarchical key derivation is perhaps most notable in
>>> the cryptocurrency space, where Bitcoin's BIP32[4] provided a means for
>>> [3]: https://gitweb.torproject.org/torspec.git/tree/proposal
>>> s/224-rend-spec-ng.txt#n1979

-- 
Best regards,
Dmitry Khovratovich

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 22 Mar 2017 08:20:31 -0400

One of the things we need is a specification for the crypto API necessary
to support interesting uses of ECDH/DH.

Most implementations do not expose the necessary calls. It would be useful
to guide them.

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 22 Mar 2017 13:47:33 -0700

On Tue, Mar 21, 2017 at 9:00 PM, Phillip Hallam-Baker <[email-masked]

> I am not understanding the full requirements for the scheme.

One of the goals of the scheme is unlinkability: given a set of candidate
keys, some of which are children of the same parent key, and others
randomly generated, an attacker should not be able to do better than chance
in determining which keys in the candidate set have the same parents.

For example, Tor hidden services will be identified by constantly rotating
"epoch keys". To find the "epoch key" for a given hidden service, a user in
possession of the parent public key derives a child key offline from the
parent key. However, it'd be undesirable for someone not in possession of
the parent key to be able to link the child epoch keys together and
enumerate hidden services without knowledge of their parent public keys.

In your scheme, given z=H("example.com"), and a parent key xG, the derived
child key would be (x+z)G. To recover the original parent public key, you
can simply subtract out zG and recover xG. To prevent this from happening
we need to use an operation which is not easily reversible, hence
multiplication

-- 
Tony Arcieri

---

From: Nadim Kobeissi <[email-masked]>
Date: Wed, 22 Mar 2017 22:40:42 +0100

> On Mar 22, 2017, at 9:47 PM, Tony Arcieri <[email-masked]> wrote:
> 
> On Tue, Mar 21, 2017 at 9:00 PM, Phillip Hallam-Baker <[email-masked]> wrote:
> You can do hierarchical key derivation in Montgomery without the need for an add.
> 
> In fact that isn't really using any EC relevant operation at all. Perhaps I am not understanding the full requirements for the scheme.
> 
> One of the goals of the scheme is unlinkability: given a set of candidate keys, some of which are children of the same parent key, and others randomly generated, an attacker should not be able to do better than chance in determining which keys in the candidate set have the same parents.

From a potentially naïve reading of this thread, it sounds like the HKDF construction (the one proposed by Hugo Krawczyk and used by Signal and TLS 1.3, among others) satisfies all of the properties requested by “hierarchical key derivation” systems. Is this right or am I missing something?

Thanks,
Nadim

> 
> For example, Tor hidden services will be identified by constantly rotating "epoch keys". To find the "epoch key" for a given hidden service, a user in possession of the parent public key derives a child key offline from the parent key. However, it'd be undesirable for someone not in possession of the parent key to be able to link the child epoch keys together and enumerate hidden services without knowledge of their parent public keys.
> 
> In your scheme, given z=H("example.com"), and a parent key xG, the derived child key would be (x+z)G. To recover the original parent public key, you can simply subtract out zG and recover xG. To prevent this from happening we need to use an operation which is not easily reversible, hence multiplication
> 
> -- 
> Tony Arcieri

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 22 Mar 2017 14:46:19 -0700

On Wed, Mar 22, 2017 at 2:40 PM, Nadim Kobeissi <[email-masked]>
wrote:

> From a potentially naïve reading of this thread, it sounds like the HKDF
> construction (the one proposed by Hugo Krawczyk and used by Signal and TLS
> 1.3, among others) satisfies all of the properties requested by
> “hierarchical key derivation” systems. Is this right or am I missing
> something?

HKDF is a symmetric construction. This scheme provides hierarchical /
blinded keys for the Ed25519 digital signature algorithm.

Someone holding the master public key for e.g. a Tor hidden service should
be able to calculate the child public keys for each epic from the parent
public key, but should not be able to produce digital signatures under any
key (because they do not know any of the associated scalar values).

-- 
Tony Arcieri

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 22 Mar 2017 17:53:34 -0400

On Wed, Mar 22, 2017 at 4:47 PM, Tony Arcieri <[email-masked]> wrote:

> In your scheme, given z=H("example.com"), and a parent key xG, the
> derived child key would be (x+z)G. To recover the original parent public
> key, you can simply subtract out zG and recover xG. To prevent this from
> happening we need to use an operation which is not easily reversible, hence
> multiplication
>
>
That is the case if you disclose x.G. But why would you do that?

You could also do:

​xs = ( H(x + 'example.com')) mod q

Which is more robust.

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 22 Mar 2017 15:06:24 -0700

On Wed, Mar 22, 2017 at 2:53 PM, Phillip Hallam-Baker <[email-masked]

> That is the case if you disclose x.G. But why would you do that?

xG can be recovered if you know (x+z)G and the "example.com" string, which
is the problem.

xG cannot be recovered if you know (x*z)G and the "example.com" string,
which is the desirable unlinkability property.

> ​xs = ( H(x + 'example.com')) mod q

This requires knowledge of the parent scalar to derive child keys. One of
the goals of a scheme like this is to allow a holder of a master public key
to derive child public keys without any knowledge of secret scalars.

-- 
Tony Arcieri

---

From: Taylor R Campbell <[email-masked]>
Date: Wed, 22 Mar 2017 22:16:59 +0000

> Date: Tue, 21 Mar 2017 12:42:10 -0700
> From: Tony Arcieri <[email-masked]>
> 
> [...]

This sounds like a good idea, because (a) it's mostly straightforward
to invent a scheme in terms of, e.g., EdDSA, that basically works, but
(b) there are some little details that need to be nailed down.

Here's a quick summary for signatures.  First, for reference, standard
signatures have three operations -- keygen, sign, and verify:

   priv, pub <- keygen(seed)
   sig       <- sign(priv, msg)
   ok        <- verify(pub, sig, msg)

Security contract: If seed is uniform random, then:

   Attacker knowing pub with oracle for msg |---> sign(priv, msg)
   can't find sig for which verify(pub, sig, msg) passes if msg not
   given to oracle.

(Maybe attacker can find novel signatures for messages already signed
-- malleability is a story for another day.  Quantifying cost left as
an exercise for the reader.)

Blinded-key signatures, or perhaps `1-level hierarchical signatures',
have five operations, with a natural extension to multi-level schemes:

   priv, pub <- keygen(seed)
   tpriv     <- blindpriv(priv, tweak)
   tpub      <- blindpub(pub, tweak)
   sig       <- sign(tpriv, msg)
   ok        <- verify(tpub, sig, msg)

Security contract: If seed is uniform random, then:

(a) Attacker knowing pub with oracle for (tweak, msg) |--->
    sign(blindpriv(priv, tweak), msg) can't find sig for which
    verify(blindpub(pub, tweak), sig, msg) passes for any (tweak, msg)
    not given to oracle.  (Again, malleability is another story.)

(b) Attacker with oracle for tweak |---> blindpub(pub, tweak) can't
    distinguish tpub from any other tpub' derived from independent
    uniform random seed' for any tweak not given to oracle.

Example of standard signatures: EdDSA on twisted Edwards curve E(F_q)
over (b - 1)-bit prime field F_q with base point B of n-bit order l,
cofactor 2^c (c < n <= b), and 2b-bit hash H, ignoring details of
encoding *except* for the clamp function:

- pub is point A on curve E(F_q);
- sig is (R, s) for point R and integer 0 <= s < l;
- verification equation is 2^c s B = 2^c R + 2^c H(R,A,msg) A;

- priv = seed is opaque b-bit k,
  a = clamp(low b bits of H(k)),
  A = a B,
  r == H(high b bits of H(k), msg) (mod l),
  R = r B,
  s == r + H(R,A,msg) a (mod l);
  thus, s B = r B + H(R,A,msg) a B
            = R + H(R,A,msg) A, as required.

`clamp' maps an integer to the form 2^n + k*2^c for k < 2^(n - c) by
clearing bits above n, setting bit n, and clearing the low c bits.

This is done only so that the private-key-to-public-key map of EdDSA
is equivalent to the corresponding map in, e.g. X25519, which demands
of secret scalars
(a) a fixed position for the high bit, to efficiently evaluate the
Montgomery ladder in constant time, and
(b) a multiple of the cofactor, to avoid revealing residues of the
secret scalar to an attacker who supplies points on a small subgroup.

I emphasize clamp because although it is irrelevant to the security of
EdDSA as far as I know, it is prescribed by standards and performed by
implementations, so we must address it if we want to enable reuse of
existing standard EdDSA code.

Example of a naive blinded-key variant of EdDSA, say B1-EdDSA, which I
am *not* claiming guarantees the security contract but which serves as
an illustration for discussion -- Dmitry's paper goes into much more
detail about existing schemes and their engineering considerations,
and I encourage reading it for anyone who wants more than my quick
summary here:

- pub is point A on curve E(F_q),
- tpub is point A' = t A, where t = clamp(low b bits of H(A, tweak))
- sig is (R, s) for point R and integer 0 <= s < l,
- verification equation is 2^c s B = 2^c R + 2^c H(R,A,A',msg) A',

- priv = seed is opaque b-bit k,
  a = clamp(low b bits of H(k)),
  A = a B,
  tpriv is b-bit scalar a' == t a (mod l) together with A' = t A = t a B,
  r == H(high b bits of H(k), A', msg) (mod l),
  R = r B,
  s == r + H(R,A,A',msg) a' (mod l);
  thus, s B = r B + H(R,A,A',msg) a' B
            = r B + H(R,A,A',msg) t a B
            = R + H(R,A,A',msg) t A
            = R + H(R,A,A',msg) A', as required.

Some convenient properties of this particular construction:

- B1-EdDSA-verify(tpub, sig, msg) = EdDSA-verify(A', sig, A'||msg).

- B1-EdDSA-sign(tpriv, msg) is almost EdDSA-sign with secret scalar a'
  of message A'||msg, except the EdDSA secret key is the seed k, not
  the scalar derived from it -- but EdDSA implementations almost
  certainly have an internal subroutine to compute this nevertheless.

- B1-EdDSA-blindpriv(priv, tweak) == t a (mod l) is multiplication of
  public and secret scalars modulo l, which EdDSA implementations are
  practically guaranteed to already have, perhaps with an additional
  addend (which can just be set to zero).

Some caveats:

- B1-EdDSA-blindpub(pub, tweak) = t A requires multiplication of a
  *possibly secret* curve point A by a public scalar.  I'm not sure
  that EdDSA implementations will necessarily have constant-time
  scalar multiplication of secret curve points, though they probably
  do.

- Some variants I have seen multiply by 2^c (mod l) instead of
  clearing the low c bits.  Other variants clamp (or multiply by 2^c
  (mod l)) only one of the scalars -- a, t, or a' -- so that in
  multi-level hierarchical schemes, different-length paths produced by
  different factorizations of scalars have the same multiplicity of
  the cofactor.  These practical considerations do not -- as far as I
  know -- affect signature security, but they do affect compatibility.

- The security contract did not mention secrecy of the tweak.  Is that
  important for applications?  Not for any I know of, but my knowledge
  is limited.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 22 Mar 2017 21:30:52 -0400

On Wed, Mar 22, 2017 at 6:06 PM, Tony Arcieri <[email-masked]> wrote:

> On Wed, Mar 22, 2017 at 2:53 PM, Phillip Hallam-Baker <
> xG can be recovered if you know (x+z)G and the "example.com" string,
> which is the problem.
>
​Ah, yes, you would want MAC ('example.com', k)

However, g​oing back to

xs = x + ( MAC('example.com', k)) mod q

You could play some interesting games with this. You could have quasi
linkability so that the identifiers are unlikable unless you choose to
claim them be revealing the difference between two of the keys.

I have no idea what you would want to use it for but you could do it.

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 22 Mar 2017 21:59:19 -0700

On Wed, Mar 22, 2017 at 6:30 PM, Phillip Hallam-Baker <[email-masked]

> claim them be revealing the difference between two of the keys.

In an Ed25519-HD scheme, you can demonstrate two keys are linked by
revealing any public key in the hierarchy that links them together.

Since the scheme is hierarchical, you can e.g. create sets of keys you wish
to demonstrate are linked at any level in the hierarchy that you want
without revealing a master/root public key. Instead you can demonstrate
some set of keys at some level of the hierarchy are linked.

-- 
Tony Arcieri

---

From: Francisco Rodriguez- Henriquez <[email-masked]>
Date: Wed, 29 Mar 2017 19:00:40 -0600 (CST)

Dear CFRG community,

We would like to draw your attention to our IACR pre-print entitled,

"A note on how to (pre-)compute a ladder
Improving the performance of X25519 and X448"

https://eprint.iacr.org/2017/264.pdf.

For the point multiplication computation Q = kP, this note describes a 
right-to-left version of the Montgomery ladder, which is amenable for 
pre-computing multiples of the base point P. By requiring very modest 
memory resources and a small implementation effort, it obtains noticeable
performance improvements with respect to the RFC 7748 classical ladder 
procedure.

We stress that our proposal fully complies with the RFC 7748 
specification, in the sense that given any arbitrary secret keys of Alice 
and Bob, our ladder generates exactly the same public keys that an 
implementation of the RFC 7748 would output.

As a way of illustration, in Appendix B of our note, we include a magma 
script, which given Alice and Bob private keys of RFC7748 Sec. 6.2, it 
computes the same public keys as specified in that document.

We would be delighted to receive feedback (including sightings of typos) 
from the CFRG community.

With best regards,

Thomaz Oliveira, Julio López and Francisco Rodríguez-Henríquez

---

From: Peter Dettman <[email-masked]>
Date: Fri, 31 Mar 2017 00:02:11 +0700

Hi Francisco,

Seems like a nice performance win for key generation with very little
extra effort over the variable-point ladder in RFC 7748.

Would it be worth briefly addressing safe-error attacks?

At first glance Algorithm 4 appears to not involve R2 in the final
result, although it's made clear later in Algorithm 5 that both R1 and
R2 are used in every addition due to the choice of addition formula.

Remark 2 at the end of 5.1 presents this as a minor performance
optimization, but fails to point out that it is needed to protect
against safe-error attacks.

Regards,
Pete Dettman

On 30/03/2017 8:00 AM, Francisco Rodriguez- Henriquez wrote:
> specification, in the sense that given any arbitrary secret keys of
> Alice and Bob, our ladder generates exactly the same public keys that an