Rotating Encryption Keys for Baseline Plan Stores

Rotating encryption keys for a baseline plan store means retiring the key-encryption key on a schedule and re-wrapping every stored data-encryption key without decrypting a single plan artifact, without downtime, and without breaking the fingerprint lookups that regression detection depends on. This runbook documents the envelope-encryption model (KMS-held KEK, per-store DEK, ciphertext at rest), the exact key-age and backlog thresholds that force a rotation, a zero-downtime re-wrap implemented against asyncpg, and the audit trail that proves every ciphertext row is readable under the current key version. It is the operational counterpart to Encrypting Baseline Query Plans at Rest and in Transit and lives under Security Boundaries for Baseline Data Storage.

The critical constraint is that a plan fingerprint is computed over plaintext and stored alongside ciphertext. Rotation must re-wrap the key material only — the DEK that encrypts the plan blob — while the plaintext, and therefore the fingerprint, is untouched. Get this wrong by re-encrypting under a fresh DEK in place without recording which version wrote which row, and lookups silently return decrypt_failed for a growing slice of the store.

Symptom Identification and Production Thresholds #

Envelope encryption fails quietly: a mis-versioned row does not raise until something tries to decrypt it. Treat each of the following as a hard breach condition with an exact trigger:

1. KEK age past ceiling. The active KEK version is older than 90 days, or older than 30 days past a known credential exposure. A KEK beyond its rotation window is an audit finding on its own.
2. Re-wrap backlog. More than 500 rows in the plan store carry a key_version lower than the current KEK version, or the oldest un-rewrapped row is more than 24 hours behind a started rotation. A stalled re-wrap leaves the store split across key generations.
3. Decrypt-failure rate. The decrypt-error rate across baseline lookups exceeds 0.1% of reads over any 5-minute window. Any sustained non-zero rate means at least one key version is missing from the resolver or a row was written without its key_version.
4. Mixed-version read amplification. A single fingerprint lookup requires more than 1 distinct KEK version to resolve its candidate rows. Cross-version fan-out means rotation left the fingerprint’s history straddling two keys.
5. KMS decrypt latency. p99 KMS Decrypt (unwrap) latency exceeds 45 ms, or the KMS call rate exceeds the account throttle by any margin. Unwrapping on every read, rather than caching the unwrapped DEK, turns rotation into a latency incident.
6. Orphaned key material. A DEK ciphertext exists in the store with no corresponding KEK version retained in KMS. This is unrecoverable data; it must fire a page, not a warning.

When conditions 2 and 3 fire together, freeze new writes to the affected DEK, complete the re-wrap batch, and only then resume.

Root Cause Analysis #

Three failure domains break envelope rotation. Each has a direct diagnostic.

Mixed key versions with no version column. If the schema stores a wrapped DEK but not the KEK version that wrapped it, the resolver cannot pick the right unwrap key and guesses — which fails as soon as two versions coexist. Confirm the column exists and is populated on every row:

-- Every ciphertext row must carry the KEK version that wrapped its DEK.
SELECT key_version, count(*) AS rows,
       min(created_at) AS oldest, max(created_at) AS newest
FROM baseline_plan_store
GROUP BY key_version
ORDER BY key_version;

More than one non-null key_version is expected mid-rotation; a NULL key_version is the bug — those rows cannot be resolved deterministically.

In-place re-encrypt races. A re-wrap that reads a row, unwraps, re-wraps, and writes back without row-level locking can lose a concurrent write, leaving a row wrapped under a KEK version that KMS no longer serves. Detect lost updates by looking for rows whose key_version regressed below the rotation floor:

-- Rows still on a retired KEK after the rotation floor timestamp.
SELECT count(*) AS stale_rows
FROM baseline_plan_store
WHERE key_version < (SELECT current_kek_version FROM kek_state)
  AND rewrapped_at IS NULL;

If stale_rows stops decreasing while the worker runs, the worker is racing writers; switch it to SELECT ... FOR UPDATE SKIP LOCKED batching.

