Hybrid signatures have a trap: one valid half is not enough

Strip one signer from a COSE_Sign envelope and the other still verifies. How a post-quantum hybrid (Ed25519 + ML-DSA-65) quietly becomes a single signature, and the two checks that stop it.

Post-quantum migration usually gets sold as "sign with both an old and a new algorithm, so you are safe if either one breaks." That sentence hides a requirement: the verifier has to demand both. Otherwise the hybrid is only as strong as its weakest half, and an attacker gets to pick which half that is.
I ran into this while building Provenza, an open-source, self-hosted governance server for AI agents. It signs its audit checkpoints and its Agent Manifests with Ed25519 and ML-DSA-65 together. This is what I learned about verifying them.

The trap

A COSE_Sign envelope carries a payload and a list of signatures. Each signature covers the payload, not the other signatures. So nothing in the envelope says "there were two signers." Remove the ML-DSA signature and what is left is a perfectly valid envelope with one valid Ed25519 signature.
Here is a verifier that most of us would write on a first pass:

def naive_verify(env):
    # "every signature that is present is valid"
    sigs = env["signatures"]
    return bool(sigs) and all(valid(s["alg"], s["sig"], env["payload"]) for s in sigs)

It does not check what is missing. The fix is to state what must be present:

REQUIRED = {"ed25519", "ml-dsa-65"}

def strict_verify(env):
    ok = {s["alg"] for s in env["signatures"] if valid(s["alg"], s["sig"], env["payload"])}
    return REQUIRED <= ok  # BOTH families must verify, not "something"

Running both against an envelope as issued and the same envelope with the ML-DSA signer removed (real keys from Python's cryptography package):

as issued:      naive = True  strict = True
ML-DSA removed: naive = True  strict = False

The naive verifier accepts the downgraded envelope. If Ed25519 is later broken by a quantum computer, the attacker forges Ed25519, drops the ML-DSA part, and the naive verifier accepts the forgery. The whole point of the hybrid is gone, and no test that only checks "a good envelope passes" will notice.
The reverse also holds: keeping only the ML-DSA signer must fail too. Test both directions. In my verifier the tests are parametrized over "only Ed25519 left" and "only ML-DSA left."

Second line of defense: the signed statement names its own algorithm

A strict verifier protects the people who run it. It does not help a verifier that is someone else's code. So the signed statement itself should say how it was signed.
In Provenza, an audit checkpoint's signed statement binds the algorithm (ed25519+ml-dsa-65) and a key fingerprint, SHA-256(ed25519_public_key || ml_dsa_public_key). If an attacker strips the ML-DSA part, they cannot also change the statement, because the statement is under the signature. A verifier then sees a statement that claims two algorithms, an envelope that carries one, and refuses on the contradiction. The fingerprint also ties the signature to one specific pair of keys, so a swapped key fails too.
Two checks, two different failure modes: the verifier requires both families, and the signed data says both were used.

Where this is used: Agent Manifests

Provenza issues an Agent Manifest (AgenTrust specification v0.2) for every agent it governs: a signed record binding the agent's approved MCP tool catalog and the root of the organization's audit log. It is a hybrid COSE_Sign with an Ed25519 signer and an ML-DSA-65 signer.
The issuer is now listed in AgenTrust's integrations repository, together with a verifier script that checks a manifest offline and refuses an envelope with either signer missing, naming the absent family. You can reproduce it in a minute:

pip install agent-manifest==0.15.0 pytest
python src/verify_provenza_manifest.py tests/agent-1-manifest.cose --keys tests/trusted_keys.json
python -m pytest tests -q

The manifest is deliberately honest about its limits. It is composition-only: Provenza does not observe the system prompt, the model identity or the RAG corpus, so those are declared as unbound, and the SDK's verdict is INCOMPLETE, never VALID. The keys are software keys held by the Provenza server, not hardware-attested. A manifest that claimed more than it could prove would be the same mistake as the naive verifier, one level up.

Takeaways

1. A hybrid signature is a conjunction. Write the verifier as "required set is a subset of verified set," not "all present signatures verify."
2. Test the downgrade. Remove each signer in turn and assert the envelope is refused.
3. Make the signed statement name its algorithms and keys, so a downgrade is a visible contradiction, not a silent success.
4. Say what you do not prove. An INCOMPLETE verdict that is honest beats a VALID that is not.

The code is Apache-2.0 at github.com/kironovlaziz-del/provenza, with a live read-only demo at stickstock.lol. If you verify hybrid signatures somewhere and have never tried removing one signer, now is a good time.