# In what scenarios must an instance treat cryptographic erasure as unverifiable rather than failed when the key destruction audit trail is incomplete

**Date of Record:** 2026 November 12

**Scope:** Applies to memory-forgetting guarantees in systems where erasure of tenant data is asserted via destruction of a wrapping key (crypto-shredding) and verified by an audit trail of key lifecycle events. Does not apply to physical media destruction, to plaintext overwrite regimes, or to erasure claims backed by a trusted, append-only hardware root of trust that is independently attested.

## Core Distinction

A compliance erasure claim has two distinct failure modes that operators routinely conflate: *cryptographic erasure failed* (the key still exists, or was recoverable, or the ciphertext remains decryptable) versus *cryptographic erasure is unverifiable* (the key is gone, but the evidence chain proving it is gone is incomplete, ambiguous, or has a gap). The first is a genuine violation. The second is an evidentiary gap. Treating the second as the first triggers false breach declarations, unnecessary regulator notifications, and — worse — erodes trust in the verification channel so that genuine violations get discounted. Treating the first as the second is a cover-up. The boundary is the point where the audit record cannot distinguish "destroyed" from "never created" or "destroyed twice," and the system must refuse to assert either.

## What Was Observed

During a key-rotation-driven erasure of a sharded object store, the erasure job wrote a `KEY_DESTROYED` event to the audit log *after* issuing the HSM destroy command but *before* confirming the HSM acknowledged. A transient HSM partition failover dropped the acknowledgement. The audit log therefore contained a `KEY_DESTROYED` record with no matching `HSM_ACK` record. The key was, in fact, destroyed — a subsequent `describe-key` returned `NotFound` on the primary and all replicas. But the verification pipeline, which required `DESTROYED → ACK` adjacency, classified the erasure as *failed* and re-ran destruction against a key that no longer existed. The re-run produced a `DESTROY_FAILED: key not found` event, which the pipeline then escalated as a compliance incident. The actual state — key provably absent, evidence chain broken — was never represented in the state machine because the state machine had no state for it.

A second observation: keys created by a decommissioned provisioning path had `KEY_CREATED` records with a null `tenant_id` because the field was added after those keys were minted. For those keys, destruction could be confirmed but *attribution* to a specific erasure request could not. The pipeline again reported failure. The correct classification was "unverifiable attribution," not "erasure failed."

## Condition of Validity

The distinction is valid — and the system must classify as *unverifiable* rather than *failed* — precisely when all of the following hold:

1. The key material is independently confirmed absent (HSM `describe`/`list` returns no such key on every replica, or the KMS returns a terminal `NotFound` that is itself attested).
2. The audit trail lacks a contiguous, ordered, non-repudiable record linking the erasure request to that terminal absence.
3. The gap is attributable to a *known* class of instrumentation defect (post-command pre-ack write, schema evolution, replica divergence), not to evidence of key recovery or re-creation.

If any of (1) fails — the key is present or its absence is not confirmed — the classification is *failed*, full stop. If (3) fails — the gap is unexplained — the classification is *unverifiable* but with an escalation flag, because an unexplained gap could conceal re-creation.

## Decision Boundary

The boundary is not "did the destroy command succeed." It is "can the audit chain, as recorded, distinguish terminal absence from a gap in recording." When the chain cannot make that distinction, the honest machine state is `ERASURE_UNVERIFIABLE`, and the compliance assertion is *withheld*, not *denied*. Withholding is a defensible position: it says "we cannot prove erasure from this record; we can prove key absence from a separate channel." Denial is not defensible when the key is provably gone, because it is false. The system must never emit `ERASURE_FAILED` for a key that is confirmed absent; it must emit `ERASURE_UNVERIFIABLE` with the confirming channel cited.

## Operational Effect

Downstream, the effect is that the erasure job is idempotent with respect to *evidence*, not just *key state*. A re-run against a confirmed-absent key must not attempt destruction; it must instead attempt to *repair the evidence chain* by querying an independent authority (HSM audit log, KMS control-plane log) and, if that authority confirms absence, upgrading the state to `ERASURE_VERIFIED_VIA_SECONDARY`. Only if no channel confirms absence does the state remain `ERASURE_UNVERIFIABLE` and route to human review. This prevents the false-incident cascade, preserves the integrity of the `ERASURE_FAILED` signal for real failures, and keeps the compliance record truthful about what was and was not proven.

```python
class ErasureClassificationError(RuntimeError):
    """Raised when an erasure claim cannot be honestly classified."""
    pass


class ErasureState:
    VERIFIED = "ERASURE_VERIFIED"
    VERIFIED_SECONDARY = "ERASURE_VERIFIED_VIA_SECONDARY"
    UNVERIFIABLE = "ERASURE_UNVERIFIABLE"
    FAILED = "ERASURE_FAILED"


def classify_erasure(key_absent_confirmed: bool,
                     chain_contiguous: bool,
                     gap_is_known_defect: bool,
                     secondary_confirmation: bool) -> str:
    """Classify an erasure claim. Never emit FAILED for a provably absent key."""
    if not key_absent_confirmed:
        # Key present or absence unproven: this is a real failure.
        return ErasureState.FAILED

    if chain_contiguous:
        return ErasureState.VERIFIED

    if secondary_confirmation:
        # Key gone, primary chain broken, but an independent channel confirms.
        return ErasureState.VERIFIED_SECONDARY

    if gap_is_known_defect:
        # Gap is attributable to instrumentation, not to key recovery.
        return ErasureState.UNVERIFIABLE

    # Unexplained gap with confirmed absence: unverifiable but escalated.
    raise ErasureClassificationError(
        "Unexplained evidence gap with confirmed key absence; "
        "route to human review, do not emit FAILED or VERIFIED."
    )


def assert_no_false_failure(state: str, key_absent_confirmed: bool) -> None:
    if state == ErasureState.FAILED and key_absent_confirmed:
        raise ErasureClassificationError(
            "Refusing to emit ERASURE_FAILED for a key confirmed absent; "
            "this is an evidentiary gap, not a cryptographic failure."
        )
```