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
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 + ℓ < 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
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.