Re: [Cfrg] EdDSA private key restrictions & composability (Re: normative references)

[David McGrew <[e-mail]>]

On 01/15/2014 03:06 PM, Adam Back wrote:
> On Wed, Jan 15, 2014 at 10:02:01AM -0800, Paul Lambert wrote:
>> - unclear guidelines on important security topics
>>    E.g.
>>      ed25519 has restrictions on the secret key structure for ECDH
>>      Does this extend to other curves?
>
> Actually on this narrow topic re Ed25519 curve for EdDSA uses, I noticed
> this also.  I think bit 254 being 1 could be optional so (Curve25519 
> has the
> same private key restrictions for ECDH) so long as constant time 
> montgomery
> addition starts from bit 254 regardless.  And the remaining hard code 
> is the
> lowest 3 bits 000 but that which I presume is precomputed 
> multiplication by
> the cofactor, as seen in the verification relation 8sG=8R+8H(R,Q,m)Q. 
> (Using ECDSA labelling G is base, Q=dG pub key).
>
> The paper seems quite unclear and hard to pick apart and maybe the 
> algorithm
> just a little too much speed hacked. 

That's my impression too.

I think that one of the goals of this work is to follow US patent 
4,995,082 (Schnorr's signature scheme, which includes elliptic curve 
groups in its claims and which is expired).   In that case, it would 
make a lot of sense for a standard based on this work to cite that 
patent explicitly, and follow it closely.   Hopefully the good "speed 
hacks" are consistent with this approach, but I am not yet sure.

David

> The above seems to break
> composability.  Ie derived public keys (Q_i = Q+M(c,i)G) where c is a
> shared-secret, i is a counter; bitcoin uses this for backup and offline
> security reasons.  Similar examples abound: threshold signatures, blind
> signatures; one of the exciting thing to me about seeing EdDSA adopted is
> that it is a Schnorr variant, and Schnorr has much simpler multiparty,
> threshold and even blinding.  ECDSA has no blinding and DSA blinding is a
> monstrosity involving Damgard-Jurik's generalized variant of Paillier 
> as a
> substep!  But some of these things are lost or complicated by the unusual
> private key restrictions, which I think if I'm not mistaken are just 
> related
> to tiny optimizations or otherise redundant defenses against variable 
> time
> execution which can be otherwise restated.
>
> These kind of questions might or might not be in scope for the draft,
> depending on your point of view.  (But anyway if anyone feels like
> expounding on the above, on list or offlist, I would quite practically
> interested :)
>
> Adam
> .
>