tl;dr: the conclusion of the EdDSA part of the article is wrong. EdDSA has its problems, but malleability is not one of them, if one is following RFC 8032.
>There are several ways to sign a document with EdDSA, and produce a valid signature. The three sources of malleability are:
>We can add a multiple of L (the order of the prime subgroup) to s. Recall that B has order L as well, so it will absorb any cofactor. Basically everything happens modulo L, so adding L won't change a thing.
This is prevented in RFC 8032 by checking that 0 <= s < L. Tink [1] does this check, and therefore is malleability free.
>We can sign the same message with a different nonce r. This requires knowledge of the secret key a.
This proves that the signature of a message is not unique -- that is the signer can product multiple signatures -- but I haven't seen anyone calling this a malleability issue. Malleability is about taking a triple (public key, signature message) and tweaking bits to produce another valid triple.
>We can add a low order point to A, and subtract it from R. That way we produce a valid signature, but from a public key nobody vouches for. If the verifier checks the weaker equation, we can add a low order point to just R, and produce a "valid" signature with the same public key.
This is the second time I saw this claim. When I first saw it [2], I thought, wait, this test is missing in Wycheproof [3], but Bleichenbacher does NOT miss anything. That's when I knew it's wrong.
Modifying A or R instantly makes the signature invalid. Using the article's notation, the signature is validated by checking that
B.s.8 == R.8 + A.h.8, where h = SHA-512(R, A, M) and M is the message
Multiplying the cofactor or not doesn't matter, doesn't introduce any weakness, as implied by the article. If R or A is changed, h will change.
> malleability is not one of them, if one is following RFC 8032
This is like claiming Weierstrass curves don't have any problems if you follow the NIST/SECG standards. The whole point of the "SafeCurves" it to be easier to get them right, but you can still get them wrong.
Daniel J. Bernstein et al's original paper (High-Speed High-Security Signatures), didn't feel the need to take as many precautions as RFC 8032. For instance, they didn't care about malleability.
You seem to think they should have. May I ask why?
I'm interested in Thai's response to this question too, as I would be in any comment anyone managed to solicit from him about this topic, but an easy point to make here is that Bernstein was himself involved in RFC 8032, at least as a reviewer and contributor to the process, as you can quickly learn by reading the CFRG mailing list.
Oh, so DJB changed his mind then? Makes sense considering the application of EdDSA beyond signatures (I've heard malleability is a problem with zero-knowledge proofs, but I haven't studied that subject).
> This is prevented in RFC 8032 by checking that 0 <= s < L
It is, but some libraries do not perform this check. Including TweetNaCl if I recall correctly.
> Modifying A or R instantly makes the signature invalid.
I was talking about modifying them together. Here's what I claim:
B.s = R + A.h
B.s = R + A.h + P - P
B.s =(R + P) + (A.h - P)
And now I'm realising this should work with any point, not just low order points. I'll correct this. Anyway, it's a commutative group we're talking about how could this not work?
> Multiplying the cofactor or not doesn't matter
Perhaps I went over this a bit to fast. Recall that for any low order point P, P.8 = zero. Once you accept this fact, the rest follows pretty smoothly:
And now you can see that the weaker equation will give the same result for R and R+P, if P has low order. Not a weakness if we're only doing signatures, but still a source of malleability.
I'll add this explanation in the article, thanks for the feedback.
>It is, but some libraries do not perform this check. Including TweetNaCl if I recall correctly.
I'm not sure why TweetNaCl is even considered a serious crypto library. I guess that it can fit in tweets, but this is an optimization that is at best irrelevant at worst a bad software engineering practice.
Re malleability: instead of just thinking about this issue in an abstract way, I recommend writing an exploit. For example, Tink doesn't check R or A at all, try to see if you can produce a new signature from an existing one by modifying R or A as you said.
> Re malleability: instead of just thinking about this issue in an abstract way, I recommend writing an exploit.
Challenge accepted! Hmm, doesn't work. Let me think a bit more abou— <facepalm>
Of course: I totally forgot that h is a hash of R and A, not just the message. So if I change them in any way, h's main factor will change unpredictably, and the signature will fail. Looks like the only malleability left is `s`, and that has nothing to do with the cofactor. Let's take the whole section down.
Lesson learned: I should test my writings like I test my code.
---
If I may, you should have lead with "If R or A is changed, h will change." I let myself get worked up by your first comment¹, and failed to notice the single most important sentence near the bottom. I ended up having to reach the same conclusion independently. I almost missed my error.
[1]: You didn't address me directly, and you didn't start with my error. Regardless of your intentions, that felt mildly confrontational. Being nicer would have been more effective.
>There are several ways to sign a document with EdDSA, and produce a valid signature. The three sources of malleability are:
>We can add a multiple of L (the order of the prime subgroup) to s. Recall that B has order L as well, so it will absorb any cofactor. Basically everything happens modulo L, so adding L won't change a thing.
This is prevented in RFC 8032 by checking that 0 <= s < L. Tink [1] does this check, and therefore is malleability free.
>We can sign the same message with a different nonce r. This requires knowledge of the secret key a.
This proves that the signature of a message is not unique -- that is the signer can product multiple signatures -- but I haven't seen anyone calling this a malleability issue. Malleability is about taking a triple (public key, signature message) and tweaking bits to produce another valid triple.
>We can add a low order point to A, and subtract it from R. That way we produce a valid signature, but from a public key nobody vouches for. If the verifier checks the weaker equation, we can add a low order point to just R, and produce a "valid" signature with the same public key.
This is the second time I saw this claim. When I first saw it [2], I thought, wait, this test is missing in Wycheproof [3], but Bleichenbacher does NOT miss anything. That's when I knew it's wrong.
Modifying A or R instantly makes the signature invalid. Using the article's notation, the signature is validated by checking that
B.s.8 == R.8 + A.h.8, where h = SHA-512(R, A, M) and M is the message
Multiplying the cofactor or not doesn't matter, doesn't introduce any weakness, as implied by the article. If R or A is changed, h will change.
[1] https://github.com/google/tink
[2] https://github.com/dalek-cryptography/ed25519-dalek/issues/2...
[3] https://github.com/google/wycheproof. Wycheproof has tests for EdDSA malleability, but it only tests if s is not properly range checked.