[Cfrg] Revised ChainKD: BIP32 adaptation to Ed25519

Oleg Andreev <oleganza@gmail.com> Fri, 14 April 2017 23: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 32079129B1E for <cfrg@ietfa.amsl.com>; Fri, 14 Apr 2017 16:06:04 -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 GmsTCt4K51XV for <cfrg@ietfa.amsl.com>; Fri, 14 Apr 2017 16:06:02 -0700 (PDT)
Received: from mail-pg0-x236.google.com (mail-pg0-x236.google.com [IPv6:2607:f8b0:400e:c05::236]) (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 860B3129B19 for <cfrg@irtf.org>; Fri, 14 Apr 2017 16:06:02 -0700 (PDT)
Received: by mail-pg0-x236.google.com with SMTP id 21so48465741pgg.1 for <cfrg@irtf.org>; Fri, 14 Apr 2017 16:06:02 -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=kVK3BZorFgXRRYMCI2NTS6e0Mbt9iNrGhC0Gsi/+Zno=; b=ZhtNjwAvXAIG15RYkraArgPx/U5rSu47c5vYT1Sc5wKQAe5LP6+QfiOavFV0VnCr8H aOE/UxO/7rUdDlfNbBA37nCwzzlY1xz48jCLpJoregpdLIHHF2XKpyWBE7QaI0wwz6SD 8HGnbKMvat30B7+KXI/PTBFCkQEpu7JYseKw6AIg8pb2CrqxFPTTHw/e8FQ2xpTupWI+ WsMjjXCsJJzmdsVGySVugtuaMMYUb5I0Fd7F96G/Eg2JYATJdcSCOS9Dt03ambl1tRqb PwRhzglM20lWOV1zz3JbHPgct5ZaJBjdKS3em1ZkZaD+AeaKBxlwH04w5IgE6HrOFQDV GsYQ==
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=kVK3BZorFgXRRYMCI2NTS6e0Mbt9iNrGhC0Gsi/+Zno=; b=LF2dNQ7Qel0GMK8tOFSDP2bv8YZtADHRVU2XSjmkGRP9003AMNqg9Gnj8/zcyDFeLn 5nzcHXpEZ2sMtQM3VbovE2EqUED8Jf4dykxMVuOZR9rsk22UhFjCsM0c4xRWYJ7+dUta iHCpUImv8VRgBH6K7DqdGuqr749z8VcX9Vd78A86gJx08oJCDzzUdoChl8eWYFq3B9yz MvQkf1HkCk6lPE2N9Mk0A6p7OaWCzIYY68D3pV6VtqqeF8BKi/wDsjQNh3J6yn7NyCsO AXahYdt+5dxpglRA93j0O5qrUMnMR3FYT98O0YhccvpMpXbs1bitaDzhshG1z9W6N23T RM0A==
X-Gm-Message-State: AN3rC/7buhclUWXSBRFRjJI9Ek1iCaQ6vMt2Tne4ImyDk7F4OHf4hc4O qdqLVGkR35yWvB/aMSg=
X-Received: by 10.84.225.129 with SMTP id u1mr11655749plj.123.1492211161321; Fri, 14 Apr 2017 16:06:01 -0700 (PDT)
Received: from [192.168.1.126] ([52.119.113.96]) by smtp.gmail.com with ESMTPSA id k88sm5004701pfj.79.2017.04.14.16.06.00 for <cfrg@irtf.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 14 Apr 2017 16:06:00 -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: <BE88C4B5-1A9D-4761-96A5-E8580FE0A3FF@gmail.com>
Date: Fri, 14 Apr 2017 16:05:59 -0700
To: cfrg@irtf.org
X-Mailer: Apple Mail (2.3273)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/qDJKIMRctVvYuZBYBcACLLeS7hM>
Subject: [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: Fri, 14 Apr 2017 23:06:04 -0000

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