[curves] Finalizing XEdDSA

[Brian Smith]

Trevor Perrin <trevp at trevp.net> wrote:

> Brian Smith <brian at briansmith.org> wrote:
> > 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.
>

Right.

Also, (X)EdDSA has been argued to secure even if the hash function isn't
fully collision-resistant; hashing V instead of M breaks that as you
describe above. Also, IIUC, hash_to_point is strictly less
collision-resistant than SHA-512 alone, but I'm too lazy to try to figure
out exactly how much less.

I think when you wrote "typical small messages" you meant that the messages
are typically small, in which case I think hashing the message three times
makes the most sense.

Since the VRF functionality fundamentally depends on hash_to_point, it
seems like collision resistance of the hash function and of hash_to_point
are required for the VRF functionality, even if it wouldn't be required for
the security of the signature functionality. I'm not sure what difference
it would make since I don't know much about VRFs.

At the very least, this stuff would be good to mention in the security
considerations.

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