BYOK, KMS, and the boring parts of multi-tenant secrets

The vault post covered how rotation works when the master key lives inside RedDB’s own keystore. That’s fine for single-tenant deployments. The moment you sell to a regulated buyer — banks, healthcare, anyone with a CISO — they ask the same question: can we keep our own key? The answer has to be yes, and the integration has to survive the failure modes that BYOK quietly introduces.

This post is the boring half of the story. Configuration, failure modes, and the operational shape that keeps you from waking up to a stuck write path.

What BYOK actually means

“Bring your own key” gets used loosely. In practice there are three shapes:

Customer-managed KMS key (CMK). The customer creates a key in their cloud account; you call their KMS with an IAM role they grant you. AWS KMS, GCP KMS, Azure Key Vault — all the same shape. Most common.
External key store / HSM-backed. The CMK in KMS is itself wrapped by a key that lives in a customer-controlled HSM (CloudHSM, GCP EKM, Thales/Entrust on-prem). Every KMS operation hits the HSM. Higher latency, higher assurance, much higher operational tax.
Hold-your-own-key (HYOK). The customer’s HSM is the only place the key exists; you never see it unwrapped. Architecturally this means the data either decrypts inside their network (proxy model) or doesn’t decrypt at all in your hot path (envelope-with-remote-unwrap, see below). HYOK is rare and almost always vendor-specific.

RedDB supports (1) and (2) directly. (3) is a custom integration we’ve done twice; the failure modes are similar but worse.

For the rest of this post, “KMS” means the customer’s chosen provider — AWS, GCP, Azure, or HSM-backed equivalent. They differ in API surface but not in the operational story.

The envelope, revisited

Recap from the vault post: each encrypted row carries an envelope (g, iv, ciphertext) where g selects a master key generation. In single-tenant mode, those master keys are wrapped by RedDB’s own keystore.

In BYOK mode, the same generation byte selects a data encryption key (DEK) that is wrapped by the customer’s KMS:

                                customer's KMS
                                    │
            ┌──── unwrap(EncryptedDEK_g) ────┐
            ▼                                │
       DEK_g (in memory, cached)             │
            ▼                                │
   AES-GCM(row.iv, plaintext) ─► ciphertext  │
                                             │
            stored on disk:                  │
       (g, iv, ciphertext, kms_arn)          │
                                             ▼
                                customer's KMS audit log
                                (one entry per unwrap)

Three things matter and people forget:

The DEK is never written unwrapped. Only the KMS-wrapped form (EncryptedDEK_g) is on disk, in a small vault_keyring table.
Unwrap is cached. Calling KMS on every row read would put 5–50ms of KMS latency on the hot path. The DEK lives in process-local memory with a TTL.
The KMS ARN/resource ID is recorded with the envelope. This matters for multi-tenant setups where different tenants use different CMKs (see “Multi-tenant” below).

Configuration

A minimal BYOK config for AWS KMS:

vault:
  provider: aws-kms
  region: us-east-1
  cmk: arn:aws:kms:us-east-1:111122223333:key/abcd1234-...
  iam_role: arn:aws:iam::111122223333:role/RedDBVaultAccess
  dek_cache:
    ttl: 1h
    max_entries: 1024
  kms_timeout: 2s
  kms_retry:
    attempts: 3
    backoff: exponential
    max_total: 5s

GCP is similar with kms_key: projects/.../locations/.../keyRings/.../cryptoKeys/... and a service account; Azure uses vault_uri and a managed identity. The shape is intentionally provider-shaped, not least-common-denominator — providers diverge in attestation, audit, and rotation semantics, and a fake-uniform abstraction would lie about them.

The four knobs that matter operationally:

Knob	Default	What happens if you get it wrong
`dek_cache.ttl`	`1h`	Too long: revocation slow. Too short: KMS request rate goes up 100×.
`kms_timeout`	`2s`	Too short: transient KMS hiccups cause write failures.
`kms_retry.max_total`	`5s`	Total wall-clock budget for unwrap including retries.
`dek_cache.max_entries`	`1024`	Sized for active generations × tenants. Default fits ~10 tenants.

