Ed25519 Quirks

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

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.

Torsion Points

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

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.