BYOK Done Right: Encrypting Per-User Provider Keys

The first BYOK design we shipped at AllRoutes was wrong. Not insecure-by-default wrong, just wrong-enough that I rewrote it three weeks after launch. This post is the design we ended up with, why the obvious approach is not enough, and what specifically we got wrong on the first attempt.

The setup: customers want to bring their own OpenAI/Anthropic/Google keys and have AllRoutes use those keys when proxying requests. They want this for two reasons. First, they already have provisioned spend with the upstream provider and do not want a second contract. Second, they want their usage to count against the provider's quota and rate limits, not ours.

This means we need to store provider API keys server-side and use them on every outbound request. Storing them in plaintext is a non-starter. Storing them encrypted is necessary but not sufficient — the question is how, and the details matter.

The threat model

Before designing the encryption, we wrote down what we were defending against:

1. Database compromise. An attacker dumps the Postgres provider_keys table. They should learn nothing.
2. Backup compromise. Same as above for any backup, snapshot, or replica.
3. Application compromise. An attacker gets RCE on a gateway pod. They can read process memory and exfiltrate keys actively in use, but should not be able to mass-exfiltrate the entire vault.
4. Insider read access. An engineer with psql access to production should not be able to read customer provider keys.
5. Compromised cloud account. This is mostly out of scope — if AWS root is compromised, the threat model is "the attacker owns everything." We accept this.

Threat 3 is the interesting one. A naive encryption scheme — single key, decrypt at startup, hold all decrypted keys in memory — defends against threats 1, 2, and 4 but completely fails threat 3. An attacker with RCE can dump the in-memory key map and walk away with every customer's provider keys.

Envelope encryption

The pattern we used is envelope encryption, which is well-known but worth describing concretely:

1. Each provider key is encrypted with a unique data encryption key (DEK) generated at upload time. The DEK is a 256-bit AES-GCM key.
2. The DEK is itself encrypted with a key encryption key (KEK) managed by AWS KMS. We never see the KEK in plaintext.
3. We store, in Postgres, the encrypted provider key plus the encrypted DEK plus the KMS key ARN. Three columns, all encrypted.
4. To use a provider key, the gateway calls KMS to decrypt the DEK, then uses the DEK to decrypt the provider key, then uses the provider key for one outbound request, then zeroes the buffers.

This defends against all five threats meaningfully:

• DB or backup compromise: the rows are useless without KMS access.
• Application compromise: the attacker can decrypt one key per gateway request they observe, but cannot mass-decrypt without making an API call to KMS for each one. KMS has CloudTrail logging and rate limiting, so a sustained mass-decrypt attempt is detectable and rate-bounded.
• Insider DB read: same as DB compromise.

The key insight is that KMS is a network call, not a local key. An attacker who steals a memory snapshot does not get the KEK, and CloudTrail records every decrypt operation. If we see 50,000 KMS decrypt calls in an hour from a single gateway pod, an alert fires.

What we got wrong the first time

The first version had two problems.

Problem 1: We cached decrypted keys in memory for 5 minutes. The reasoning was "KMS calls cost money and add latency, and most customers reuse the same key on every request, so let's cache." This was correct on cost and latency and wrong on threat 3. A 5-minute cache means an attacker with RCE gets a 5-minute window to dump every active key.

The fix: we removed the cache entirely. Every outbound request does a fresh KMS decrypt. The cost increase was negligible (KMS decrypt is around $0.03 per 10k operations) and the latency added 4ms p50, which we made up for elsewhere. The CloudTrail log per request also turned out to be a nice audit feature, which is now part of the BYOK product surface.

Problem 2: We used one KMS key per environment, not per customer. This meant a single KMS policy controlled every customer's keys. If we accidentally granted decrypt to the wrong IAM role, every customer was exposed.

The fix: each customer gets their own KMS key (kms_key_arn column on the tenant row). KMS keys are cheap ($1/month each) and the per-customer isolation lets us do per-customer key rotation, per-customer key disable in case of contract termination, and per-customer CloudTrail filtering. This also gave us a clean answer to "what happens when a customer leaves" — we delete their KMS key and every encrypted artifact that depended on it becomes permanently unrecoverable, which is the right behavior.

The current schema

Roughly:

CREATE TABLE tenant_kms_keys (
    tenant_id UUID PRIMARY KEY,
    kms_key_arn TEXT NOT NULL,
    created_at TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

CREATE TABLE provider_keys (
    id UUID PRIMARY KEY,
    tenant_id UUID NOT NULL REFERENCES tenant_kms_keys(tenant_id),
    provider TEXT NOT NULL,           -- 'openai', 'anthropic', etc
    label TEXT NOT NULL,              -- user-facing name
    encrypted_key BYTEA NOT NULL,     -- AES-GCM(provider_key, dek)
    encrypted_dek BYTEA NOT NULL,     -- KMS.encrypt(dek, kms_key_arn)
    iv BYTEA NOT NULL,                -- AES-GCM nonce, 12 bytes
    auth_tag BYTEA NOT NULL,          -- AES-GCM auth tag, 16 bytes
    created_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    last_used_at TIMESTAMPTZ
);

The iv and auth_tag columns are explicit because we use AES-GCM, and accidentally reusing an IV with the same key catastrophically breaks the security guarantee. Generating a fresh IV per encryption (which we do, via crypto.randomBytes(12) at upload time) is not optional.

The decrypt path

The hot path on a customer request is:

async def get_provider_key(tenant_id: UUID, provider: str) -> str:
    row = await db.fetch_one(
        "SELECT encrypted_key, encrypted_dek, iv, auth_tag, kms_key_arn "
        "FROM provider_keys "
        "JOIN tenant_kms_keys USING (tenant_id) "
        "WHERE tenant_id = $1 AND provider = $2",
        tenant_id, provider,
    )
    if row is None:
        raise NoKeyError()

    # KMS round-trip: ~4ms p50, ~12ms p95
    dek = await kms.decrypt(
        CiphertextBlob=row["encrypted_dek"],
        KeyId=row["kms_key_arn"],
    )

    # Local AES-GCM decrypt: ~10us
    cipher = AES.new(dek["Plaintext"], AES.MODE_GCM, nonce=row["iv"])
    plaintext = cipher.decrypt_and_verify(row["encrypted_key"], row["auth_tag"])

    return plaintext.decode("utf-8")

We zero the dek and plaintext buffers as soon as the outbound request completes. Python makes this annoying because string immutability means we cannot truly zero the bytes, but we use bytearray and secrets.compare_digest patterns where it matters.

What we still want to improve

A few things on the roadmap:

• HSM-backed KEK option. For enterprise customers, we want the KEK to live in a CloudHSM cluster rather than a KMS-managed key. Same envelope pattern, stronger isolation.
• Key rotation automation. Right now key rotation is manual: customer uploads a new key, we mark the old one inactive, traffic shifts. We want a "scheduled rotate" feature where customers schedule a rotation window and the new key gets phased in over an hour.
• Confidential compute. Eventually the gateway should run inside an enclave so memory exfiltration becomes meaningfully harder. Not on the immediate roadmap but on the radar.

If you are storing provider API keys today, audit your design against the threats above. The path from "encrypted at rest" to "actually safe under realistic threats" is longer than it looks. The BYOK setup guide walks through the customer-facing side.