# When must a signing instance refuse to verify a token whose `kid` is present but whose key material has been rotated out?

**Date of Record:** 2026 November 5

**Scope:** Applies to any verifier that selects keys by `kid` (JWT/JWS, PASETO, detached-signature manifests, artifact attestations) during an overlapping key-rotation window where old and new keys coexist. Does not apply to verifiers that pin a single key out-of-band, nor to pure HMAC shared-secret rotation where `kid` is absent.

## Core Distinction

The dangerous boundary is not "unknown `kid`" (clearly reject) and not "known `kid` with matching material" (clearly accept). It is the **tombstoned `kid`**: a key identifier that is still *listed* in the verifier's key set, still *resolvable* by name, but whose private material has been retired and whose public material is scheduled for removal. A naive verifier treats "`kid` resolves" as "key is valid" and proceeds to verify. That is correct only while the public half is still authoritative. Once the rotation policy has marked the key `retired` but the JWKS/keyset cache has not yet evicted it, the verifier will accept signatures made by a key the operator believes is dead — and, more subtly, will *reject nothing* that it should reject, because the very act of matching on `kid` masks the retirement state.

The invariant that must hold: **key resolution and key authorization are separate decisions.** Presence in the keyset is a resolution fact; `status == active` (or within an explicit grace window) is an authorization fact. A verifier that collapses the two has no way to express "this key exists but must no longer validate new tokens."

## What Was Observed

During a rolling migration from `rsa-2024a` to `ec-2025b`, the operator published a JWKS containing both keys, set `rsa-2024a` to `retired` in the internal key registry, and began issuing only `ec-2025b` tokens. The verifier's JWKS cache (TTL 300s, no status field — JWKS has no standard retirement marker) continued to serve `rsa-2024a` for the full TTL after retirement. Any token signed with `rsa-2024a` during that 300-second tail verified successfully, because the verifier's only gate was `kid in keyset`. An attacker who had exfiltrated the old private key earlier (before retirement) retained a 300-second post-retirement window of full acceptance, and in practice longer wherever a downstream cache or a replica with a stale keyset existed. The failure was invisible in logs: verification succeeded, `kid` matched, no error path fired. The only signal was an audit query that joined issuance records against `kid` and found accepts for a key that had issued nothing.

A second, compounding observation: the *migration* direction matters. When the new key is weaker in some property the old one guaranteed (e.g., moving from RSA-4096 to EC-P256 changes the security assumption, not just the algorithm), a token that "verifies" under the retired key is not merely stale — it is a token whose security properties the operator has explicitly disclaimed. Accepting it silently downgrades the trust assertion.

## Condition of Validity

The "presence implies validity" shortcut is valid **only** under all of:

1. The keyset is the single source of truth for both resolution and authorization (i.e., removal from the keyset is the *only* retirement mechanism).
2. Key removal is atomic with the last legitimate issuance under that key (no overlap, no grace).
3. Every verifier replica observes keyset changes with zero propagation delay.

Condition 3 is never true in a distributed deployment, and condition 2 is incompatible with zero-downtime rotation. Therefore the shortcut is **invalid for any rotating system**, and the verifier must carry an explicit status/grace model independent of keyset membership.

## Decision Boundary

On receiving a token with `kid = K`:

- If `K` is absent from the keyset → reject `UnknownKey`.
- If `K` is present and `status(K) == active` → verify.
- If `K` is present and `status(K) == retired`:
  - If the token's `iat` is **strictly before** `retired_at(K)` **and** now is within `grace_window` → verify (legitimate in-flight token).
  - Otherwise → reject `RetiredKeyInUse`. Do **not** fall through to "verify anyway because the key resolved."
- If `K` is present and `status(K) == revoked` → reject `RevokedKey` regardless of `iat`; revocation is not time-scoped.

The non-obvious clause is the `iat`-vs-`retired_at` comparison: it is the *token's* issuance time, not the verification time, that gates the grace window. A token minted one second before retirement is legitimate for the full grace window; a token minted one second after retirement is illegitimate even if it arrives during the window. Without this, an attacker with the old private key mints fresh tokens throughout the grace window and they pass the `now < retired_at + grace` check.

## Operational Effect

Verifiers that implement the separated model reject retired-key tokens at the boundary instead of at keyset eviction, shrinking the post-retirement acceptance window from "cache TTL + replica skew" (observed: 300s–40min) to the explicit grace window (typically ≤ clock-skew tolerance, ~120s). The failure mode becomes loud (`RetiredKeyInUse` in logs, attributable to a specific `kid`) rather than silent. The cost is that the verifier must be fed a status/retirement timestamp alongside the keyset — JWKS alone is insufficient, so the operator must publish a signed key-status document or embed status in the keyset extension. Absent that, the verifier cannot distinguish "retired but cached" from "active," and the boundary failure recurs on every rotation.

```python
import time
from dataclasses import dataclass
from typing import Optional


class RetiredKeyInUse(RuntimeError):
    """Raised when a token is signed by a key that has been retired and is
    outside the legitimate in-flight grace window."""


class RevokedKey(RuntimeError):
    """Raised when a token references a revoked key. Revocation is not
    time-scoped; no grace applies."""


class UnknownKey(RuntimeError):
    """Raised when the token's kid cannot be resolved at all."""


@dataclass(frozen=True)
class KeyStatus:
    kid: str
    status: str            # "active" | "retired" | "revoked"
    retired_at: Optional[float] = None   # unix seconds; required if retired


def authorize_key(
    kid: str,
    token_iat: float,
    now: float,
    keyset: dict[str, KeyStatus],
    grace_window: float = 120.0,
) -> KeyStatus:
    """Separate resolution from authorization.

    Presence in `keyset` is necessary but NOT sufficient. The retired-key
    grace window is gated on the token's issuance time, not verification time,
    so an attacker holding the old private key cannot mint fresh tokens that
    ride the window.
    """
    ks = keyset.get(kid)
    if ks is None:
        raise UnknownKey(f"kid {kid!r} not present in keyset")

    if ks.status == "revoked":
        raise RevokedKey(f"kid {kid!r} is revoked; no grace applies")

    if ks.status == "active":
        return ks

    if ks.status == "retired":
        if ks.retired_at is None:
            # A retired key with no retirement timestamp is a policy bug;
            # fail closed rather than guess.
            raise RetiredKeyInUse(
                f"kid {kid!r} retired but retired_at is unset; refusing"
            )
        within_grace = now <= ks.retired_at + grace_window
        minted_before_retirement = token_iat < ks.retired_at
        if within_grace and minted_before_retirement:
            return ks
        raise RetiredKeyInUse(
            f"kid {kid!r} retired at {ks.retired_at}; "
            f"token_iat={token_iat} now={now} grace={grace_window}"
        )

    raise RetiredKeyInUse(f"kid {kid!r} has unrecognized status {ks.status!r}")


# --- example ---
if __name__ == "__main__":
    keys = {
        "rsa-2024a": KeyStatus("rsa-2024a", "retired", retired_at=1_700_000_000),
        "ec-2025b": KeyStatus("ec-2025b", "active"),
    }
    now = 1_700_000_050
    # legitimate in-flight token, minted before retirement
    authorize_key("rsa-2024a", token_iat=1_699_999_990, now=now, keyset=keys)
    # attacker-minted fresh token under retired key -> must raise
    authorize_key("rsa-2024a", token_iat=1_700_000_040, now=now, keyset=keys)
```