[curves] Handling invalid (unreduced) public keys and signatures in 25519

[Trevor Perrin]

On Wed, Aug 6, 2014 at 3:38 PM, Robert Ransom <rransom.8774 at gmail.com> wrote:
> On 8/6/14, Trevor Perrin <trevp at trevp.net> wrote:
>>
>> The DJB papers specify precise formats for public keys and signatures
>> [3,4].  However, some implementations are tolerant of noncompliant
>> "unreduced" values (treating them as equivalent to the reduced
>> values).
>>
>> That's harmless for interop, as no implementations produce such
>> values, and I believe harmless for security.
>
> *Every* property which can be used to distinguish between two
> implementations or implementation strategies is a security
> vulnerability.

You're concerned about "fingerprinting" of implementations which might
reduce anonymity, e.g. in Tor?  Huh.  That's an unusual concern, but I
guess legitimate.

I was proposing implementations have the option to reject invalid
values OR keep processing via bit-masking then reduction.  If a single
behavior was to be mandated, which would you recommend?

I think I'd prefer the latter, since:
 - It's what most Curve25519 implementations do,
 - I think it's an easier retrofit to code that doesn't currently do
it (just mask a few bits, as opposed to big-integer comparison)
 - It doesn't require an error-handling case in code which may not have one.


> I'm glad someone else is looking at Ed25519 with an eye toward this
> type of flaw, but you seem to have missed the big one there: there is
> a trade-off between allowing fast single-signature verification
> (without decompressing R) and allowing fast batch verification (by
> decompressing R and multiplying it by 8), which each application needs
> to resolve.

I don't follow, does this have some bad interaction with
mask-then-reduce processing?

Trevor