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

Oleg Andreev <oleganza@gmail.com> Fri, 31 March 2017 18:06 UTC

Return-Path: <oleganza@gmail.com>
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 B5648128DF6 for <cfrg@ietfa.amsl.com>; Fri, 31 Mar 2017 11:06:40 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 sHqw8Kk2xA0W for <cfrg@ietfa.amsl.com>; Fri, 31 Mar 2017 11:06:36 -0700 (PDT)
Received: from mail-pg0-x22e.google.com (mail-pg0-x22e.google.com [IPv6:2607:f8b0:400e:c05::22e]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C40B0129450 for <cfrg@irtf.org>; Fri, 31 Mar 2017 11:06:36 -0700 (PDT)
Received: by mail-pg0-x22e.google.com with SMTP id x125so77970576pgb.0 for <cfrg@irtf.org>; Fri, 31 Mar 2017 11:06:36 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:content-transfer-encoding:mime-version:subject:message-id:date :to; bh=hBysr6SZvg/AX9ey5ZiNJYdRELW1qEMm+VgFTtNM5Fg=; b=eDtPazoBBR5YFDltMmUl96ApWdw5UNsY5XF8PO9Ch4zgLixKxXbtGYYTJ5ne7wzSMw EWU2JKcR5GTjW/Vpzw/wGEyTPwKWXiajGTEJ0698tatzdpx/kzmmEp2Ynrj7U5Iuee7S /6Igfeor9IJWz0//K4hQfowB4Jmqt67osFjlp3kYLOTFnhbe+becv15NQImVP9oI5oaq BvfGNO5ctlFIyOcv663dYCq6aKINwPRopkEyAV5f7SJmmzNsEipt2JlmcRnkw7U8zRPF n2coyiH8u27ICyf7p7n5uyMpz3weWRwWXmixDxLEqUj3P+u9Na1hpqSplpgiEognvrvW Mh/w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:content-transfer-encoding:mime-version :subject:message-id:date:to; bh=hBysr6SZvg/AX9ey5ZiNJYdRELW1qEMm+VgFTtNM5Fg=; b=iIaxr/NzhIgt/TqyXYzsFGDce89v6Tn1x6s64WynEZLNM79qZSdLvcVV3v6tLq3yW/ pr/lNb7LblC+8GHGK/AspwMhEdonW4Qcpf2ENBclhp7fzHEnhQG2NUKQ2r0P3zBh/SfO 4A4J0PD6fD6sat4gf+H3mIhNfAzJYzrWNzyTr4S0KOCKYhg8T3cJMu2zFtbH2L2JOr2t nqmU7EjZpb9tPSIQIbOTqoi3JoAjBnu4WbWi7BwAJFm/OkemSuBOYs8LDifmbzLM2qZw B7q3XrRl73E8zAR5jsW8rGRkM09N1AxCFrcV5uelaSdCmsmWsAbYmIL+XHLTHaEsLsln iZzA==
X-Gm-Message-State: AFeK/H2hQ6tAY+snasqHZQD8kWZwExHNt46aU9deIfVbYIn4EZcxcVanr5kiVj+a4MhRng==
X-Received: by 10.84.208.102 with SMTP id f35mr4863502plh.19.1490983595764; Fri, 31 Mar 2017 11:06:35 -0700 (PDT)
Received: from ?IPv6:2601:642:4000:9d0c:fd08:5b9:6d11:bb3e? ([2601:642:4000:9d0c:fd08:5b9:6d11:bb3e]) by smtp.gmail.com with ESMTPSA id w186sm11874419pgb.35.2017.03.31.11.06.34 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 31 Mar 2017 11:06:35 -0700 (PDT)
From: Oleg Andreev <oleganza@gmail.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
Message-Id: <83CC086B-5B89-41CA-8A20-D7D688DD00AC@gmail.com>
Date: Fri, 31 Mar 2017 11:06:34 -0700
To: cfrg@irtf.org, khovratovich@gmail.com
X-Mailer: Apple Mail (2.3273)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/GD15xVaamO9hg8aRoh_x0ktmVjM>
Subject: [Cfrg] Questions regarding BIP32-Ed25519 (was: 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: Fri, 31 Mar 2017 18:06:41 -0000

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.

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?

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? :)

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.

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