[tor-dev] Interest in collaborating on a standard Ed25519 key blinding scheme?

[Oleg Andreev]

> From: George Kadianakis
> Date: Wed, Apr 12, 2017 at 7:57 AM
> 
> An update:
> 
> After lots of discussions in the Amsterdam Tor meeting, the following
> approach was suggested for cleansing keys of their torsion components
> that is more friendly towards hierarchical key-derivation schemes:
>         https://moderncrypto.org/mail-archive/curves/2017/000866.html
> 
> However, my current intuition is to just not do this for hidden service
> ed25519 blinded keys. Those keys are only used for signing descriptors
> which should be safe to do, and we don't plan to use them for D-H any
> time soon. If we or some crazy app EVER decides to use those ephemeral
> keys for key exchange, we would need to use a special DH function that
> kills the tensor component of keys before using them, as suggested by
> Trevor here: https://moderncrypto.org/mail-archive/curves/2017/000874.html
> 
> Please let me know if you think this is not a good idea!

Thanks for the update, George.

TL;DR: your scheme seems to be just fine for signatures, and even 
torsion-safety issues are not huge issues IMHO. For wide applicability
reasons, I am trying to make our scheme ChainKD [1] to fit as many 
use cases as possible and therefore very interested in Tor's 
requirements and rationale regarding Tor's key blinding proposal.

L;R:

After studying the situation with key derivation schemes for Ed25519, 
my impression is that the central issue is not even safety, but 
compatibility with existing Ed25519 implementations. People who have 
to integrate a key derivation scheme in their protocol are often not 
the same people who write the underlying primitives such as scalar 
multiplication.

This means, that it's safer to be conservative and keep the derivation
scheme as compatible with EdDSA as possible so that assumptions that 
implementors may take by just reading the EdDSA spec without knowing
about key derivation schemes, do not cause compatibility problems.

Since it's not a trivial task to even learn the landscape of problems
around Ed25519 compatibility- and safety-wise, it'd help if we can
figure all of that once, implement and reuse the result w/o having
to go through this again and again. Hence, our interest in standardizing
the scheme that satisfies as many requirements as possible.

<comic relief>
https://xkcd.com/927/
</comic relief>

Following the feedback in BIP32-Ed25519 paper [2], I've updated our
ChainKD [1] scheme to make it safely "compatible" with DH use cases 
(among those is asymmetric encryption such as ECIES). 

In the Design Rationale section [3] I try to describe the issues with
low/high bits and torsion-safe representative and why we choose
to keep those bits as defined in Curve25519 instead of "torsion-safe
representative" and why we use BIP32-style blinding-by-addition instead
of blinding-by-multiplication.

One piece of feedback affecting our proposal is missing, though:
I'd like to ask Tor developers what is the rationale and requirements 
for their key blinding proposal. Specifically, why do you choose to
blind via multiplication instead of addition:

	s' = b*s; P' = b*P         (Tor's proposal)
		
	vs

	s' = s + b; P' = P + b*G   (BIP32, ChainKD)

	
	(G -- base point, 
         P -- pubkey, 
         s -- secret scalar, P = s*G,
         b -- blinding scalar)

I know of a few reasons to use addition over multiplication
(e.g. performance and bit-compatibility with EdDSA), 
but would love to learn if that hurts some protocols.


PS. I've just joined the list and replying to a forwarded message. 
    I apologize if I break the thread.


[1] ChainKD, revised: https://github.com/chain/chain/blob/chainkd-dh/docs/protocol/specifications/chainkd.md
[2] BIP32-Ed25519: https://drive.google.com/open?id=0ByMtMw2hul0EMFJuNnZORDR2NDA
[3] ChainKD rationale: https://github.com/chain/chain/blob/chainkd-dh/docs/protocol/specifications/chainkd.md#design-rationale