feat(cmd): verify a retired root key is removable by unwrapping

Suleimi Ahmedrequested to merge
sahmed/s04b-verify-root-key-removable into main

What

Adds re-encrypt --scope=root --phase=verify: prove every live namespace key still unwraps under the active root key, before the operator removes a retired key from Vault.

--phase is new on the root scope and defaults to rewrap, so every existing runbook and Job invocation behaves exactly as before.

Why

The re-wrap phase's verification reads root_key_uri. Nothing checks that column against the key a row's wrapped_key is actually sealed under — UnwrapKey never reads it, because the local provider tries every key it holds. So a row whose label names the active key while its ciphertext is still sealed under a retired one is:

  • skipped by the re-wrap selection (it looks already-rotated), and
  • passed by the re-wrap verification (it looks compliant).

Removing the retired key from Vault then makes that row permanently unwrappable and the namespace's credentials permanently unreadable. The label can diverge without an attacker: RootKeyProvider does not require WrapKey to stamp KeyURI(), and the re-wrap's own write validates only the URI the provider returned before overwriting the sole copy of the ciphertext.

--phase=verify asks the ciphertext, which no label can misreport.

How

  • ListLiveKeys — a paged, cross-namespace live-key read carrying the same live-set predicates the sibling rotation reads carry.
  • A provider built over only keys[0]. Building it over the whole mounted key file would defeat the phase: every retired key is still in that file for the whole rotation window, so a row left on one would unwrap and pass. This is the property TestVerifyRootKeyRemovable_FailsOnARowSealedUnderARetiredKey pins, with a two-key file.
  • A three-way verdict — all rows unwrapped / at least one did not / the drain did not finish — because the operator's next action differs in each. A partial pass proves nothing and must not read as either of the other two.
  • Two defective-read tripwires: a page that does not advance the cursor, and a page longer than the requested limit. Either aborts before a verdict rests on it, matching what the spec already requires of the credential sweep's paged reads.
  • The offender count is tracked apart from the capped sample the log enumerates, so a run past the cap reports the true total rather than the number of warning lines.

Notable decisions

root_key_uri is not added to the wrapping AAD. It would not close this gap: a writer that stamps a wrong URI stamps it into the AAD too, so the wrapping is self-consistent, unwraps, and fools the re-wrap verification exactly as before. It would also turn a recoverable label divergence into an unrecoverable one. Recorded in the spec's Resolutions.

An accepted code smell. listLiveKeysStmt keeps a shredded_at IS NULL conjunct that changes no result set — a shredded row is a tombstone for its own namespace, so the tombstone exclusion already removes it. It stays because a partial index is only usable where the query implies its predicate, and index_ns_enc_keys_on_root_key_uri is partial on exactly that condition. Measured: with the conjunct each partition takes a Bitmap Index Scan on that index; without it, all 64 fall to Seq Scan. No correctness test can kill it, so an EXPLAIN test asserts reachability with and unreachability without, and says to delete the conjunct if that stops holding.

A follow-up, not fixed here. RotateAll validates only the URI its provider returned before overwriting a row's wrapped_key, so this phase detects a divergence after the fact rather than preventing it. Verifying the new wrapping unwraps before the write is what would make it unreachable. Added to the spec's Follow-ups.

Review round 1

Six threads, all accepted and answered in place. Two changed the implementation in ways worth surfacing here:

  • AppSec — ciphertext probe gap. The log-absence assertion used %v, which renders []byte as a decimal list; slog.Any emits base64, so slog.Any("wrapped_key", …) would have passed silently. Confirmed empirically, and there was a third encoding neither of us listed (slog.String(string(raw))). The probe now covers all three, derives the escaped-UTF-8 needle from slog itself, and a new test proves the guard catches each leak path rather than trusting an account of the encodings.
  • Duo — every page scanned the whole live set. Correct, and the most valuable finding on the MR. The tombstone NOT EXISTS was being pulled up into a hash anti join, which discards the id ordering LIMIT needs, so the planner materialised all live rows across 64 partitions per page. Fixed; see Database review evidence below for the measurement.

