Ed25519 Cofactors, Canonical Encoding, and Strict Verification

Ed25519 signs by computing a scalar from a hash of the private key, multiplying the base point, and then producing a second scalar that ties the message, the public key, and the first scalar together. Verification is a single equation involving two scalar multiplications. That equation is elegant, and its elegance is the source of the problem: it is satisfied by more inputs than the signer would ever produce, and whether an implementation accepts those inputs depends on checks that the original specification left implicit.

The signature equation

Let $B$ be the base point of order $\ell$ on the twisted Edwards curve edwards25519, and let $L$ be that order. The private key is 32 bytes of seed. The public key is $A = aB$, where $a$ is derived from the seed by hashing it and clamping the low and high bits of the result. To sign a message $M$, the signer computes $r = \mathrm{Hash}(\text{prefix} ,|, M)$ for a prefix derived from the same seed hash, then $R = rB$, then $S = (r + \mathrm{Hash}(R ,|, A ,|, M) \cdot a) \bmod L$. The signature is the 32-byte encoding of $R$ followed by the 32-byte little-endian encoding of $S$.

Verification computes $k = \mathrm{Hash}(R ,|, A ,|, M)$ and checks

$$SB = R + kA$$

The equation is checked projectively, without inverting the scalars, and a batch verifier can multiply several equations by random coefficients and check the sum, which amortises the cost across many signatures.

The structure resembles Schnorr, and the security argument is the standard one: a forger who can answer a challenge after seeing the commitment can extract the discrete logarithm by rewinding. The differences from textbook Schnorr are all in the details of what counts as a valid input.

Cofactor four

The curve edwards25519 has order $8\ell$ for a prime $\ell$ slightly below $2^{252}$, so the group of points has a small cofactor of 8. The base point $B$ generates the subgroup of order $\ell$, but the full group contains seven other cosets, including points of order 2, 4, and 8. A point on the curve need not be in the prime-order subgroup.

If a verifier accepts public keys and $R$ values that are not in the prime-order subgroup, the equation can hold for signatures the signer never made. The classical attack uses a small-order point $T$ with $8T = \mathcal{O}$: a malicious signer publishes $A + T$ as a public key, and one signature made with that key becomes valid for another message under the key $A$, because the difference is absorbed by the torsion component. The number of distinct forgeries is bounded by the cofactor, so this is not a catastrophic break, but it violates the requirement that a signature binds one message to one key.

The standard defences are to multiply both sides by the cofactor, checking $8SB = 8R + 8kA$, which kills torsion components, or to reject any encoding that decodes to a point outside the prime-order subgroup. The first is cheap and is what the verification equation in RFC 8032 effectively specifies by checking the equation in the group. The second is stricter and requires a subgroup membership test, which is a scalar multiplication by $\ell$ or an equivalent check.

Canonical encoding of points

A point on edwards25519 is encoded as 32 bytes: the $y$-coordinate in little-endian, with the sign of $x$ in the most significant bit of the last byte. Since the field has $2^{255} - 19$ elements, the top bit of the little-endian encoding is always part of the sign flag rather than a field element, and the encoding is exactly 32 bytes for every valid point.

Two problems follow. First, the encoding is not injective on the set of field elements unless the decoder rejects non-canonical values: the integers from $2^{255}-19$ to $2^{255}-1$ are congruent to small values modulo the field prime, so several 255-bit strings decode to the same $y$. A decoder that reduces modulo $p$ without checking accepts multiple encodings of the same point, which allows a signature to be transformed into a different byte string that also verifies. Second, not every $y$ corresponds to a point; the implied $x$ must satisfy the curve equation, and roughly half of all field elements fail. A decoder that ignores the failure and substitutes a default value is broken in a way that silently accepts garbage.

The same applies to $S$, the second half of the signature. It is a scalar modulo $L$, and the encoding is 32 bytes of little-endian, but $L$ is about $2^{252}$, so the top three bits of the final byte are always zero for a canonical scalar. A non-canonical $S$ that exceeds $L$ can be reduced modulo $L$ to a canonical value, and the signature still verifies; this is a malleability property, as in ECDSA, and a verifier that identifies signatures by their bytes must reject such values or the identity is not well defined.

def decode_canonical(sig: bytes, p=2**255 - 19, L=2**252 + 27742317777372353535851937790883648493):
    R, S = sig[:32], int.from_bytes(sig[32:], "little")
    if S >= L:
        return None  # non-canonical scalar
    y = int.from_bytes(R, "little") & ((1 << 255) - 1)
    if y >= p:
        return None  # non-canonical field element
    return R, S

The function above checks the two ranges and nothing else; a complete decoder also recovers $x$ by computing a square root and rejects if none exists, and it must handle the point with $x = 0$ where the sign bit must be zero.

Why implementations disagreed

The original Ed25519 paper and the reference implementation were written for speed, and the verification they performed checked the equation without the strictness that the analysis required. Several independent libraries then implemented the signature and made different choices about which of these checks to perform, because the specification they were reading did not enumerate them. The result was a set of implementations that were individually reasonable and mutually incompatible in edge cases: a signature accepted by one was rejected by another, and more importantly, some accepted signatures that a strict verifier would call forgeries.

Chalkias, Garillot, and Nikolaenko catalogued this in work on EdDSA variants. The checks that matter are: reject non-canonical encodings of $A$ and $R$; reject $S$ values at or above $L$; ensure the public key is not a small-order point; and either multiply by the cofactor or reject non-prime-order points. The first two are cheap comparisons, the third is a table lookup against a handful of known torsion points, and the fourth is a scalar multiplication or an equivalent test.

RFC 8032 states the verification procedure with cofactored multiplication, which handles torsion for the equation but does not by itself reject non-canonical encodings. The practical rule for a new implementation is to apply all the checks, because the cost is negligible relative to the two scalar multiplications that dominate verification, and because any relaxation creates a difference in the accepted language of the verifier that an attacker can exploit if that language is ever used to make a decision.

The hash and the message

The hash inside the nonce derivation and the challenge is SHA-512, and the construction assumes it behaves like a random oracle. The message is hashed as a byte string with no domain separation and no length prefix, so an application that signs two different structures can have a signature on one reinterpreted as a signature on the other if their byte concatenations coincide. The signature covers $R$, $A$, and $M$ in that order, so the public key is bound into the challenge and a signature cannot be transplanted onto a different key.

The lack of a context string in the original scheme was addressed in later variants, which prepend a domain separator to the message hash so that signatures made for one protocol cannot verify in another. Without that, the defence is at the application layer: prefix each message with a fixed protocol identifier before signing, so that the signed byte string is unambiguous across uses.

The signing key is derived from a seed by hashing and clamping: the low three bits of the first byte are cleared to make the scalar a multiple of the cofactor, the top bit is cleared to keep it below $2^{255}$, and the second-highest bit is set so that the scalar has a fixed bit length. Clamping means the scalar is never uniformly distributed over $[0, L)$, but the distribution is close enough for the security argument, and it removes the need for rejection sampling. Implementing clamping differently from the specification produces a public key that does not match the published one, which is detectable immediately, unlike the verification-side differences that are silent.

The relationship between signing and verification here is a clean illustration of the general problem described in the MAC and signature split: a verification equation defines a language of accepted byte strings, and the security property holds only if that language is exactly the set the signer can produce. For Ed25519 the gap between the two was small but real, and closing it took an explicit list of checks rather than a change to the mathematics. Constructions that aggregate many signatures, such as BLS, face the same question in a different form, where the set of accepted inputs is a pairing equation over a group.