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

From: Oleg Andreev <[email-masked]>
Date: Fri, 14 Apr 2017 16:05:59 -0700

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

---

From: Dmitry Khovratovich <[email-masked]>
Date: Wed, 26 Apr 2017 10:03:39 +0200

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 <[email-masked]> wrote:

> [8] Tor prop224 (see KEYBLIND): https://gitweb.torproject.org/
> torspec.git/tree/proposals/224-rend-spec-ng.txt
>
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

-- 
Best regards,
Dmitry Khovratovich