Duo's stated premise was wrong in one respect worth recording: the PK is (id, namespace_id), so id does lead and an ordered path existed all along. The conclusion held anyway.

That fix then invalidated the justification for a redundant shredded_at IS NULL conjunct elsewhere in the same statement — its own EXPLAIN test caught that by failing. The conjunct still earns its place, but for a different reason (short-circuiting the subquery probe, 2,287 buffers versus 2,485), and both its comment and its test are rewritten.

Verification

Tree-pinned to the rebased branch.

Check Result
go build ./... 0
go vet ./internal/... ./cmd/..., and with -tags=integration 0
go test ./internal/... ./cmd/... 0
go test -race (crypto, datastore, cmd) 0
GODEBUG=fips140=only ./internal/crypto/... 0
golangci-lint run ./internal/... ./cmd/... 0 findings in any file this branch touches
golangci-lint run --build-tags=integration --max-same-issues=0 --max-issues-per-linter=0 0 findings in any file this branch touches
mise run lint:docs 0 errors
Integration suites on PostgreSQL 16 / 17 / 18 0 / 0 / 0
pre-commit scoped to the branch (32 hooks) exit 0

golangci-lint reports 11 findings on pristine origin/main in this worktree (checksum, ociroute, jobsriver, jsonsafe, slug, transport) — identical before and after this branch's changes, so none are introduced here. Flagging separately: main appears to be lint-dirty from recent merges.

Non-vacuity. 19 mutations were applied; 18 were killed, including: the active-only provider widened to the whole key file; the offender count replaced by the capped sample size; the drain stopping after one page; the deadline arm treated as a plain store error; --phase defaulting to verify; the cursor predicate relaxed from > to >=; the tombstone exclusion dropped; wrapped_key dropped from the projection; and ListLiveKeys losing its per-statement deadline.

Round 1 added three more, all killed: the over-long-page guard disabled, and the ciphertext probe faced with a real slog.Any leak (which the old %v-only probe passed and the new probe set fails on).

The one that survived was dropping shredded_at IS NULL from listLiveKeysStmt — correctly, since it is result-set-redundant. That survival is what produced its EXPLAIN test, rather than being written off.

Two defects were found by these tests during development and fixed here:

  • the verdict reported the capped sample size as the offender count, so a run with 25 offenders said "20 of 20";
  • a store whose read stopped advancing the cursor made the drain spin forever holding an operator connection instead of failing. It now refuses.

Database review evidence

Query mode only — this MR adds no migration. Collected per db-review-prep methodology against PostgreSQL 17.10 (matching GL_PG_CURR_VERSION), inside a rolled-back transaction, seeded from the schema's FK graph.

Queries

Note

Plans are from EXPLAIN (ANALYZE, BUFFERS) at moderate cardinality (namespaces=600, namespace_encryption_keys=6000, of which 5,400 live and 600 tombstoned across 60 namespaces) and do not capture production-scale effects. Two rows are given for the one new method because its cost profile differs between the first page and the tail of the drain, and both are operationally reachable. Expand each row for seed shape, rendered SQL, bound args, and the raw plan.

Method Plan node Index Rows (plan / actual) Cost Time Buffers (hit / read) Partitions
datastore.ListLiveKeys.first-page Limit → Merge Append → Index Scan ×64 namespace_encryption_keys_p00..p63_pkey 1000 / 1000 5064.78 18.678ms 2290 / 0 ⚠️ 64/64
datastore.ListLiveKeys.drain-tail Limit → Sort → Bitmap Heap Scan namespace_encryption_keys_p00..p63_pkey (bitmap) 185 / 399 1332.39 9.320ms 864 / 0 ⚠️ 25/64

Warning

