Ed25519 malleability vs libsodium

[aep]

Hi,

i'm still confused if malleability is a problem or not.

"A signature scheme is malleable if, given a signature σ on a message m, one can efficiently derive a signature σ' on a message m' = T(m) for an allowed transformation T."

The m' = T(m) is where i get lost. If there isn't any additional MAC, doesnt that mean any T is valid and therefor the signature schema is broken?

Even if not, libsodium has added this change

https://github.com/jedisct1/libsodium/issues/125

And as far as i my limited understanding goes this may lead to ed25519-dalek producing signatures rejected by libsodium. Would it be worth following libsodium here, since it's very popular and incompatibilities may be rather unexpected?

[isislovecruft]

Hi @aep!

Thanks for asking about this! So the malleability in question is due to the fact that curve25519 does not have prime order (meaning that the number of points on the curve is not prime). Instead, the order is l * c where l (henceforth written as \ell in order to distinguish it from the number one) is the order of the base point, i.e. \ell = 2^252 + 27742317777372353535851937790883648493 (which is prime) and the cofactor c = 8. The cofactor is the order of a torsion component to each curve point. For visual people, if you imagine a prime-order group as a (very) large cog, then this torsion component would be like a smaller cog, something like this (except that the big cog should have \ell teeth and little cog should only have c teeth):

And then imagine that to produce a point on the curve, it depends on how each cog is (independently) rotated. This means that every time any cryptographic primitive depends upon something being within a prime-order group, there are potentially eight "equal" things in curve25519.

This comes into play w.r.t. signatures in two ways:

1. Public ed25519 keys are points on the extended twisted Edwards form of the curve.
2. ed25519 signatures are of the form (R, s), where R is again a point in extended twisted Edwards format and s is a scalar (for this curve, an integer modulo \ell = 2^252 + 27742317777372353535851937790883648493).

In implementation, scalars are generally not guaranteed to be less than \ell, because they are usually stored as 32-byte arrays or 256 bits (where the top bit is usually coerced to be unset), however that still allows several potential values which are outside the intended bounds. With curve25519-dalek, it's generally impossible for a user to create a scalar outside the bounds, unless you purposefully (mis)use functions, such as the curve25519_dalek::scalar::Scalar::from_bits() function, which are specifically meant for dealing with wonky legacy code.

The above two things produce the following potentials for malleability, respectively:

1. The public key, being a point, is not guaranteed to not have a small torsion component (i.e. the little cog being turned to a tooth not equal to whichever one is labelled 1).
2. a. The same as (1), but for the R portion of the signature. b. The scalars in most libraries are malleable, as described above, because additional factors of \ell can fit into the (standard) allotment of 255 bits.

That code has since been removed from libsodium, presumably because it breaks compatibility with legacy (read: "reference, not implemented by people in industry") implementations, the original paper, and its subsequent specification. (An interesting thing of note is that some ed25519 libraries included the check for batch signature verification and not for single signature verification, and vice versa, which produced differences in which libraries said which things were valid in which context.)

