Digital Signatures, in depth: what a signature proves, EUF-CMA, hash-then-sign, choosing a scheme and the protocol mistakes that break them

What a signature proves, and what it does not

A valid signature on m under public key pk proves one thing: someone with access to the matching private key computed a signature over exactly those bytes. Three properties follow. Integrity: a changed message fails verification. Authenticity: only a key holder could have produced it. Public verifiability: anyone with pk can check, which is the difference from a MAC such as HMAC, where the verifier holds the same secret and could have forged the tag itself.

It does not prove when the message was signed, that it is fresh rather than replayed, that the signer understood what they signed, or that the public key belongs to who you think it does. Time comes from trusted timestamps, freshness from nonces or expiry fields inside the signed bytes, and key ownership from certificates, pinning or a transparency log. Non-repudiation is a legal claim layered on top, and it only holds if the private key was never shared or stolen.

Three algorithms and a security game

A signature scheme is three algorithms. KeyGen outputs a key pair (sk, pk). Sign(sk, m) outputs a signature. Verify(pk, m, sig) outputs accept or reject. Correctness means honest signatures always verify. Security is defined by a game.

In the EUF-CMA game (existential unforgeability under chosen-message attack), the attacker gets pk and may ask a signing oracle for signatures on any messages it likes, adaptively. It wins if it outputs a valid signature on any message it never asked about, even a meaningless one. A scheme is EUF-CMA secure if every efficient attacker wins with negligible probability. That is deliberately strong: real attackers often can get signatures on messages of their choosing, for example by submitting documents to a signing service.

SUF-CMA (strong unforgeability) also counts a new signature on an already-signed message as a win. ECDSA is not strongly unforgeable: if (r, s) is valid, so is (r, n - s). That gap does not let anyone sign new messages, but it breaks systems that use the signature bytes as an identifier, which is how transaction malleability hurt early Bitcoin exchanges. Ed25519 with the strict verification rules of RFC 8032, which reject S at or above the group order, is designed to be strongly unforgeable.

Why we sign hashes, and why that is not enough

Public-key operations work on numbers of bounded size, a few hundred to a few thousand bits, and they are slow. So every practical scheme hashes the message first, or hashes it inside the signing algorithm, and signs the digest. The hash must be collision resistant: if an attacker can find m1 and m2 with the same digest, a signature on harmless m1 is also a signature on malicious m2. That is not theoretical. In 2008 researchers used MD5 collisions to obtain a rogue certificate authority certificate from a real CA, and in 2017 the SHAttered attack produced the first practical SHA-1 collision. Use SHA-256 or stronger; see the SHA family in depth for why.

Hashing alone is not a signature encoding. Raw RSA on a hash, sometimes called textbook RSA, is multiplicatively malleable and forgeable. Schemes therefore specify padding or structure: PSS for RSA, the (r, s) equations for ECDSA, and the hash of R, A and M for Ed25519. Use the scheme as specified; never hash and exponentiate yourself.

Worked example: a toy Schnorr signature

Schnorr signatures are the cleanest example, and Ed25519 is a Schnorr signature over an elliptic curve. Here is one in a toy group small enough to check by hand. Take the prime p = 23 and the generator g = 2, which has order q = 11 modulo 23 (2 to the 11th is 2048, and 2048 = 89 x 23 + 1). The private key is x = 7, so the public key is X = 2^7 mod 23 = 13. The hash e = H(R, m) is SHA-256 of the string "R|m" reduced mod 11.

1. Sign m = "pay alice 5". Pick a secret nonce k = 3 and compute R = 2^3 mod 23 = 8. The hash gives e = 7. Then s = k + e x mod q = 3 + 49 = 52 = 8 (mod 11). The signature is (R, s) = (8, 8).
2. Verify: check g^s equals R X^e mod p. Left: 2^8 = 256 = 3 (mod 23). Right: 13^7 mod 23 = 9, and 8 x 9 = 72 = 3 (mod 23). They match, so accept.
3. Tamper: change the message to "pay alice 6". The hash becomes e = 10, the right side becomes 8 x 13^10 = 8 x 16 = 128 = 13 (mod 23), which is not 3, so reject.
4. Reuse the nonce: sign "pay carol 9" with the same k = 3. Now e = 6 and s = 3 + 42 = 1 (mod 11). Anyone holding both signatures computes x = (s1 - s2) / (e1 - e2) = 7 / 1 = 7 mod 11: the private key falls out.

The last step is the most important lesson in signature engineering: in Schnorr, DSA and ECDSA, the nonce is as secret as the key, and a repeated or even slightly biased nonce leaks it. That is how the PlayStation 3 signing key was recovered in 2010. Ed25519 derives the nonce deterministically from the key and message, and RFC 6979 does the same for ECDSA. Real groups are about 2^256 in size, which is what makes guessing x infeasible; in this toy group there are only eleven possible keys.

The schemes in use today

FIPS 186-5 (2023) added EdDSA and dropped DSA for new signatures, so the classical choices are RSA-PSS, ECDSA and EdDSA. Each has its own page here: ECDSA in depth covers the equations and nonce attacks, Ed25519 in depth covers clamping and verification edge cases, and hash-based signatures covers the stateful and stateless post-quantum families. For new designs without legacy constraints, Ed25519 is the default; P-256 ECDSA is the default where FIPS validation or hardware support demands it.

Signing correctly in code

With a maintained library, signing is a few lines. The example uses the Python cryptography package and was run as shown. Note what surrounds the two calls.