dek_cache.ttl is the one that decides the security-vs-availability tradeoff. We default to one hour because most customers’ “rotate immediately when an engineer leaves” runbook tolerates an hour of stale-key exposure. Some banks require five minutes. The blast radius of getting this wrong is one knob away — write it down in your runbook.

Multi-tenant: one CMK per tenant

The pattern most SaaS deployments want:

One CMK per customer, in their AWS account.
An IAM trust policy that lets RedDB assume a role into their account.
A row-level tenant_id column that selects which CMK was used to wrap the DEK for that row’s generation.

The vault keyring table grows a tenant dimension:

CREATE TABLE vault_keyring (
  tenant_id     uuid NOT NULL,
  generation    smallint NOT NULL,
  kms_arn       text NOT NULL,
  wrapped_dek   bytea NOT NULL,
  created_at    timestamptz NOT NULL,
  retired_at    timestamptz,
  PRIMARY KEY (tenant_id, generation)
);

Reads look up (tenant_id, generation), unwrap once via the tenant’s KMS, cache the DEK keyed on the same pair. Writes always use the tenant’s active-write generation.

Two things this gets you for free:

Cryptographic deletion per tenant. Customer churns? Revoke their CMK in their KMS console. Every row of theirs becomes unreadable, instantly, with no scan over your storage. The bytes are still on your disks, but they’re effectively shredded. This is the GDPR erasure shape your privacy lawyer wants.
No cross-tenant blast radius. A misconfigured IAM policy on Tenant A’s CMK doesn’t take down Tenant B’s reads.

Two things it costs you:

Cache pressure scales with active tenants. Size dek_cache.max_entries accordingly. With 10,000 tenants and 8KB per DEK entry, that’s 80MB of cache — fine. With 1M tenants, you’re rebuilding the cache strategy. We have customers doing both; the 1M case uses a two-tier cache with an L2 backed by RedDB itself (yes, the database caches its own keys).
KMS rate limits per account. AWS KMS defaults to 10,000 RPS per region per account. If your tenants share an AWS account (rare) or your cache TTL is too low (common mistake), you’ll hit it. Get the limit raised before launch, not during.

The three failure modes nobody writes about

1. KMS outage during the write path

This is the one that surprises teams. You designed the read path to tolerate KMS hiccups via cache. The write path cannot be served from cache — a new generation needs a fresh wrap, and even the steady-state write uses an active-write DEK that may not be in the local cache yet on a new pod.

When KMS goes down (regional outage, IAM misconfiguration, account-level throttle), writes start failing while reads keep working. Customers panic. Support escalates. Your dashboard looks fine because read traffic is healthy.

Three defenses, in order of how much we’d insist on each:

Pre-warm the cache on pod startup. When a pod boots, eagerly unwrap the active-write DEK for every tenant it might serve. Reject readiness until this completes. Pods that can’t reach KMS at boot never enter rotation. This is the single highest-leverage change.
Allow a write_unavailable mode that fails fast and explicitly. Writers see SQLSTATE 53300 (“KMS unreachable”) instead of timing out. Applications can queue, drop to a dead-letter, or retry with backoff — but they know what’s happening, instead of staring at 30-second timeouts.
Cross-region KMS replication. AWS multi-region keys, GCP multi-region key rings. Adds cost; removes the regional-outage failure case. Required for any customer that’s run a regional failover drill.

The defense we don’t recommend: a synthetic “emergency unwrapped DEK” fallback. It defeats the whole point of BYOK. Two customers asked for it; both withdrew the request after their security team read the runbook.

2. Key rotation in a multi-region setup

You read the rotation post and built a clean two-stage rotation. Now you have three regions, async replication between them, and BYOK. The rotation now has a subtle ordering bug.

The flow that breaks:

t=0   region A: promote generation 7 to active-write
t=1   region A: a row is written, encrypted under DEK_7
t=2   replication ships the row to region B
t=3   region B receives the row, tries to decrypt → fails

      because region B hasn't yet seen the keyring update
      that says "generation 7 exists and here's its wrapped DEK"

