Re: [Cfrg] Revised ChainKD: BIP32 adaptation to Ed25519

Dmitry Khovratovich <khovratovich@gmail.com> Wed, 26 April 2017 08:03 UTC

Return-Path: <khovratovich@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 9E91F131CDA for <cfrg@ietfa.amsl.com>; Wed, 26 Apr 2017 01:03:59 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Level:
X-Spam-Status: No, score=-2.699 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, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-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 FW4pjPM8Gorp for <cfrg@ietfa.amsl.com>; Wed, 26 Apr 2017 01:03:56 -0700 (PDT)
Received: from mail-yw0-x234.google.com (mail-yw0-x234.google.com [IPv6:2607:f8b0:4002:c05::234]) (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 A4409131CD5 for <cfrg@irtf.org>; Wed, 26 Apr 2017 01:03:55 -0700 (PDT)
Received: by mail-yw0-x234.google.com with SMTP id 203so104004485ywe.0 for <cfrg@irtf.org>; Wed, 26 Apr 2017 01:03:55 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=wTFrU8VI2CkM6qeZZwdIsSha4vadxCXth3hyiB5AT+k=; b=aZpGWJatgGBGJbchqIhRtOQnPJ1jT9y23PltavZDTQJsiYCzw7r5+VCJW61wFY5TkD gr1EJz9eUvjkqpBMlX6GSOW2X168owireSXlKgP/RHEXKr4kMR7AQXcJrRDOz7liG+ZU WAVSbC/KUVY42pp/vyYzCUKx4YVZyJCjEL/BzUiAHFay0H5KocqtWfma7m8uskDzHnW+ LTUhzSryoqFqL/W44MOFr2rLrFCB8To/SE4UFjFVTGz1kZYwA9Yo5H1UandFwv2WN1FQ 4bdSvrhLRBKInO19VXoN4FUUpJlZp8u2W3X8mV1XfCFLq9e0DxC0/2GlHRm3vuynMmzz +Jrw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=wTFrU8VI2CkM6qeZZwdIsSha4vadxCXth3hyiB5AT+k=; b=XnuypARkbjRJIZOvR4n0bG+3YRl9OYIzeTy8ygaarn2xbeHtYhTZI8D+fGGCvNLfJR VJz27GcRsj6eJDrleU9iC1sLmEXnvWEJ4eNKYAdFR75ucOHktL3d4CyWEJTFrRRR4dpH /zPSVfpoiSQw0GoSsbGnLY99qzvrCLRF2tbf04MnKJT+GRncdc60kcmwmuOw54Po8p4p lOVGLYW4RXpOt8mZMCfp126Zm2NA3eMwoR7TL9iojIhxZRIaq7iHfv6/tNhlR51ni+uR 7cErHyob2lGBGz0HnPKR3NEx34zb/hFVQiYh5k70SLOPZdA+kgA/U9j1xZGjowth0azc rUuQ==
X-Gm-Message-State: AN3rC/6zo4agMANLZGiGDW8VT5SUNxnpGndoy50eL3I6syfEpUvPlTjX 8YO9J2MBffzHneYw1I8fk0FUELeKTA==
X-Received: by 10.129.157.214 with SMTP id u205mr14027653ywg.12.1493193834849; Wed, 26 Apr 2017 01:03:54 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.83.10.12 with HTTP; Wed, 26 Apr 2017 01:03:39 -0700 (PDT)
In-Reply-To: <BE88C4B5-1A9D-4761-96A5-E8580FE0A3FF@gmail.com>
References: <BE88C4B5-1A9D-4761-96A5-E8580FE0A3FF@gmail.com>
From: Dmitry Khovratovich <khovratovich@gmail.com>
Date: Wed, 26 Apr 2017 10:03:39 +0200
Message-ID: <CALW8-7+Lm-=yGPu3mv7pCounMN6tHB7HQLxM+NdOswx-YTiXPA@mail.gmail.com>
To: Oleg Andreev <oleganza@gmail.com>
Cc: cfrg@irtf.org
Content-Type: multipart/alternative; boundary=94eb2c0bcc3e1b6b82054e0d48f4
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/0QV3qQmOkbzdyqk7zcOt8B1-TEw>
Subject: Re: [Cfrg] Revised ChainKD: BIP32 adaptation to Ed25519
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, 26 Apr 2017 08:04:00 -0000

Hi Oleg,

I have depicted our and yours schemes at the attached pictures, and I
invite the readers to look at them. The scheme by Dmitry is here
https://drive.google.com/open?id=0ByMtMw2hul0Ea1pkVkxUYmpSd1k and the
newest scheme by Oleg is here
https://drive.google.com/open?id=0ByMtMw2hul0ERHhlNXhxT1Axa0k

One may see that the Oleg version does save on space for public/private
keys and for HMAC calls. However, it is more intrusive as it uses HMAC
instead of SHA-512 for the private key derivation and introduces an extra
HMAC call in the signature generation phase thus making it incompatible
with the original EdDSA. (Generally I do not see any reason to use HMAC,
particularly HMAC with a public key, when we just need a keyed hash
function).

I truly believe that it is worth to rely as much as possible on the EdDSA
parts as TCB, thus minimizing the difference. It seems to be possible to
combine both Oleg's approach to compactness and ours to be less intrusive.
Concretely, I suggest deriving the "chain code" directly by hashing the
extended private key:
https://drive.google.com/open?id=0ByMtMw2hul0EcGxEUHpaSWFWLUE
Note that the k_R part enters the hash function exactly in the same way as
it does in the signature generation phase. However,  a collision is
possible only if k_L equals M, which is unlikely (and can be properly upper
bounded) for an attacker who does not know k_L.  A formal security proof
should  handle this case. An alternative could be to use a different hash
function here.

I wonder what the community thinks of these three approaches.

Dmitry

On Sat, Apr 15, 2017 at 1:05 AM, Oleg Andreev <oleganza@gmail.com> wrote:

> Hello,
>
> I would like to present a revised version ChainKD: a deterministic
> hierarchical
> key derivation scheme for Ed25519 inspired by BIP32 [1]. This a result of
> ongoing
> discussion on CFRG list [2,3], Curves list at moderncrypto.org [4,5] and
> Tor-dev list [6].
>
> ChainKD is now a concrete proposal, with specification and a working code,
> ready to be evaluated as a candidate for becoming an industry standard.
>
> Specification & rationale:
> https://github.com/chain/chain/blob/chainkd-dh/docs/
> protocol/specifications/chainkd.md
>
> Implementation in Go:
> https://github.com/chain/chain/blob/chainkd-dh/crypto/
> ed25519/chainkd/chainkd.go
>
> Pull-request & discussion:
> https://github.com/chain/chain/pull/844/
>
> You will find the description of functionality, rationale and tradeoffs in
> the spec
> (first link above), here I will only highlight some _differences_ with
> other
> schemes and proposals:
>
> ChainKD vs BIP32:
> 1. BIP32 is defined for curve secp256k1, and fairly easily applied to
> cofactor=1 curves,
>    while ChainKD is designed specifically for Ed25519 having cofactor 8.
> 2. Derivation index in BIP32 is a 31-bit integer, in ChainKD it is a
> binary string.
> 3. BIP32 proposes a serialization format with metadata and checksums,
> ChainKD
>    delegates it to other specifications and uses raw hex representation.
>
> ChainKD vs BIP32-Ed25519 (BE for brevity) [7]:
> 1. Like in BIP32, BE uses 31 integers as derivation indices, ChainKD
> allows binary strings.
> 2. BE extended private key is 96-byte structure with 3 fields, ChainKD is
> similar to BIP32
>    having 2-field 64-byte structure.
> 3. BE has a slightly higher child key collision probability due to a
> slightly simpler
>    bit-clearing rule for the child scalars. ChainKD saves 6 bits. I will
> note, though,
>    that entropy in all private keys is the same 250 bits in both schemes.
>
> ChainKD vs Tor proposal 224 [8]:
> 1. ChainKD, like BIP32 uses scalar addition to derive child scalars, while
> prop224 uses
>    scalar multiplication.
> 2. Tor's prop224 does not include considerations for hardened derivation
> (from the
>    private key only).
> 3. Tor's prop224 is not concerned with non-signature usage and does
> attempt to be
>    compatible with EdDSA [6]. ChainKD strives for compatibility with EdDSA
> and DH uses.
> 4. Note: I'm still in the process of figuring out Tor's requirements to
> figure out
>    if the ChainKD satisfies them or not. Result of this investigation may
> affect
>    some aspects of the ChainKD design in the near future.
>
> Would love to hear more thoughts on this. I imagine there are many more
> fine details
> and considerations to discuss, including, of course, potential bugs and
> security issues with our design.
>
> Thank you!
>
> PS. I would like to thank Tony Arcieri, Dmitry Khovratovich, Jason Law,
> Gregory Maxwell,
> Pieter Wuille, Henry de Valence, Mike Hamburg, Trevor Perrin, Taylor R.
> Campbell
> and others for the hugely valuable feedback, suggestions and explanations.
>
> [1] BIP32: https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
> [2] CFRG thread 1: https://www.ietf.org/mail-archive/web/cfrg/current/
> msg09077.html
> [3] CFRG thread 2: https://www.ietf.org/mail-archive/web/cfrg/current/
> msg09110.html
> [4] Curves thread 1: https://moderncrypto.org/mail-
> archive/curves/2017/000858.html
> [5] Curves thread 2: https://moderncrypto.org/mail-
> archive/curves/2017/000866.html
> [6] Tor-dev thread: https://lists.torproject.org/
> pipermail/tor-dev/2017-April/012204.html
> [7] BIP32-Ed25519: https://drive.google.com/open?id=
> 0ByMtMw2hul0EMFJuNnZORDR2NDA
> [8] Tor prop224 (see KEYBLIND): https://gitweb.torproject.org/
> torspec.git/tree/proposals/224-rend-spec-ng.txt
>
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>



-- 
Best regards,
Dmitry Khovratovich