One of the counter-intuitive feats of Ed25519 is that there are signatures matching any given message (or at least, a non-trivial fraction of messages, say, 1/8).
This result doesn’t break Ed25519: the signatures are valid under a specifically generated public key, which cannot be obtained with valid key generation. Still, it looks fascinating.
To obtain “wildcard” signatures, let’s first take the identity point as the public key: A = O.
The verification equation
[s]B = R + [H(R ‖ A ‖ M)]A
loses the second term on the right-hand side; no matter the value of the hash scalar H(R ‖ A ‖ M),
when multiplied by the identity, it yields O. The equation transforms into [s]B = R;
thus, signature ([s]B, s) for any possible scalar s is a valid signature
for any message under public key O.
The identity point has conspicuous serialization 0x0100…00. Not to fear; there are other public keys
that lead to almost the same result. These 8 points form the torsion subgroup
on the Ed25519 elliptic curve Gtors;
for any such point E, [8]E = O. The torsion group is isomorphic to integers modulo 8,
i.e., we can select a group generator E1, such that the group is
Gtors = { O, E1, E2 ≡ [2]E1, …, E7 ≡ [7]E1 }.
For any public key A in Gtors, with probability
at least 1/8 over message space, the hash scalar H([s]B ‖ A ‖ M) is divisible
by the point order (1, 2, 4 or 8). In this case, signature ([s]B, s) will still be valid.
This may take some time.