The fix is order-of-operations: the keyring entry for a new generation must replicate before any row written under that generation can replicate. RedDB handles this internally by treating keyring updates as a special replication record that flushes ahead of data records carrying that generation. If you’re integrating at a lower layer (e.g., custom replication), preserve this invariant or accept that cross-region reads will occasionally return decryption errors for the few seconds after a rotation.

The corollary: rotate during a quiet window the first time you do it on a new multi-region deployment, and watch the replication-lag-versus-keyring-lag metric. We expose both. They should never be reordered, but the time you find out they were is also the time you find out it matters.

3. The CMK is deleted (or scheduled for deletion)

Customer’s engineer fat-fingers a aws kms schedule-key-deletion on the wrong CMK. The customer panics. They cancel the deletion within the 7-day window (AWS minimum). Crisis averted.

Or: they didn’t notice for 8 days, and now the CMK is gone. Every row encrypted under DEKs wrapped by that CMK is unreadable. Forever. Including from your backups.

This is the actual, named threat that BYOK introduces, and it’s the customer’s responsibility — but you carry the operational scar of being the one who has to tell them. Three things to put in your runbook:

Monitor for kms:ScheduleKeyDeletion events on customer CMKs. Most customers will grant you the CloudTrail read permission for this; the ones that won’t, you note in their onboarding doc.
Page on any read that returns KMSAccessDenied or KMSDisabled above a threshold rate. This is the signal of a CMK being yanked.
Document that backups encrypted under a yanked CMK are unrecoverable. This sounds obvious. It is not obvious to everyone. Get sign-off in writing during onboarding.

HSM-backed: same shape, more latency

CloudHSM, GCP EKM, on-prem HSMs (Thales, Entrust) plug in at the KMS layer — either as the KMS provider (rare), or behind a CMK that’s configured to call into the HSM for every operation (common). From RedDB’s side it looks like a slow KMS. Three operational deltas:

Latency is ~10–50ms per unwrap, vs ~5ms for cloud KMS. Cache TTL matters more. We’ve seen customers set dek_cache.ttl: 4h for HSM-backed setups; verify with their security team.
Throughput is capped by the HSM. A single CloudHSM cluster does ~1,200 RSA ops/s. Plan capacity for peak unwrap rate, which happens during a cache cold-start after a deploy.
Failover is the customer’s problem. HSM clusters can lose quorum. Their runbook, not yours — but document the read/write impact when they do.

What to actually measure

If you operate BYOK in production, these five metrics catch 95% of the failure modes:

vault_kms_unwrap_seconds              (histogram, p50/p99 per tenant)
vault_kms_unwrap_errors_total         (counter, by reason: timeout, throttle, denied)
vault_dek_cache_hit_ratio             (gauge, per tenant)
vault_active_generations_count        (gauge, per tenant — should be 1 except during rotation)
vault_keyring_replication_lag_seconds (gauge, cross-region)

Page on:

vault_kms_unwrap_errors_total{reason="denied"} > 0 — almost always a yanked CMK.
vault_dek_cache_hit_ratio < 0.95 for 5 min — cache misconfigured or TTL too short.
vault_kms_unwrap_seconds{quantile="0.99"} > 500ms for 5 min — KMS is sick or HSM is overloaded.

The cache-hit-ratio alarm is the one that’s caught the most weird configs in practice. It’s cheap to wire up. Wire it up first.

The shape that ages well

BYOK is mostly boring once configured. The traps are the ones that show up months later when a customer rotates an IAM policy, deletes a CMK, fails over to a new region, or sells to a sub-organisation that wants its own CMK. The shape of the system that survives all of these:

Per-tenant CMKs from day one, even if you only have one tenant.
Cache TTL that matches the customer’s revocation expectation, documented.
Pre-warming on pod startup, with readiness gated on it.
Cross-region keyring replication that flushes ahead of data.
Alerts on KMSAccessDenied and on cache-hit-ratio drops.

None of these are interesting in a sales call. All of them are the difference between “BYOK works” and “BYOK works in production, for years, with no surprises.”

Per-row encryption with zero-downtime key rotation — the rotation mechanics this post assumes.
GDPR right-to-erasure when data is replicated and embedded — the cryptographic-deletion shape, fleshed out.
Self-hosting RedDB: the real-world checklist — where the KMS section in your runbook should live.