[curves] EdDSA specification

[Gregory Maxwell]

On Sat, Oct 22, 2016 at 1:53 PM, Trevor Perrin <trevp at trevp.net> wrote:
> Existential unforgeability under chosen message attack (EUF-CMA) is
> the usual security goal for signatures.  VXEdDSA adds the VRF
> requirements from the referenced Dodis or Micali papers (VRF output =
> provably unique, and pseudorandom).
>
> "Strong" unforgeability / non-malleability [1] isn't usually that
> important.  See the discussions of malleability in the Ed25519 and
> EdDSA papers [2,3].  That's a non-goal here too - for example, if
> (R,s) is a valid signature the verifier would accept (R,s+q) as well,
> if s+q satisfies the check s < 2^|q|.
>

Failing to specify a non-malleable form has resulted in
vulnerabilities in multiple protocols and systems.

For example, some users of openssl will blacklist certificates by
their hash. But you can take a valid ecdsa signature, change it to
another valid one under the same key, thus change the certificate
hash-- and bypass the blacklist. OpenSSL CVEed their fix for
DER-parser originated signature malleability related to blacklisting,
but still has the ecdsa algebraic one (adding half the order to s to
flip the sign of R).

All things equal it's preferable for cryptographic constructs to not
have surprising features which less cryptographically experienced
system integrators would not expect.

In libsecp256k1's implementation of ECDSA we accept signatures only in
a malleability prohibited form-- and require users to explicitly
normalize the signature themselves via an additional function call if
they wish to be more permissive. This is explained at
https://github.com/bitcoin-core/secp256k1/blob/master/include/secp256k1.h#L399