Documentation: Confusing statement on signature malleability

[snej]

The documentation on signatures says:

EdDSA signatures are not unique like cryptographic hashes. For any given public key and message, there are many possible valid signatures. Some of them require knowledge of the private key. Others only require knowledge of an existing signature. Observing a valid signature only proves that someone with knowledge of the private key signed the message at some point. Do not rely on any other security property.

I found the boldfaced phrase confusing. At first it sounded like a signature could be modified to act as a signature of a different message, but then I realized that would be a fatal bug. I think what you mean is that, given a valid signature of message X, it's possible for someone without knowledge of the private key to alter some byte(s) of the signature so that it's still a valid signature of X. Is that accurate?

I think I would rephrase this warning as something like:

EdDSA signatures are not unique like cryptographic hashes. For any given public key and message, there are many possible valid signatures. A signature can be modified by someone without knowledge of the private key, while remaining valid. It's therefore not valid to assume that, if two signatures are byte-for-byte different, that they must sign two different messages. Observing a valid signature only proves that someone with knowledge of the private key signed the message at some point. Do not rely on any other security property.

This also begs the question of whether two calls to crypto_sign with the same message and key-pair always produce the same output bytes. I assume they do, but it's not stated. (libSodium's docs do make this guarantee.)

[fscoto]

I think what you mean is that, given a valid signature of message X, it's possible for someone without knowledge of the private key to alter some byte(s) of the signature so that it's still a valid signature of X. Is that accurate?

As far as I know, that is indeed what this is supposed to mean. To the best of my knowledge, this part is about signature malleability, the details of which are fairly boring and involve :math:. Monocypher has had a check against malleability since 24f4be7acc3ec7ff613715a7a97597e587f6d6d8, so in that sense the passage is irrelevant; however, I believe it was kept as a warning about EdDSA in general because Monocypher may be used together in a larger systems with other libraries working with EdDSA. @LoupVaillant, please correct me if I remember wrong.

EdDSA signatures are not unique like cryptographic hashes. For any given public key and message, there are many possible valid signatures. A signature can be modified by someone without knowledge of the private key, while remaining valid. It's therefore not valid to assume that, if two signatures are byte-for-byte different, that they must sign two different messages. Observing a valid signature only proves that someone with knowledge of the private key signed the message at some point. Do not rely on any other security property.

s/It's/It is/ for formality. Otherwise, I don't really have a strong opinion on whether to use your wording or the existing one. @LoupVaillant, thoughts?

This also begs the question of whether two calls to crypto_sign with the same message and key-pair always produce the same output bytes. I assume they do, but it's not stated. (libSodium's docs do make this guarantee.)

Two calls to crypto_sign with the same parameters will result in the same signature, yes; you can break this in the incremental interface if you really want to. I can go into the details here if you want me to, but I suspect you don't care that much.

[LoupVaillant]

The current docs are indeed a bit ambiguous. Before seeing @snej's suggestion, I was thinking of something like this:

Others only require knowledge of an existing signature (of the same message).

Overall, I think I prefer @snej's suggestion. Or I would, if Monocypher didn't prevent signature malleability. Now that it does, we could remove the warning entirely. We should change the paragraph to something like the following:

Signature malleability is the ability of an attacker to produce a valid signature with knowledge of only an existing signature and the public key. Monocypher prevents it by only accepting signatures in canonical form (where the first part of the signature is a number below the order of the curve).

On the other hand, EdDSA signatures are not unique like cryptographic hashes. While the standard procedure, that crypto_sign() follows, is deterministic, someone with the private key can generate arbitrarily many valid, canonical, different signatures of the same message. Because of this, never assume that signatures are unique.

To enact this change however, we must add the relevant Whycheproof test vectors that test signature malleability (if we haven't already). If I recall correctly, they were originally removed because Monocypher, like TweetNaCl, was happily accepting non-canonical signatures. But if we're going to document that it accept them, we need those test vectors so we don't revert back to the old behaviour with a careless implementation change.

We should also add a versioning note stating when Monocypher started to check against malleability. (It did so for performance reasons, and the change wasn't documented, so we'll have to dig back). We don't want a user of an old version of Monocypher read the new manual and assume they can rely on malleability prevention to build their crypto currency or something.

[fscoto]

I've added a PR about the note in the HISTORY section, which I hope will be uncontroversial per se other than possibly the exact wording.

@LoupVaillant

Signature malleability is the ability of an attacker to produce a valid signature with knowledge of only an existing signature and the public key. Monocypher prevents it by only accepting signatures in canonical form (where the first part of the signature is a number below the order of the curve).

On the other hand, EdDSA signatures are not unique like cryptographic hashes. While the standard procedure, that crypto_sign() follows, is deterministic, someone with the private key can generate arbitrarily many valid, canonical, different signatures of the same message. Because of this, never assume that signatures are unique.

I think we can entirely remove “(where the first part of the signature is a number below the order of the curve)”. This only makes sense for people who are already on the other side of understanding elliptic curve cryptography, at which point the issue of malleability feels kind of inherently obvious.

I'd suggest the following (additions and changes marked in bold, removals without replacement with strikethrough):

Signature malleability is the ability of an attacker to produce a valid signature with knowledge of only an existing signature and the public key. That is, given a message, a signature and a public key, an attacker could generate a new signature for the same message that is valid under the same public key. Monocypher prevents signature malleability by only accepting signatures in canonical form (where the first part of the signature is a number below the order of the curve).

On the other hand, EdDSA signatures are not unique like cryptographic hashes. The signing procedure is deterministic by specification and crypto_sign() follows this specification. However, someone with the private key can generate arbitrarily many valid, canonical, different signatures of the same message. Because of this, never assume that signatures are unique.

[LoupVaillant]

Yes, your wording is perfect.

[LoupVaillant]

I've just confirmed the presence of the malleability specific Wycheproof Ed25519 test vectors on tests/gen/vectors/ed_25519_check.

Malleability won't happen ever again. We can document its absence.

[LoupVaillant]

@fscoto, could you issue one last PR for the wording you suggested? I'd do it myself, but you deserve the credit.

[fscoto]

@LoupVaillant Shouldn't we wait for @snej to agree as well? This is a particularly intricate issue and I don't want to steamroll the person who brought it to our attention into a wording that they themselves would still consider too confusing or incomplete.

[LoupVaillant]

Okay, no rush. @snej, what do you think?

[snej]

The new wording sounds great; thank you!