[curves] Finalizing XEdDSA

[Trevor Perrin]

On Fri, Nov 4, 2016 at 11:43 PM, Brian Smith <brian at briansmith.org> wrote:
>
> For reference, the first part of VXEd25519 is:
>     A, a = calculate_key_pair(k)
>     Bv = hash_to_point(A || M)
>     V = aBv
>     r = hash3(a || V || Z) (mod q)
>
> 1. Does r really *need* to be calculated differently in VXEdDSA? That is, is
> there a risk of a security failure or that things otherwise stop working if
> it were calculated the same way as XEdDSA, r = hash2(a || M || Z)?

No, but that means hashing the input message three times, instead of
twice.  Avoiding that seemed worthwhile at the time, but you're right
there's a cost:


> 3. To what extent does calculating hash3(a || V || Z) reduce security
> compared to hash3(a || M || Z) when Z is the output of a broken PRNG? In
> other words, how much worse is it to hash V instead of M?

If an attacker can find messages M1 and M2 which are a colliding pair
for hash2, and the RNG repeats, then the private key will probably
leak since M1 and M2 probably won't collide hash4.

VXEdDSA is broken as a VRF if you can collide hash2, because after
seeing VRF(M1) you can predict VRF(M2).  But you still might care
about signature forgery, or the key might be shared with something
else.

So I could see an argument for just hashing the message three times -
it's more consistent with XEdDSA, for typical small messages it's not
a big time difference, and if hashing time does matter the caller
could do their own pre-hashing.


Trevor