Partition fan-out. This statement scans more than one partition of a hash-partitioned table:

  • datastore.ListLiveKeys: 64/64 partitions of namespace_encryption_keys (25/64 at the drain tail, where the cursor has already passed the rest). The partition key is namespace_id and this read deliberately does not bind it: it is a cross-namespace sweep whose entire purpose is to visit every namespace's live keys, so there is no value to thread through. The fan-out is inherent to the operation, not a missing predicate, and it is the same shape the sibling ListLiveKeysNotUnderRootKeyURI rotation read already has. What is bounded is the work per statement: see the first-page details below.
datastore.ListLiveKeys.first-page

Summary: Plan matches the method's intent. LIMIT terminates early off a Merge Append over the 64 partitions' primary keys (id leads pk_namespace_encryption_keys), so the page returns 1000 rows having examined 1,063 — proportional to the limit, not to the table. The tombstone predicate stays a per-row SubPlan filter, which is what preserves the ordering; the cheaper shredded_at IS NULL qual is ordered ahead of it, so shredded rows skip the probe. Full partition fan-out is inherent (see warning above). No anomalies.

Seed shape: namespaces=600, namespace_encryption_keys=6000

Rendered SQL:

SELECT namespace_encryption_keys.id AS "namespace_encryption_keys.id",
     namespace_encryption_keys.namespace_id AS "namespace_encryption_keys.namespace_id",
     namespace_encryption_keys.version AS "namespace_encryption_keys.version",
     namespace_encryption_keys.wrapped_key AS "namespace_encryption_keys.wrapped_key",
     namespace_encryption_keys.root_key_uri AS "namespace_encryption_keys.root_key_uri",
     namespace_encryption_keys.active AS "namespace_encryption_keys.active",
     namespace_encryption_keys.created_at AS "namespace_encryption_keys.created_at"
FROM public.namespace_encryption_keys
WHERE ((namespace_encryption_keys.id > $1::uuid) AND (namespace_encryption_keys.shredded_at IS NULL)) AND (NOT (EXISTS (
           SELECT $2
           FROM public.namespace_encryption_keys AS tombstones
           WHERE (tombstones.namespace_id = namespace_encryption_keys.namespace_id) AND (tombstones.shredded_at IS NOT NULL)
           OFFSET $3
      )))
ORDER BY namespace_encryption_keys.id ASC
LIMIT $4;

Bound args: ['00000000-0000-0000-0000-000000000000', 1, 0, 1000]

Plan (EXPLAIN (ANALYZE, BUFFERS) output):

Limit  (cost=11.02..5064.78 rows=1000 width=71) (actual time=3.165..16.101 rows=1000 loops=1)
  Buffers: shared hit=2290
  ->  Merge Append  (cost=11.02..13656.16 rows=2700 width=71) (actual time=3.161..15.986 rows=1000 loops=1)
        Sort Key: namespace_encryption_keys.id
        Buffers: shared hit=2290
        ->  Index Scan using namespace_encryption_keys_p00_pkey on namespace_encryption_keys_p00 namespace_encryption_keys_1  (cost=0.14..247.55 rows=50 width=71) (actual time=0.073..0.270 rows=15 loops=1)
              Index Cond: (id > '00000000-0000-0000-0000-000000000000'::uuid)
              Filter: ((shredded_at IS NULL) AND (NOT EXISTS(SubPlan 1)))
              Rows Removed by Filter: 3
              Buffers: shared hit=41
              SubPlan 1
                ->  Append  (cost=0.00..179.43 rows=86 width=4) (actual time=0.010..0.010 rows=0 loops=1063)
                      Buffers: shared hit=1849
                      ->  Seq Scan on namespace_encryption_keys_p00 tombstones_1  (cost=0.00..3.38 rows=1 width=4) (actual time=0.010..0.010 rows=0 loops=15)
                            Filter: ((shredded_at IS NOT NULL) AND (namespace_id = namespace_encryption_keys_1.namespace_id))
                            Rows Removed by Filter: 110
                            Buffers: shared hit=30
                      ->  Seq Scan on namespace_encryption_keys_p01 tombstones_2  (cost=0.00..3.25 rows=1 width=4) (actual time=0.008..0.008 rows=0 loops=16)
              …
              (62 further partition scans elided; each is the same shape)
