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

Taylor R Campbell <campbell+cfrg@mumble.net> Wed, 22 March 2017 22:17 UTC

Return-Path: <campbell@mumble.net>

X-Original-To: cfrg@ietfa.amsl.com

Delivered-To: cfrg@ietfa.amsl.com

Received: from localhost (localhost [127.0.0.1])
by ietfa.amsl.com (Postfix) with ESMTP id 7A09F128CFF
for <cfrg@ietfa.amsl.com>; Wed, 22 Mar 2017 15:17:03 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -1.902

X-Spam-Level:

X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001,
RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no

Received: from mail.ietf.org ([4.31.198.44])
by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id iZorhvlZfvzk for <cfrg@ietfa.amsl.com>;
Wed, 22 Mar 2017 15:17:01 -0700 (PDT)

Received: from jupiter.mumble.net (jupiter.mumble.net [74.50.56.165])
(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 4EB8F12949F
for <cfrg@irtf.org>; Wed, 22 Mar 2017 15:17:01 -0700 (PDT)

Received: by jupiter.mumble.net (Postfix, from userid 1014)
id C9464605C4; Wed, 22 Mar 2017 22:16:27 +0000 (UTC)

From: Taylor R Campbell <campbell+cfrg@mumble.net>

To: Tony Arcieri <bascule@gmail.com>

CC: cfrg@irtf.org

In-reply-to: <CAHOTMVKHA-yJR1oCyPtUp4-aJVc3dTdyxQHNo4xqnJt0hU6jVQ@mail.gmail.com>
(bascule@gmail.com)

Date: Wed, 22 Mar 2017 22:16:59 +0000

Sender: Taylor R Campbell <campbell@mumble.net>

MIME-Version: 1.0

Content-Type: text/plain; charset=us-ascii

Content-Transfer-Encoding: quoted-printable

Message-Id: <20170322221627.C9464605C4@jupiter.mumble.net>

Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/8iF_5kVxVu3NtTTdUwV0pKMvJLg>

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

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.22

Precedence: list

List-Id: Crypto Forum Research Group <cfrg.irtf.org>

List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>,
<mailto:cfrg-request@irtf.org?subject=unsubscribe>

List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>

List-Post: <mailto:cfrg@irtf.org>

List-Help: <mailto:cfrg-request@irtf.org?subject=help>

List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>,
<mailto:cfrg-request@irtf.org?subject=subscribe>

X-List-Received-Date: Wed, 22 Mar 2017 22:17:03 -0000

> Date: Tue, 21 Mar 2017 12:42:10 -0700 > From: Tony Arcieri <bascule@gmail.com> > > 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. > > [...] > > 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. 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.

- [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Aaron Zauner
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Dmitry Khovratovich
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Nadim Kobeissi
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Taylor R Campbell
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- [Cfrg] A note on how to (pre-)compute a ladder Francisco Rodriguez- Henriquez
- Re: [Cfrg] A note on how to (pre-)compute a ladder Peter Dettman
- Re: [Cfrg] A note on how to (pre-)compute a ladder Peter Dettman
- Re: [Cfrg] A note on how to (pre-)compute a ladder Francisco Rodriguez- Henriquez
- Re: [Cfrg] A note on how to (pre-)compute a ladder Francisco Rodriguez- Henriquez
- [Cfrg] How to (pre-)compute a ladder [revised ver… Francisco Rodriguez- Henriquez
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Mike Hamburg
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Peter Dettman
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Antonio Sanso
- Re: [Cfrg] How to (pre-)compute a ladder [full C … Francisco Rodriguez- Henriquez
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Francisco Rodriguez- Henriquez
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Francisco Rodriguez- Henriquez