[curves] XEd25519

[Trevor Perrin]

Hi Pelayo,

Sorry for the delay, good questions.

Let me tackle the question of batch verification, and whether to do
single-signature verification with or without cofactor multiplication,
i.e.

R == sB - hA    (cofactorless)
or
cR == csB - chA     (cofactor)

This is a hard question, and relevant to Ed25519 and EdDSA as well as XEdDSA.

XEdDSA currently specifies cofactorless verification.  I'm leaning
towards keeping this, for reasons below.  I'd love to hear other
arguments.


On Sun, Nov 20, 2016 at 12:17 PM, Pelayo Bernedo Azpiri
<bernedode at gmail.com> wrote:
> Given
> that XEd25519 signatures are compatible with Ed25519, can they be used with
> Ed25519 batch verification?


XEdDSA signatures could certainly be used with "Fast batch
verification" from [Ed25519].  However, the XEdDSA spec mandates
"cofactorless verification" [EdDSA].  My rationale was to match other
Ed25519 codebases, such as:
 * Ref10 and the other SUPERCOP implementations (ref, amd)
 * Libsodium
 * Tweetnacl
 * Golang
 * BoringSSL
 * LibreSSL
 * Ed25519-donna (though it also contains batch verification)
 * Nettle
 * Signify
 * PGP (libgcrypt and Google's end-to-end)
 * OpenSSH

In fact, the only "implementation" of cofactor verification I've found
is the reference code in Appendix A of the EdDSA [CFRG] draft.

The cofactor vs cofactorless question is relevant to batch
verification because a signer could maliciously construct XEdDSA (and
EdDSA) signatures which might not give the same verification results
with "cofactorless verification" and "fast batch verification".

This could be fixed by changing single-signature verification to
cofactor verification.  In the XEdDSA spec:

OLD:
    h = hash(R || A || M) (mod q)
    Rcheck = sB - hA
    if bytes_equal(R, Rcheck):
        return true

NEW:
    h = hash(R || A || M) (mod q)
    if points_equal(cR, csB - chA):
        return true

VXEdDSA is more complicated because it sends the hash value h, instead
of R and Rv.  You can do Schnorr signatures either way:
 (1)  Send (R, s).  Verifier solves for h = hash(R || A || M)
 (2)  Send (h, s).  Verifier solves for R = sB - hA

Because VXEdDSA has two "R-like" values (R and R_v) it uses (2) to get
a smaller signature (VXEd25519 signatures of 96 bytes versus 128
bytes).  Unfortunately, (2) is incompatible with batch verification,
since (2) requires calculating the full sB - hA to recover R.

Also unfortunately, (2) is incompatible with cofactor verification,
since csB - chA gives cR but we need R to check the hash.  So we can't
just specify cofactor verification for VXEdDSA and allow the same
signature to be represented with either a short (h, s) or a
batch-friendly (R, R_v, s).

If we wanted that flexibility we could change the VXEdDSA hashing to
include cR instead of R (and cR_v instead of R_v).

However, that makes VXEdDSA deviate further from EdDSA.  I'm nervous
about ad hoc cofactor adjustments like this.  Also, I'm interested in
extension to other Schnorr-like zero-knowledge protocols (e.g.
designated verifier signatures, algebraic macs).  Those add other
complications, so the burden of analyzing batch support / cofactor
verification for all these is something I'm happy to abandon.

But that's just one perspective, let's consider others:


Performance
------------
Below is some rough timing of Floodyberry's ed25519-donna batch
verification.  That implementation only uses batch verification for
batch sizes >= 4, presumably because it's slower on smaller batches.

(clang, no optimization, though -O3 didn't change the ratios):

1 = 360K (single-signature verification)

4 = 307K (15% savings)
6 = 265K (26% savings)
8 = 245K (32% savings)
10 = 235K (35% savings)

20 = 198K (45% savings)
40 = 192K (47% savings)
60 = 186K (48% savings)

The numbers at [Ed25519-Donna] show 50-60% savings for 64 signatures,
and the numbers in [Ed25519] show 50% savings for 64 signatures.

I was curious whether batching helps much for verifying a typical
certificate chain, with a small number of signatures.  I think the
answer is no - this only becomes a significant optimization with
larger batch sizes.


Use cases
----------
It's not obvious what use cases are bottlenecked on signature
verification such that batching is applicable and worth the costs of:
 * added latency of waiting for a batch
 * added complexity of the batch verification itself
 * added complexity of handling verification failures by falling back
to individual verification or [badbatch]).

The only real-world attempt at batch verification I'm aware of is Tor.
Tor uses ed25519-donna with batches of a few signatures, but I think
the batches are small enough that it just falls through to
ed25519-donna's cofactorless single-signature verification.

I guess a server supporting multiple clients might be able to batch
the verification of client-auth signatures, but that's only part of
typical handshake computations, so saving 50% of verification compute
time probably saves less than 25% of handshake compute time.  Modern
EC crypto is already fast on servers, so that's a pretty modest
savings.


CFRG
-----
The IETF's [CFRG] group is working on a document for EdDSA.  It takes
various positions on this:
 * In 3.4 EdDSA is defined as using cofactor verification
 * In 5.1.7 and 5.2.7 cofactorless verification is described as being
"sufficient"
 * In 10.8 it explains that the "given verification formulas" use
cofactor verification to prevent batch / non-batch implementations
disagreeing on the "exact set of valid signatures"
 * There is reference code in Section 6 and "the complete
implementation" in Appendix A.  The former uses cofactorless
verification, the latter uses cofactor verification.

I guess it's saying that both choices are OK, but people should prefer
cofactor verification to avoid the potential for implementation
disagreement.

Of course, given that almost all fielded implementations do
*cofactorless* verification, and almost no-one does batch
verification, this advice seems much more likely to cause
implementation disagreement than prevent it.


Adding batching later
----------------------
If XEdDSA mandates cofactorless verification now, does that prevent
batch verification from being used later?  No, for two reasons:

 (1) If implementation variance in accepting weird signatures doesn't
matter, you can always add batch verification.  In many protocols it
won't matter if someone can produce a signature that fails to verify
on some implementations.

 (2) A protocol that anticipates batch verification and implementation
invariance being important can define cofactor verification / batch
verification at that point.  But they'd be doing that work when/if an
actual need arises.


Conclusion
-----------
I think XEdDSA is better off with cofactorless verification because:

 * We want it to be easy to adapt EdDSA codebases for XEdDSA.
Existing implementations overwhelmingly do cofactorless verification.

 * Trying to force existing codebases to transition from cofactorless
-> cofactor is likely to be unsuccessful, as this would require many
Ed25519 [users] to rewrite and redeploy security-critical code for
almost no gain.

 * Trying to force a transition from cofactorless -> cofactor is
likely to be counterproductive to the goal of reducing implementation
variance.

 * Batch verification is not terribly useful, but nothing in XEdDSA
prevents it from being specified later.


Trevor


[Ed25519] https://ed25519.cr.yp.to/ed25519-20110705.pdf
[EdDSA] https://ed25519.cr.yp.to/eddsa-20150704.pdf
[CFRG] https://datatracker.ietf.org/doc/draft-irtf-cfrg-eddsa/?include_text=1
[Decaf] https://eprint.iacr.org/2015/673
[Ed25519-Donna] https://github.com/floodyberry/ed25519-donna
[badbatch] https://cr.yp.to/badbatch/badbatch-20120919.pdf
[users] https://ianix.com/pub/ed25519-deployment.html