(too old to reply)
Pelayo Bernedo Azpiri
2016-11-20 20:17:10 UTC
The XEd25519 signature method creates signatures compatible with Ed25519
using X25519 keys. If the sign bit of the public key is negative then the
private scalar used for signing is negated in order to obtain a positive
public key. The Ed25519 specification requires that the private scalars
have bit 254 set and the lower 3 bits cleared. This makes the private
scalar a multiple of the cofactor. Private scalars obtained by negating a
private X25519 key that already includes the bit masking do not conform to
this Ed25519 requirement. From my very limited understanding it seems that
this is not a problem for the single signature verification as defined in
XEd25519. Ed25519 also defines batch signature verification. Batch
verification is 3 times faster than single signature verification (at least
in the ed25519-donna implementation). Therefore there is an incentive for
an Ed25519 implementation to use batch verification whenever applicable.
Given that XEd25519 signatures are compatible with Ed25519, can they be
used with Ed25519 batch verification? What are the security considerations
of not conforming to the bit masking required by Ed25519?

The specification for the XEd25519 verification states that the X25519
public key shall be converted to an Ed25519 public key (the convert_mont
routine). Instead of this conversion, it could mention the direct
decompression from Montgomery u to Edwards as shown in
https://moderncrypto.org/mail-archive/curves/2015/000376.html (also by the
same author as the XEdDSA specification). I have implemented this based on
ed25519-donna and there is no measurable difference in the time required
for verification of signatures using compressed Montgomery or compressed
Edwards points.

XEd25519 signatures are fully compatible with Ed25519 signatures. If the
requirement of Ed25519 compatibility is dropped and the only goal is to be
able to use X25519 keys for signing and verifying, then the computation of
the hash(R || A || M) can be done with the X25519 public key instead of the
Ed25519 public key. This still ties the message to the public key as
explained in
https://www.ietf.org/mail-archive/web/cfrg/current/msg07335.html. Using the
public X25519 key would avoid the need to keep the public Ed25519 key for
signing and would also eliminate the need for caching it. Using the X25519
public key in hash(R || A || M) together with the direct decompression from
Montgomery coordinates would remove all mentions of the Ed25519 public
keys, simplifying key management.

An alternative method for generating signatures with X25519 keys was
proposed in https://moderncrypto.org/mail-archive/curves/2014/000293.html
(by the same author as the XEdDSA specification). In this proposal the sign
bit is stored in the signature. The method is otherwise identical to
Ed25519, except that it allows the attacker to choose the sign bit. In this
proposal all private scalars comply with the bit masking requirements of
Ed25519. How does this scheme compare to XEd25519? It would allow batch
verification but it is not clear to me if allowing an attacker to choose
the sign bit would somehow offer a practical attack.

Trevor Perrin
2016-12-19 05:56:19 UTC
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,

R == sB - hA (cofactorless)
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

On Sun, Nov 20, 2016 at 12:17 PM, Pelayo Bernedo Azpiri
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:

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

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:

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

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
* 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

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.

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

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


[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