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.
Some Ed25519 implementations 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.
This may take some 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.
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.
This may take some 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.