[Cfrg] Signature malleability

[Bryan Ford <[e-mail]>]

Hmmm, has the topic of signature malleability been discussed or decided on?  If so, I don’t see evidence of that in the eddsa draft.

The basic issue is whether an attacker can take a valid signature, for which the attacker doesn’t know the private key, and produce a differently-encoded signature (on the same message) that also validates correctly.  Plain, classic Ed25519 signatures are (slightly) malleable, because there are several 32-byte encodings of S values that are equal modulo L (the group order), and the Ed25519 verifier traditionally doesn’t bother to check that S < L in the input signature.  

But the current libsodium implementation of Ed25519, for example, *does* check that S < L and reject signatures for which this doesn’t hold, thereby ensuring that an attacker can’t fiddle with S without invalidating the signature.  While “normal” well-behaved Ed25519 signing implementations as far as I know always produce S < L, libsodium’s added check in principle risks rejecting signatures that in principle might be legitimate according to the Ed25519 standard and that earlier verifiers would have accepted.  This risk is presumably reflected in the “#ifndef ED25519_COMPAT” conditional compilation in the libsodium code.

Signature malleability was a contributor to the security problem of transaction malleability in Bitcoin; see https://en.bitcoin.it/wiki/Transaction_Malleability for example.  Non-malleability is of course not traditionally a formally expected property for signing schemes to have, and the original Ed25519 obviously was not formally “broken” just because it was malleable.  But given that the basic purpose of signatures is to protect from malicious changes to any part of the signed content, it seems like an easy and understandable mistake for people to assume that “non-malleability of signed content” extends to “non-malleability of the signature itself”, or to an expectation of non-malleability of a combined “content + signature” blob.  In retrospect, Bitcoin at least seems to illustrate the reality of that particular pitfall, and I don’t know if there are other relevant historical examples.

A careful reading of the verification text of the current draft seems to *suggest* implicitly that S is supposed to be verified to be < L: for example, section 3.4 “Verify” says:

   To verify a PureEdDSA signature ENC(R) || ENC(S) on a message M under
   a public key ENC(A), proceed as follows.  Parse the inputs so that A
   and R are elements of E, and S is a member of the set {0, 1, ..., L-1
   }. […]

Sections 5.1.7 and 5.2.7 seem to “suggest” this even a bit more clearly:

   1.  To verify a signature on a message M using public key A, first
       split the signature into two 32-octet halves.  Decode the first
       half as a point R, and the second half as an integer S, in the
       range 0 <= s < L.  Decode the public key A as point A'.  If any
       of the decodings fails, the signature is invalid.

A reader who is paying attention sufficiently well perhaps “should” read this as saying the verifier should ensure that s < L, and reject the signature if it is not.

But on the other hand, in the current phrasing a reader could be forgiven for accidentally overlooking this, since it’s still not a completely, explicitly stated as required.  And indeed, I can find no such check in the Python reference code in section 6:

       s = int.from_bytes(signature[32:], "little")
       h = sha512_modq(Rs + public + msg)
       sB = point_mul(s, G)

The draft presumably needs to be clarified one way or another with respect to whether such an S < L check is allowed (MAY), recommended (SHOULD), or required (MUST).  Probably MUST would in principle be best from a conservative security-robustness perspective.  

The caveat is that, as mentioned above, this behavior risks breaking backward compatibility by rejecting signatures that “could in principle” have been generated by old Ed25519 implementations whose signatures would traditionally have been considered acceptable.  So for that reason (and perhaps only that reason?), perhaps a SHOULD would be better, with an explicit statement as to when the SHOULD might be disobeyed (namely “if needed for backward compatibility with old Ed25519 signatures”).

What do you think?
Bryan