[curves] Finalizing XEdDSA

[Brian Smith]

Trevor Perrin <trevp at trevp.net> wrote:

> I plan to make the following tweaks, then freeze the design (at least
> for 25519):
>
>  (1) Check that all integers in signatures are fully reduced (s<q,
> h<q, R.y<p, V.y<p).  This prevents "signature malleability", which
> could be an issue for badly-designed protocols [1].
>

This seems good to me.


> (2) Replace hash_i(a || ... || Z) with hash_i(a || Z || pad || ...)
> for reasons here [2] - mainly a bit more sidechannel resistance, and
> slightly cleaner use of the hash.
>

This seems good to me. I am not convinced that "pad" is needed, and also if
it is needed then should it be random too?

Other opinions?  Any other last-minute tweaks?
>

I still haven't had time to read the paper carefully. But, I have some more
questions. Note that I intentionally avoided reading the prior discussion
on the list (which happened before I subscribed, I think), so that you can
get a newbie's impression of the paper, which I hope is valuable to you.


The motivation for VXEdDSA is unclear. Is the purpose simply to give the
verifier a proof that the EdDSA keypair really was derived from the
X25519/X448 key, that is indistinguishable from random to a third-party
observer? Is it also serving to provide proof-of-possession of the private
key, or any other purpose?


hash_0(x) is reserved for other specifications. But, if hash_0(x) is never
used, then it is clear that Curve25519 and Curve448 are fully domain
separated, right? (The 32nd input byte to the hash function will always be
0xff for Curve448 and never 0xff for Curve25519, for i > 0). Conversely, if
something does use hash_0(x) then will the domain separation actually work?
It seems like, instead of reserving hash_0(x) for other specifications, it
might be better for it to be forbidden from being used?


It seems like the domain separation provided by the hash_i(x) scheme can
only work for curves with differing values of b (curves of different octet
lengths). It may be useful to mention this.


In this paper, should we also consider the EdDSA public key to be a secret
worth protecting?


In VXEdDSA, will the call to hash_to_point change from hash_to_point(A ||
M) to something similar to the proposed change for the first hashing in
XEdDSA? (I guess this may depend on whether the EdDSA public key is
supposed to be secret.)


In VXEdDSA, every use of a hash function is a hash_i(x). But, in XEdDSA,
the first use of the hash function is hash_1(x) but the second use of the
hash function is just hash(x). Why isn't it hash_2(x) instead for the
second hashing?


In XEdDSA and EdDSA, near the end we calculate:

    h = hash(R || A || M).

But in VXEdDSA we calculate:

    h = hash_4(A || V || R || Rv || M).

Why doesn't VXEdDSA use this instead?:

    h = hash_4(V || Rv || R || A || M)

Note that that is equivalent to:

    h = hash(P || R || A || M) where P = 2**b - 1 - i || V || Rv

Note in particular that this would be consistent with EdDSA & XEdDSA with P
= "". Also note that (P || R) fills one block of SHA-512 for Curve25519,
and A || M form the subsequent block(s), and A is the public key. I'm not
sure any of this matters. However, if it is important that it be different
than EdDSA and XEdDSA then the paper should explain why; conversely, if it
isn't important then it would be better to be consistent.


Section 2.4 explains how elliptic curve points are encoded, but it isn't as
precise as the IETF draft. In particular, it isn't clear whether the
coordinates of P must or must not be reduced (mod p) before encoding, but
this is important because the results of point multiplications are hashed.
In the IETF draft for EdDSA, this is clearer because it has a precondition
that 0 <= x, y < p. If the goal is to be aligned with EdDSA then I suggest
defining the encoding rules by reference to the IETF draft for EdDSA.


It would be good to have some test vectors, where RNG outputs are given as
inputs.

Cheers,
Brian
-- 
https://briansmith.org/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161101/6a1f7841/attachment.html>