Finally, to answer your question, to my knowledge it should not be possible to produce a signature with ed25519-dalek which will be rejected by libsodium. However, (I'm not entirely 100% certain, so perhaps @jedisct1 would be kind enough to comment) but I believe it might be possible to handcraft a signature which will be rejected by ed25519-dalek which would be accepted by libsodium (a malicious case of 2b above), but I've not looked into libsodium's treatment of scalars in the last year or so.

[aep]

Wow thank you so much for this long and thorough explanation. Maybe it should be added in the README for everyone to see?

I still lack the background to understand why this is a problem in the first place. If all that an adversary could do is find a different valid signature for the same content, then why is there so much discussion about it?

I would be really grateful if you could explain (in the readme too, not just for me) in which cases malleability is actually an issue. One thing I could image is if someone used the signature as a message id.

[jedisct1]

The check was re-added shortly after (ge25519_is_canonical()), and RFC 8032 that stands as the current specification, requires it.

[isislovecruft]

Hi @jedisct1!

The check was re-added shortly after (ge25519_is_canonical()), and RFC 8032 that stands as the current specification, requires it.

Did you mean the check that s < \ell mentioned in §8.4 of RFC8032, or the check to multiply by the cofactor in §5.1.7? In the latter I still see:

Check the group equation [8][S]B = [8]R + [8][k]A'. It's sufficient, but not required, to instead check [S]B = R + [k]A'.

[jedisct1]

@isislovecruft The check that s< \ell.

[daira]

This issue is clearly a design flaw in Ed25519/EdDSA. I can't imagine any good reason to have a signature scheme that is underspecified to the extent that there are signatures for which the spec doesn't say whether they should pass or fail verification. (Well, perhaps if there were a significant performance impact, but there isn't.)

For blockchain consensus, for instance, that's obviously a severe problem. More generally, whenever you have multiple parties verifying signatures (including different pieces of software on behalf of the same user), it introduces complexities that we shouldn't have to think about. Protocol security analysis is hard enough as it is.

This isn't by itself enough to justify changing the definition of existing signature schemes (IMHO). But it should be a design criterion for new signature schemes [insert plug for RedDSA (section 5.4.6 here), or Schnorr-over-Ristretto], and it needs to be considered every time an existing signature scheme that fails this criterion is included in a new protocol.

[daira]

Also note that this criterion isn't quite the same thing as malleability.

You can have a signature scheme for which it is well-specified whether a given signature passes or fails verification, but that is still malleable (meaning that an adversary, in a chosen message attack, can produce a fresh signature on a previously signed message).

You can also have a nonmalleable signature scheme for which there are "nonstandard" signatures (meaning that they're not produced by the specified signing algorithm), for which it is not well-specified whether they pass or fail verification. Nonmalleability here would require that only the private key holder can produce such signatures.

Arguably, both well-specified verification (including for batch verification) and nonmalleability are useful design goals for new signature schemes.

[isislovecruft]

As an update to the forms of malleability:

Signature s < \ell

By default, ed25519-dalek performs this check when deserialising a signature, in Signature::from_bytes() (cf. the check_scalar function). Early implementations (i.e. ed25519-donna, etc.) did not and do not have this check; if you need strict compatibility with those, the check can be disabled via compiling ed25519-dalek with the "legacy_compatibility" feature, which is off by default, however when enabled does the "legacy" behaviour of checking that the most-significant three bits of the scalar are unset (which is identical to what libsodium does when compiled with -DED25519_COMPAT).

Group element malleability

If you need the additional check upon signature verification that the signature R portion and the public key are torsion free, use the verify_strict() function.

Batch verification

~I am currently investigating whether the group element malleability countermeasures are in fact necessary/useful during batch verification. Given a public key A and signature (R, s) it's not immediately clear to me how one could create A' and (R', s') in a way that would pass verification (at least, not without knowing the private key), particularly using the slightly stronger batch verification formula which uses a randomised system of linear equations?~

(EDIT [five minutes later]): Stupid question. I now have test code demonstrating that a malicious signature, created from a legitimate signature, by adding torsion components to R and A produce a signature which falsely satisfies the verification equation.

[thaidn]

(EDIT [five minutes later]): Stupid question. I now have test code demonstrating that a malicious signature, created from a legitimate signature, by adding torsion components to R and A produce a signature which falsely satisfies the verification equation.

Hi Isis,

I spent half a day looking at this, but I failed to see how this is possible. A signature (s, R) on a public key A and message M is considered valid as long as

[8][s]B = [8]R + [8][h]A, where h = SHA-512(R, A, M)

If either R or A is modified, h would change unpredictably.

Did I miss anything?

[thaidn]

Just out of curiosity, I took a closer look at the verify_strict() function.

Unlike the verify function verify_strict checks that R (and -A) does not have small order. I'm not sure how this check can help prevent the malleability issue. If R = P + Q where P has larger order and Q has small order, R has larger order.

Also, it seems that all verify functions:

• verify that [s]B = R + [h]A, where h = SHA-512(R, A, M)
• do not check that 0 <= s < L

This seems contradicted by what is claimed in the documentation.

FWIW, Tink verifies that 0 <= s < L, and [s]B = R + [h]A. We don't multiply by the co-factor. This is conformant to RFC8032 which requires that R and A are selected from the subgroup generated by B, making the multiplication by 8 moot.

Thoughts?

Edit: typos

[andreacerulli]

Hi @isislovecruft, thanks for including the malleability check to the library! I have some comments regarding the forms of malleability, mostly concerning the documentation.

The malleability check seems to happen on deserialization of the signature and not in the verify methods. As already pointed out by @thaidn, this seems to contradict the documentation, which states

All verify_*() functions within ed25519-dalek perform this check.

Regarding "point malleability":

• Since R is included in the hash of the signature, I do not see how point malleability could help producing a new accepting signature. As @daira was saying above, I think this has to do more with what signatures should be considered valid rather than making signatures malleable. My impression is that this is a less critical issue than malleability. Do you have any scenario in mind where this would constitute a problem?

• The documentation seems to suggest that point malleability is checked by using the verification equation without the cofactors:

  Check the group equation [8][S]B = [8]R + [8][k]A. It's sufficient, but not required, to instead check [S]B = R + [k]A.

However this is clearly not sufficient, as it does not guarantee R to be in the prime order subgroup.

• All verify* methods are actually using the verification equation without the cofactor, not just verify_strict. The latter additionally checks that R and A are not in the small subgroup of order 8. This is also not sufficient to guarantee R to be in the prime order subgroup. One way to do this would be to check the torsion-freeness of A (a similar check on R is not required, since the verification equation omits the cofactors).