[curves] Another try at point compression

[Trevor Perrin]

On Wed, Dec 17, 2014 at 8:12 AM, Robert Ransom <rransom.8774 at gmail.com> wrote:
> On 12/14/14, Michael Hamburg <mike at shiftleft.org> wrote:
>> * there is no fingerprinting or splitting attack based on how your signature
>> scheme handles the cofactor;
>
> This is a major benefit -- major enough that I would seriously
> consider using Curve1174 instead of Curve25519 in an anonymity system
> or any privacy system that needs to permit alternative
> implementations, despite the relative lack of implementation
> experience.

I believe your concern is this Ed25519 implementation choice, due to
the cofactor:

"The verifier is permitted to check this stronger equation [doesn't
clear cofactor] However this is not required" (page 7):
http://ed25519.cr.yp.to/ed25519-20110926.pdf

The "stronger" equation is used in "Fast single-signature
verification", and clearing the cofactor is done in "Fast batch
verification".  You've pointed out this choice would distinguish
implementations in an anonymity context (e.g. over Tor).

https://moderncrypto.org/mail-archive/curves/2014/000266.html

This seems easy to avoid by recommending the stronger check in
anonymity systems.  I assume most libraries implement fast
single-signature verification, so already do this.

That means avoiding batch verification in anonymity systems.  I don't
think batch verification matters in practice - the only plausible use
case I can think of is servers handling large volumes of signatures.
However, 25519 is so fast (10K+ ops per second per core) that compute
costs for large services are going to be relatively small, and not
much is gained by a further 2x optimization (client-side optimization
is more important).

Anyways, I still contend that the cofactor is a minor "security
consideration".  Switching to a less-widely-used curve and more
complex encoding to avoid it seems like adding more risk than you're
eliminating.


Trevor