Unwrap-per-read without DEK caching. Calling KMS Decrypt on every lookup couples read latency to KMS availability and throttle limits. Inspect the call pattern from the audit log:

# Count KMS unwrap calls vs baseline reads over the last hour (structured audit).
grep kms_unwrap /var/log/baseline/audit.jsonl \
  | jq -r 'select(.ts > (now - 3600)) | .kek_version' | sort | uniq -c

An unwrap count that tracks read volume one-to-one means there is no per-DEK cache; the DEK should be unwrapped once and held in memory for the store’s lifetime, re-unwrapped only on rotation.

Step-by-Step Remediation #

1. Add the version and audit columns. The store must record which KEK wrapped each DEK and when the row was last re-wrapped:

ALTER TABLE baseline_plan_store
  ADD COLUMN IF NOT EXISTS key_version  integer NOT NULL DEFAULT 1,
  ADD COLUMN IF NOT EXISTS wrapped_dek  bytea   NOT NULL,
  ADD COLUMN IF NOT EXISTS rewrapped_at timestamptz;

CREATE INDEX IF NOT EXISTS idx_plan_store_stale
  ON baseline_plan_store (key_version)
  WHERE rewrapped_at IS NULL;

-- Single source of truth for the active KEK generation.
CREATE TABLE IF NOT EXISTS kek_state (
  singleton boolean PRIMARY KEY DEFAULT true CHECK (singleton),
  current_kek_version integer NOT NULL,
  rotated_at timestamptz NOT NULL DEFAULT now()
);

2. Run the zero-downtime re-wrap. The worker claims rows in bounded batches with SKIP LOCKED, unwraps each DEK under the old KEK, re-wraps it under the new KEK, and advances key_version — never touching wrapped_dek’s underlying plaintext key beyond the KMS round trip, and never touching the plan blob. It is async, typed, and every action is a structlog audit event and an OpenTelemetry span.

from __future__ import annotations

import asyncio
from dataclasses import dataclass

import asyncpg
import structlog
from opentelemetry import metrics, trace

log = structlog.get_logger("baseline.keyrotation")
tracer = trace.get_tracer("baseline.keyrotation")
meter = metrics.get_meter("baseline.keyrotation")

_rewrapped = meter.create_counter("dek_rewrapped_total")
_failures = meter.create_counter("dek_rewrap_failed_total")

BATCH_SIZE = 200                 # rows claimed per transaction
KEK_MAX_AGE_DAYS = 90            # rotation ceiling
BACKLOG_CEILING = 500            # stale rows that force completion before new writes


@dataclass
class KmsEnvelope:
    """Thin async adapter over a KMS. unwrap/rewrap are provider-specific."""
    client: object
    key_arn: str

    async def unwrap(self, wrapped_dek: bytes, kek_version: int) -> bytes:
        return await self.client.decrypt(self.key_arn, wrapped_dek, kek_version)

    async def rewrap(self, wrapped_dek: bytes, from_v: int, to_v: int) -> bytes:
        plaintext_dek = await self.unwrap(wrapped_dek, from_v)
        try:
            return await self.client.encrypt(self.key_arn, plaintext_dek, to_v)
        finally:
            del plaintext_dek  # drop key material as soon as it is re-wrapped


