[curves] Finalizing XEdDSA

[Brian Smith]

On Wed, Nov 2, 2016 at 1:53 PM, Brian Smith <brian at briansmith.org> wrote:

> I've not bothered to do VXEd25519 yet.


I did spend a little bit of time figuring out what a newbie would have
trouble understanding about VXEd25519 in relation to XEd25519. Below I
reference the XEdDSA nonce calculation in the published draft, not the
proposed modified calculation, just to keep things simpler. The same
applies for the new calculation.

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)?


2. If the answer to #1 is "no," is there any material advantage to
calculating it differently?

Consider the following hand-wavy (and therefore probably wrong) argument.
First, note

    V = aBv
    V = a * hash_to_point(A || M)
    V = a * hash_to_point(public_from_private(a) || M)

When we compute r = hash3(a || V || Z) (mod q), we're already hashing a,
therefore also hashing any function f(a) is redundant. Similarly, hashing
the output of a function f(M) can't give us a larger set than M. Therefore,
computing r the same was as in XEdDSA r = hash3(a || M || Z) is sufficient
and actually at least slightly more secure than calculating hash3(a || V ||
Z), AFAICT. The only obvious advantage to calculating hash3(a || V || Z)
instead of hash3(a || M || Z) is that the length of V will generally be
smaller than the length of M, so less data will be hashed.

Regardless, it would be useful to note the rationale for this design.

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? Put yet another
way, it would be useful to explain how lossy hash_to_point is in the
Elligator 2 summary.

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