[curves] Finalizing XEdDSA

[Trevor Perrin]

https://whispersystems.org/docs/specifications/xeddsa/


Thanks for feedback everyone,

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].

 (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.

(The 448 design would be easier to change later.  We can keep adding
explanatory text.)


One last tweak to consider is clearing the cofactor in verification.
Currently XEdDSA does "cofactorless verification", i.e. it takes a
signature (R, s) and checks R == sB - hA.  We could change it to cR ==
c(sB - hA).  VXEdDSA would be unchanged.

This has no effect on valid signatures, but adding the cofactor
multiplication means signers could create signatures with a few
different values of R for the same s (which has no security relevance,
I think, and does not cause "malleability" because the signer's choice
of R is included in the hash).

Advantages to current "cofactorless" approach:
 - matches existing code like (ref10, libsodium)
 - less code, doesn't need a "point comparison" function (can encode,
then compare)
 - less computation (by tiny amount, 1% or something)

Advantages to changing to "cofactor" approach:
 - Allows batch verification of signatures (I'm told), that can give ~2x speedup
 - Preferred approach in Ed25519 paper, "EdDSA for more curves" paper,
and CFRG draft

I don't consider batch verification that compelling, given existing
code, but if that's the direction new implementations are going, maybe
this should align.

Other opinions?  Any other last-minute tweaks?

Trevor

[1] https://moderncrypto.org/mail-archive/curves/2016/000764.html
[2] https://moderncrypto.org/mail-archive/curves/2016/000773.html