Ed25519 Quirks

Now, the fun part begins: attempting to break Ed25519 in various ways. Our first approach is malleability, the ability to create digital signatures without the knowledge of the necessary secret key.

Contrary to a threatening definition, malleability doesn’t break a digital signature scheme. It allows to create new digital signatures for messages already signed by the legitimate message signers, rather than for new messages (which would indeed break signature scheme security). In application to Ed25519, the malleability attack is as follows: given a valid signature (R, s) under the message M and the public key A, produce another signature (R′, s′) != (R, s) such that it would verify for M and A.

Although malleability is not a problem for signing, things can get ugly if a system accepting digitally signed messages assumes that every signature is created by the owner of a respective secret key. For example, the system may identify messages by their cryptographic hash computed from the message together with the signature (as it was the case with Bitcoin before SegWit). In this case, the same message signed by two different signatures will have different hashes and thus will be treated as two separate entities! This was a significant obstacle for implementing chained payments, e.g., for Lightning Network, in Bitcoin pre-SegWit.

Mutating Signature Scalar

Some Ed25519 implementations (generally, older ones) verify that signature scalar s < 2253, rather than comparing it to the subgroup order . The problem is, for most valid scalars s, s + ℓ < 2253 as well; thus, (R, s + ℓ) is considered a valid signature. Since 2ℓ > 2253, using s + 2ℓ, s + 3ℓ, etc. as a scalar component of the signature will always fail.

Newer Ed25519 implementations generally conform to IETF RFC 8032, which requires the strict s < ℓ comparison as a part of verification. Thus, the described malleability vector is not applicable.

Loading interactive parts
This can take come time…

You can plug the message, public key and the new signature into verification form or an external website and check that the new signature is actually valid.

Fiddling with Randomness

It is impossible for an external party to mutate the R part of a signature, as it is included both into the hash scalar and in free form. The owner of the secret key can, however, trivially create as many signatures for the same content as he wishes. Indeed, it’s impossible to tell during signature verification if the point R = [r]B was created properly; rather than producing the scalar r from the secret key and the message, it can be set to any possible scalar.

Loading interactive parts
This can take come time…

If you search for a cryptographic primitive that provides a “unique” analogue of digital signatures, it does exist and is called verifiable random function (VRF); there is a VRF implementation based on Curve25519 as well.