Planning:
  Buffers: shared hit=8145
Planning Time: 96.059 ms
Execution Time: 18.678 ms

Timings: planning 96.059ms, execution 18.678ms, total 114.737ms.

datastore.ListLiveKeys.drain-tail

Summary: The same statement at a cursor near the end of the drain, with 399 rows left. The planner drops the 64-way merge and sorts the residual tail instead — correct, and still bounded: it sorts 399 rows, not the live set, and the cursor has already excluded 39 partitions from the scan. Included because a first-page plan alone would not show what later pages do. The tombstone predicate remains a SubPlan filter here too, which is the property that must hold at every cursor. No anomalies.

Seed shape: namespaces=600, namespace_encryption_keys=6000

Rendered SQL: as above.

Bound args: ['ec5bfe78-11fc-48ae-a0d7-6a0107793e2a', 1, 0, 1000]

Plan (EXPLAIN (ANALYZE, BUFFERS) output):

Limit  (cost=1331.93..1332.39 rows=185 width=71) (actual time=6.091..6.455 rows=399 loops=1)
  Buffers: shared hit=864
  ->  Sort  (cost=1331.93..1332.39 rows=185 width=71) (actual time=6.089..6.425 rows=399 loops=1)
        Sort Key: namespace_encryption_keys.id
        Sort Method: quicksort  Memory: 77kB
        Buffers: shared hit=864
        ->  Append  (cost=4.20..1324.96 rows=185 width=71) (actual time=0.087..6.122 rows=399 loops=1)
              Buffers: shared hit=861
              ->  Bitmap Heap Scan on namespace_encryption_keys_p00 namespace_encryption_keys_1  (cost=4.20..20.89 rows=3 width=71) (actual time=0.086..0.158 rows=8 loops=1)
                    Recheck Cond: (id > 'ec5bfe78-11fc-48ae-a0d7-6a0107793e2a'::uuid)
        …
        (25 partition scans and the SubPlan branches elided)
Planning:
  Buffers: shared hit=8033
Planning Time: 73.022 ms
Execution Time: 9.320 ms

Timings: planning 73.022ms, execution 9.320ms, total 82.342ms.

Plan regressions are pinned, not just measured

Two integration tests keep these plans from drifting, both run on PostgreSQL 16, 17 and 18:

  • TestNamespaceEncryptionKeyStore_ListLiveKeys_PagesWithoutSortingTheLiveSet — requires the tombstone predicate to stay a SubPlan (never an anti join) at both the first page and the deepest cursor, and requires the first page to reach a Merge Append with no sort.
  • TestNamespaceEncryptionKeyStore_ListLiveKeys_ShortCircuitsTheTombstoneProbe — requires shredded_at IS NULL to be filtered ahead of the subquery on the same scan, which is the only thing that redundant conjunct is kept for.

Both were written against a larger fixture (8,000 namespaces / 80,000 rows, 72,000 live) than the numbers above, where the merged plan examined all 72,000 rows per page against ~1,063 for the plan this MR ships.

Reviewable size

+1723/−31 across 14 files, well past the 500-LOC bar. Split by group:

Group LOC
Implementation (reencrypt.go, operator.go, store read, query name) +407 / −18
Tests (new verify suite, store integration, EXPLAIN plans, fake stores) +1177 / −2
Docs (spec, plan, runbook) +139 / −11

Tests are 68% of the diff. The implementation is 407 lines and much of that is doc comment.

Splitting was considered and rejected: the store read has no consumer other than this phase, so a two-MR stack would leave the first MR landing a dead method. Implementation is 359 lines, much of it doc comment; the bulk of the diff is tests and documentation.

e2e scenarios

No scenario in docs/testing/ is added or affected: the catalogs cover client-facing per-format flows, and this is an operator command with no client surface.

Found during the #608 data-consistency review of the merged S04 A/B/C tier.

Related to https://gitlab.com/gitlab-org/ops/artifact-registry/-/work_items/651

Edited by Suleimi Ahmed

Merge request reports