[prev in list] [next in list] [prev in thread] [next in thread]
List: cfrg
Subject: Re: [Cfrg] Revised ChainKD: BIP32 adaptation to Ed25519
From: Dmitry Khovratovich <khovratovich () gmail ! com>
Date: 2017-04-26 8:03:39
Message-ID: CALW8-7+Lm-=yGPu3mv7pCounMN6tHB7HQLxM+NdOswx-YTiXPA () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
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
[Attachment #5 (text/html)]
<div dir="ltr">Hi Oleg,<div><br></div><div>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 <a href="https://drive.google.com/open?id=0ByMtMw2hul0Ea1pkVkxUYmpSd1k">https://drive.google.com/open?id=0ByMtMw2hul0Ea1pkVkxUYmpSd1k</a> \
and the newest scheme by Oleg is here <a \
href="https://drive.google.com/open?id=0ByMtMw2hul0ERHhlNXhxT1Axa0k">https://drive.google.com/open?id=0ByMtMw2hul0ERHhlNXhxT1Axa0k</a></div><div><br></div><div>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).</div><div><br></div><div>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:</div><div><a \
href="https://drive.google.com/open?id=0ByMtMw2hul0EcGxEUHpaSWFWLUE">https://drive.google.com/open?id=0ByMtMw2hul0EcGxEUHpaSWFWLUE</a></div><div>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. </div><div><br></div><div>I wonder what \
the community thinks of these three \
approaches.</div><div><br></div><div>Dmitry</div></div><div \
class="gmail_extra"><br><div class="gmail_quote">On Sat, Apr 15, 2017 at 1:05 AM, \
Oleg Andreev <span dir="ltr"><<a href="mailto:oleganza@gmail.com" \
target="_blank">oleganza@gmail.com</a>></span> wrote:<br><blockquote \
class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc \
solid;padding-left:1ex">Hello,<br> <br>
I would like to present a revised version ChainKD: a deterministic hierarchical<br>
key derivation scheme for Ed25519 inspired by BIP32 [1]. This a result of ongoing<br>
discussion on CFRG list [2,3], Curves list at <a href="http://moderncrypto.org" \
rel="noreferrer" target="_blank">moderncrypto.org</a> [4,5] and Tor-dev list [6].<br> \
<br> ChainKD is now a concrete proposal, with specification and a working code,<br>
ready to be evaluated as a candidate for becoming an industry standard.<br>
<br>
Specification & rationale:<br>
<a href="https://github.com/chain/chain/blob/chainkd-dh/docs/protocol/specifications/chainkd.md" \
rel="noreferrer" target="_blank">https://github.com/chain/<wbr>chain/blob/chainkd-dh/docs/<wbr>protocol/specifications/<wbr>chainkd.md</a><br>
<br>
Implementation in Go:<br>
<a href="https://github.com/chain/chain/blob/chainkd-dh/crypto/ed25519/chainkd/chainkd.go" \
rel="noreferrer" target="_blank">https://github.com/chain/<wbr>chain/blob/chainkd-dh/crypto/<wbr>ed25519/chainkd/chainkd.go</a><br>
<br>
Pull-request & discussion:<br>
<a href="https://github.com/chain/chain/pull/844/" rel="noreferrer" \
target="_blank">https://github.com/chain/<wbr>chain/pull/844/</a><br> <br>
You will find the description of functionality, rationale and tradeoffs in the \
spec<br> (first link above), here I will only highlight some _differences_ with \
other<br> schemes and proposals:<br>
<br>
ChainKD vs BIP32:<br>
1. BIP32 is defined for curve secp256k1, and fairly easily applied to cofactor=1 \
curves,<br>
while ChainKD is designed specifically for Ed25519 having cofactor 8.<br>
2. Derivation index in BIP32 is a 31-bit integer, in ChainKD it is a binary \
string.<br> 3. BIP32 proposes a serialization format with metadata and checksums, \
ChainKD<br>
delegates it to other specifications and uses raw hex representation.<br>
<br>
ChainKD vs BIP32-Ed25519 (BE for brevity) [7]:<br>
1. Like in BIP32, BE uses 31 integers as derivation indices, ChainKD allows binary \
strings.<br> 2. BE extended private key is 96-byte structure with 3 fields, ChainKD \
is similar to BIP32<br> having 2-field 64-byte structure.<br>
3. BE has a slightly higher child key collision probability due to a slightly \
simpler<br>
bit-clearing rule for the child scalars. ChainKD saves 6 bits. I will note, \
though,<br>
that entropy in all private keys is the same 250 bits in both schemes.<br>
<br>
ChainKD vs Tor proposal 224 [8]:<br>
1. ChainKD, like BIP32 uses scalar addition to derive child scalars, while prop224 \
uses<br> scalar multiplication.<br>
2. Tor's prop224 does not include considerations for hardened derivation (from \
the<br> private key only).<br>
3. Tor's prop224 is not concerned with non-signature usage and does attempt to \
be<br>
compatible with EdDSA [6]. ChainKD strives for compatibility with EdDSA and DH \
uses.<br> 4. Note: I'm still in the process of figuring out Tor's \
requirements to figure out<br>
if the ChainKD satisfies them or not. Result of this investigation may \
affect<br> some aspects of the ChainKD design in the near future.<br>
<br>
Would love to hear more thoughts on this. I imagine there are many more fine \
details<br> and considerations to discuss, including, of course, potential bugs \
and<br> security issues with our design.<br>
<br>
Thank you!<br>
<br>
PS. I would like to thank Tony Arcieri, Dmitry Khovratovich, Jason Law, Gregory \
Maxwell,<br> Pieter Wuille, Henry de Valence, Mike Hamburg, Trevor Perrin, Taylor R. \
Campbell<br> and others for the hugely valuable feedback, suggestions and \
explanations.<br> <br>
[1] BIP32: <a href="https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki" \
rel="noreferrer" target="_blank">https://github.com/bitcoin/<wbr>bips/blob/master/bip-0032.<wbr>mediawiki</a><br>
[2] CFRG thread 1: <a \
href="https://www.ietf.org/mail-archive/web/cfrg/current/msg09077.html" \
rel="noreferrer" target="_blank">https://www.ietf.org/mail-<wbr>archive/web/cfrg/current/<wbr>msg09077.html</a><br>
[3] CFRG thread 2: <a \
href="https://www.ietf.org/mail-archive/web/cfrg/current/msg09110.html" \
rel="noreferrer" target="_blank">https://www.ietf.org/mail-<wbr>archive/web/cfrg/current/<wbr>msg09110.html</a><br>
[4] Curves thread 1: <a \
href="https://moderncrypto.org/mail-archive/curves/2017/000858.html" rel="noreferrer" \
target="_blank">https://moderncrypto.org/mail-<wbr>archive/curves/2017/000858.<wbr>html</a><br>
[5] Curves thread 2: <a \
href="https://moderncrypto.org/mail-archive/curves/2017/000866.html" rel="noreferrer" \
target="_blank">https://moderncrypto.org/mail-<wbr>archive/curves/2017/000866.<wbr>html</a><br>
[6] Tor-dev thread: <a \
href="https://lists.torproject.org/pipermail/tor-dev/2017-April/012204.html" \
rel="noreferrer" target="_blank">https://lists.torproject.org/<wbr>pipermail/tor-dev/2017-April/<wbr>012204.html</a><br>
[7] BIP32-Ed25519: <a \
href="https://drive.google.com/open?id=0ByMtMw2hul0EMFJuNnZORDR2NDA" rel="noreferrer" \
target="_blank">https://drive.google.com/open?<wbr>id=<wbr>0ByMtMw2hul0EMFJuNnZORDR2NDA</a><br>
[8] Tor prop224 (see KEYBLIND): <a \
href="https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.txt" \
rel="noreferrer" target="_blank">https://gitweb.torproject.org/<wbr>torspec.git/tree/proposals/<wbr>224-rend-spec-ng.txt</a><br>
<br>
<br>
<br>
______________________________<wbr>_________________<br>
Cfrg mailing list<br>
<a href="mailto:Cfrg@irtf.org">Cfrg@irtf.org</a><br>
<a href="https://www.irtf.org/mailman/listinfo/cfrg" rel="noreferrer" \
target="_blank">https://www.irtf.org/mailman/<wbr>listinfo/cfrg</a><br> \
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div \
class="gmail_signature" data-smartmail="gmail_signature"><div>Best \
regards,</div><div>Dmitry Khovratovich</div></div> </div>
_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic