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

[Trevor Perrin]

Hi,

So Watson and others are working on IETF specs for 25519 [1], and I'm
working on a proposal for 25519 in W3C WebCrypto [2].

There's a processing detail everyone should agree on:

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.

However, there should be precise instructions for handling these
values, for a few reasons:
 (1) So interop problems don't arise if some implementor starts
producing noncompliant values based on testing against liberal
implementations
 (2) So the unused bits in the public key and signature can be used
for other things
 (3) So implementors have explicit guidance

I propose unreduced values should be either
 (a) rejected, or
 (b) the unneeded bits should be masked to zero, and the rest of the
value should be reduced

The rationale for (b) is that it matches existing Curve25519
implementations, and some applications may find it easier to keep
processing than generate an error.

I believe existing Ed25519 implementations are more liberal (i.e.
don't mask the high bits or reject unreduced R or S values [5]), so
this is asking them to become stricter.  But I think this makes sense
for reasons 1-3 above.

Below is an attempt to define these rules in RFC 2119 terms:


Curve25519
===========
 * Implementations MUST encode the public key as a value < 2^255-19
 * Implementations MAY reject a received public key if its value is >= 2^255-19
   Otherwise, an invalid public key MUST be handled as follows:
   * Implementations MUST decode the public key as a value < 2^255 (by
ignoring the high bit)
   * Implementations MUST process a public key with value >= 2^255-19
as if the public key was reduced by 2^255-19

Ed25519
========

R
--
 * Implementations MUST encode R as a value < 2^255-19
 * Implementations MAY reject a signature if its R is >= 2^255-19
   Otherwise, an invalid R MUST be handled as follows:
   * Implementations MUST decode R as a value < 2^255 (by ignoring the high bit)
   * Implementations MUST process R with value >= 2^255-19 as if R was
reduced by 2^255-19

S
--
 * Order of main subgroup l = 2^252 + 27742317777372353535851937790883648493
 * Implementations MUST encode S as a value < l
 * Implementations MAY reject an S if its value is >= l
   Otherwise, an invalid S MUST be handled as follows:
   * Implementations MUST decode S as a value < 2^253 (by ignoring the
3 high bits)
   * Implementations MUST process S with value >= l as if S was reduced by l


Thoughts?

Trevor

[1] http://www.ietf.org/mail-archive/web/cfrg/current/msg04809.html
[2] https://www.w3.org/Bugs/Public/show_bug.cgi?id=25839
[3] http://cr.yp.to/ecdh/curve25519-20060209.pdf
[4] http://ed25519.cr.yp.to/ed25519-20110926.pdf
[5] http://crypto.stackexchange.com/questions/14712/non-standard-signature-security-definition-conforming-ed25519-malleability