async def rewrap_batch(pool: asyncpg.Pool, kms: KmsEnvelope, target_version: int) -> int:
    with tracer.start_as_current_span("rewrap_batch") as span:
        span.set_attribute("kek.target_version", target_version)
        async with pool.acquire() as conn:
            async with conn.transaction():
                rows = await conn.fetch(
                    """
                    SELECT id, key_version, wrapped_dek
                    FROM baseline_plan_store
                    WHERE key_version < $1 AND rewrapped_at IS NULL
                    ORDER BY key_version, id
                    LIMIT $2
                    FOR UPDATE SKIP LOCKED
                    """,
                    target_version, BATCH_SIZE,
                )
                done = 0
                for r in rows:
                    try:
                        new_dek = await kms.rewrap(
                            r["wrapped_dek"], r["key_version"], target_version)
                        await conn.execute(
                            "UPDATE baseline_plan_store "
                            "SET wrapped_dek=$1, key_version=$2, rewrapped_at=now() "
                            "WHERE id=$3",
                            new_dek, target_version, r["id"],
                        )
                        _rewrapped.add(1, {"to_version": str(target_version)})
                        done += 1
                    except Exception:  # noqa: BLE001 — audit then continue; never abort the batch
                        _failures.add(1)
                        log.error("rewrap_failed", row_id=str(r["id"]),
                                  from_version=r["key_version"], exc_info=True)
                span.set_attribute("rewrap.rows_done", done)
                return done


async def run_rotation(pool: asyncpg.Pool, kms: KmsEnvelope, target_version: int) -> None:
    total = 0
    while True:
        n = await rewrap_batch(pool, kms, target_version)
        total += n
        log.info("rewrap_progress", batch=n, total=total, target_version=target_version)
        if n == 0:
            break
        await asyncio.sleep(0.05)  # yield; keep KMS call rate under the account throttle
    log.info("rewrap_complete", total=total, target_version=target_version)

3. Flip the active version and retire the old KEK. Only after the backlog reaches zero, advance kek_state.current_kek_version and schedule the retired KEK for deletion after a retention window — never before the store is fully re-wrapped. Expected audit trail for a clean rotation:

2026-07-18T02:03:11Z [info]  rewrap_progress batch=200 total=200 target_version=7
2026-07-18T02:03:12Z [info]  rewrap_progress batch=200 total=3400 target_version=7
2026-07-18T02:03:14Z [info]  rewrap_progress batch=64  total=3464 target_version=7
2026-07-18T02:03:14Z [info]  rewrap_complete total=3464 target_version=7
2026-07-18T02:03:14Z [info]  kek_state_advanced current_kek_version=7 stale_rows=0

Because the plan blob and its plaintext fingerprint are never re-encrypted, lookups keep resolving throughout — the same immutability guarantee the Plan Hashing Algorithms for SQL Engines rely on.

Verification Checklist #

• [ ] Every row in baseline_plan_store has a non-null key_version and no version predates the rotation floor.
• [ ] stale_rows (rows below current_kek_version with rewrapped_at IS NULL) is exactly 0 before the old KEK is scheduled for deletion.
• [ ] The active KEK version is under 90 days old and both old and new KEK versions were resident in KMS for the entire re-wrap.
• [ ] Decrypt-failure rate across baseline lookups is 0% over a 15-minute window after the version flip.
• [ ] No fingerprint lookup requires more than one KEK version to resolve its rows.
• [ ] A sampled plan artifact decrypts and its recomputed fingerprint matches the stored fingerprint byte-for-byte.
• [ ] p99 KMS unwrap latency is under 45 ms and unwrap call count is decoupled from read volume (DEK cache confirmed).
• [ ] The rotation is recorded in kek_state with a rotated_at timestamp and a matching audit-log line.

Compatibility and Engine-Specific Notes #

The envelope model is portable; the KMS primitives and their version semantics differ.

AWS ReEncrypt and Vault rewrap re-wrap without exposing the DEK plaintext to your process, so prefer them over the manual decrypt-then-encrypt path where available; on GCP the plaintext DEK transits your worker briefly, so the del plaintext_dek discipline in the code above is load-bearing. Whichever provider, keep at least the current and immediately-previous KEK version decryptable until the backlog is provably zero, and ground the underlying at-rest model in Encrypting Baseline Query Plans at Rest and in Transit.

Related #

• ← Back to Security Boundaries for Baseline Data Storage (parent topic)
• The at-rest and in-transit model this rotates: Encrypting Baseline Query Plans at Rest and in Transit
• Why the fingerprint survives rotation: Plan Hashing Algorithms for SQL Engines
• Wider context: Core Architecture & Baselining Fundamentals