from cryptography.exceptions import InvalidSignature
from cryptography.hazmat.primitives.asymmetric import ed25519

# Fixed, versioned, NUL-terminated: a signature for this purpose can never
# be replayed as a signature for another purpose that uses the same key.
CONTEXT = b"acme-release-manifest-v1\x00"

def sign_manifest(sk: ed25519.Ed25519PrivateKey, manifest: bytes) -> bytes:
    return sk.sign(CONTEXT + manifest)          # 64 bytes

def verify_manifest(pk: ed25519.Ed25519PublicKey, manifest: bytes, sig: bytes) -> bool:
    try:
        pk.verify(sig, CONTEXT + manifest)      # raises, never returns False
        return True
    except InvalidSignature:
        return False

sk = ed25519.Ed25519PrivateKey.generate()
manifest = b'{"artifact":"app-1.4.2.tar.gz","sha256":"9f2c..."}'
sig = sign_manifest(sk, manifest)
assert verify_manifest(sk.public_key(), manifest, sig)
assert not verify_manifest(sk.public_key(), manifest.replace(b"1.4.2", b"1.4.3"), sig)

The context prefix provides domain separation. If the same key ever signs two kinds of message, a signature intended as "approve release manifest" must not also parse as "approve key rotation". Better still, use one key per purpose. The manifest is signed as exact bytes and parsed only after verification succeeds; signing a parsed object and re-serialising it at the verifier invites canonicalisation bugs. For ECDSA the equivalent call is sk.sign(data, ec.ECDSA(hashes.SHA256())), which returns a DER encoding, and RSA-PSS takes a padding.PSS(...) object plus the hash.

Protocol failure modes

• Algorithm confusion. If the message says which algorithm to use, an attacker chooses. JSON Web Tokens with "alg": "none" or with HS256 verified using the RSA public key as an HMAC secret have bypassed authentication repeatedly. Pin the algorithm per key on the verifier side, as RFC 8725 recommends.
• Broken verifiers. Java 15 to 18 accepted ECDSA signatures with r = s = 0 for any message (CVE-2022-21449). Lax PKCS#1 v1.5 parsers allowed Bleichenbacher's 2006 forgery for exponent 3 keys. Keep crypto libraries patched and test that invalid signatures are rejected, not only that valid ones pass.
• Signing what the user did not see. A hardware wallet or approval screen that displays a summary while signing different bytes defeats the whole design. Sign the exact bytes that were displayed or derived deterministically from them.
• Canonicalisation. XML signature wrapping attacks moved the signed element and fed the application an unsigned one. Verify, then use only the verified bytes.
• Malleability as identity. Do not use ECDSA signature bytes as a transaction or deduplication ID; hash the message, or enforce low-S normalisation.
• Key substitution. Some schemes let an attacker find a different public key under which an existing signature verifies. Bind the signer's key or key ID into the signed bytes when signatures are attributed to identities.
• Nonce failures. Repeated or biased nonces leak the key, as the toy example shows. Use deterministic nonces or a vetted library, never your own random number code.

Keys in production and the post-quantum transition

The private key is the asset. Generate it inside an HSM or a cloud KMS when the signatures matter for more than a single service, and make signing an audited API call rather than a file on disk. Give each key an identifier carried with the signature, so verifiers can look up the right key and you can rotate without a flag day: publish the new public key, sign with both for a period, then retire the old one. Plan revocation before you need it, with a published list, short-lived certificates or a transparency log that lets you notice signatures you did not make.

Long-lived signatures need a time anchor. A firmware image signed today may be verified in fifteen years, after the key is retired or the algorithm weakened, so record a trusted timestamp and keep the verification policy that applied when it was made.

Post-quantum migration is now an engineering task. A large quantum computer running Shor's algorithm would forge RSA, ECDSA and EdDSA signatures alike. Unlike encryption, there is no harvest-now-decrypt-later risk for signatures, but anything verified long after signing, such as firmware roots of trust and document archives, needs a plan. Start with inventory: where you sign, which algorithms, how big the signature fields are allowed to be. ML-DSA signatures of 2.4 to 4.6 KB will not fit in protocols with tight size limits, and many teams plan hybrid signatures, classical and ML-DSA together, during the transition.

Trade-offs

Choosing comes down to a few questions. If compliance or hardware requires FIPS-validated curves, use ECDSA P-256 with RFC 6979 or a hardware random source. If verification speed dominates and keys are long-lived, RSA-PSS verifies fastest but signs slowly and carries large keys; RSA in depth covers PSS and key sizes. If you control both ends, Ed25519 is simplest and hardest to misuse. If the signatures must survive a quantum adversary, ML-DSA is the general-purpose standard and SLH-DSA the conservative fallback with larger signatures. In every case, the protocol around the call decides whether the system is secure.

What to do next

1. Inventory every place your systems sign or verify: algorithm, library, key location, key ID scheme and how verifiers obtain public keys.
2. Pin algorithms per key on the verifier side and remove any code path where the message selects the algorithm.
3. Add a versioned context prefix, or a separate key, for each purpose a key signs.
4. Move signing keys into an HSM or KMS, and rehearse a rotation and a revocation end to end.
5. Write negative tests: tampered messages, wrong keys, truncated and zero-valued signatures must all be rejected.
6. Measure your largest signature field and test whether ML-DSA-65 sizes fit; start a hybrid-signature prototype where they do.