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

Oleg Andreev <oleganza@gmail.com> Wed, 05 April 2017 00:24 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 578FC129453 for <cfrg@ietfa.amsl.com>; Tue, 4 Apr 2017 17:24:38 -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, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, 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 LGrTxFGhOnTs for <cfrg@ietfa.amsl.com>; Tue, 4 Apr 2017 17:24:35 -0700 (PDT)
Received: from mail-pf0-x231.google.com (mail-pf0-x231.google.com [IPv6:2607:f8b0:400e:c00::231]) (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 AE7C5124D6C for <cfrg@irtf.org>; Tue, 4 Apr 2017 17:24:35 -0700 (PDT)
Received: by mail-pf0-x231.google.com with SMTP id s16so25657470pfs.0 for <cfrg@irtf.org>; Tue, 04 Apr 2017 17:24:35 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:message-id:mime-version:subject:date:in-reply-to:cc:to :references; bh=ZVcbDrl0K4G/D9hopYDgB4mRpWLQWCdHjl5FMb4dGXQ=; b=Id7oVOQvaVA1oXsdYKddWJTi/4zae26dJyAqkoLSFMUhVfULOmR47EWgXwVc+TLZCN eJ+m5sRX7hiAmlNPt9PR790ETdYMPMf85wuwC/UFWBgas/QwNh4jO+anJtFWxBPDAktJ k4iNcwWd2FAS33n1PcyhTtUdNQSXV8iBD+ZijAHG+PT4eVsVOPBYZIRIifEg2iX6+2mp UZ9gqhRuYmUQbAotVjhejOELwOLFBb5wEzrw5YAEfpMCDSekfYQl1E+2qJrm65mfPCBo BVfFxnWitESHiUlmAUz76MlI25dPM6rjR1PUbB8f2dwdOH2chUidMkgL1ndlHi3C3+sE gaWQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:message-id:mime-version:subject:date :in-reply-to:cc:to:references; bh=ZVcbDrl0K4G/D9hopYDgB4mRpWLQWCdHjl5FMb4dGXQ=; b=DpyVB5Umu+7SGLfqeKiWtQxPvcHMDiJ9WE12bAcm5y0dTwrDLuINDFUNdQdt/TtRED /6FJJLL6Nsun4Dll2GITfqN/ccnO/oeLBH9R0UBdu0acmB/cfhJP8EfhosZCcSM0BGXe j3pa2wCYDlKhmDgfEqeqjx1Pleq8NWw4z8ycfi+lBpKPrk8h9bfmM7Xgqv+Au+fUatZn e7KHcvDqd1gzGSqxkSs6QsLfRC6EnCIdFR7e56+ScSMTNnZn7UcxACRjZkWxBzNgw1Yx sFETVfDN9vzQ24IhiP82Foeq5+4A5SsHPtBNRzyxr37KVQkq6KWL9EquiQI63urWbmz3 qQIg==
X-Gm-Message-State: AFeK/H2aMiu05lSZPrF9oIvqq1WfO9KwEcvq0l+5yPQw3CGJ92LUma8J1/uUAoqF3pNI9g==
X-Received: by 10.98.58.7 with SMTP id h7mr12965752pfa.27.1491351875199; Tue, 04 Apr 2017 17:24:35 -0700 (PDT)
Received: from [192.168.1.126] ([52.119.113.96]) by smtp.gmail.com with ESMTPSA id t66sm33736552pfk.53.2017.04.04.17.24.33 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 04 Apr 2017 17:24:34 -0700 (PDT)
From: Oleg Andreev <oleganza@gmail.com>
Message-Id: <3544CA01-C73D-462D-A046-C2800D02756C@gmail.com>
Content-Type: multipart/alternative; boundary="Apple-Mail=_FDD7CD70-E5BC-4EAA-91B7-57C0D2EEC161"
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
Date: Tue, 4 Apr 2017 17:24:32 -0700
In-Reply-To: <CALW8-7LZGbw2UcRpFVBnX-C5au81zxb-8+o91ROoXQTtRh62kQ@mail.gmail.com>
Cc: cfrg@irtf.org
To: Dmitry Khovratovich <khovratovich@gmail.com>
References: <83CC086B-5B89-41CA-8A20-D7D688DD00AC@gmail.com> <CALW8-7LZGbw2UcRpFVBnX-C5au81zxb-8+o91ROoXQTtRh62kQ@mail.gmail.com>
X-Mailer: Apple Mail (2.3273)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/XMS0ssym26qUsG3adOOrqB95KLw>
Subject: Re: [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: Wed, 05 Apr 2017 00:24:38 -0000

Thanks for the detailed reply.

> 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.
> 
> Our idea was to reject as few master secrets as possible, so we decided to clear only one extra bit, thus rejecting half of master keys. By setting 6 bits I mean that we set three highest and three lowest bits.

I probably did not phrase my question clearly in the first place. I meant, why don't you reject _none_ of the master secrets by simply setting 6 bits as required? If the third highest bit happen to be not zero, instead of rejecting the master secret, simply set it to zero? What'd be wrong with that?

> 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?
> 
> Apart from clearing one more bit, the idea to take 28 bytes instead of 29 is to cut a 32-bit word, which could simplify some implementations. I agree it is a minor issue.

Oh, it's 32-bit aligned then, I see. Thanks!

>  
> 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? :)
> 
> The use cases we have seen did not require hierarchy deeper than a few dozen levels. I think 2^20 is a safe bound as long as every new level has some real-world meaning (extra wallet, extra connection, etc.), and thus it seems unlikely that this set will be ever exhausted by any user.

I thought along the same lines, but I can imagine an immense scope for bikeshedding around that number (unfortunately). The 2^20 depth seems fine by me, but there are over 9000 opinions waiting to enter that territory and I'd love to figure out a good story defending any particular decision to avoid wasting a lot of time on it :-) 


> 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.
> 
> We just tried to mimic the original BIP32 key derivation as much as possible. I am not sure I entirely understands the rationale behind your manipulation with bytes of private key after you add up the hash output. Also, could you elaborate on the notions of EdDSA public and private keys, which seem to complement public and private keys you derive in the scheme?

The main problem I see is that extended private key in BIP32-Ed25519 paper becomes pretty long - 96 bytes (also not symmetrical with xpub which is 64-byte). It has 32 bytes for the scalar, 32 bytes for the secret "prefix" (from where the nonce is derived) and 32 bytes for the chain code. In EdDSA both the scalar and the "prefix" are derived from a 256-bit secret, so my suggestion is to derive the "prefix" from the scalar, but since the scalar only has 250 bits of entropy, we can throw in extra 6 bits by using a "pepper" byte to be 100% safe :-) In other words, the full 64-byte "private key" as expected by NaCl has shape: <scalar><Hash(scalar || pepper)> so we do not explode the size of xprv to carry additional 32 bytes.
 
I justify that decision by RFC6979 behavior which is effectively doing the same: the source of entropy for the nonce is the signing key (32-byte), not the 32-byte key + some additional secret 32 bytes of entropy. In EdDSA it's the same - both are derived from a master 32-byte buffer (which, of course, we cannot use because of need for linear non-hardened derivation). I'm curious is there a concern regarding such space optimization?