HMAC ate my autocomplete: type-ahead search over encrypted emails

We encrypt user PII at rest with per-tenant keys, so that a leaked database dump exposes nothing useful. The email column is ciphertext. Phone numbers, names, custom attributes — ciphertext. We're proud of this. It's a selling point.

And the day it went live, the admin search box quietly stopped autocompleting.

No error. No log line. Type ali into user search and the tenant admin who used to see [email protected] pop up after three keystrokes now saw... nothing, unless they typed the entire email address, exactly. Search hadn't broken — it had silently degraded from "starts with" to "equals," and nothing in the system considered that worth mentioning.

This is the story of getting type-ahead back over data we refuse to store in plaintext, and the three traps we hit doing it. The cryptography turned out to be the easy part.

Why encryption eats autocomplete

With plaintext, prefix search is what databases are for. Keep an index ordered by email and starts with "ali" is a range scan: everything >= "ali" and < "alj". Cheap, obvious, done.

Encrypt the column and the ordered index is gone. The standard replacement is a blind index: alongside the ciphertext, store a keyed HMAC of the value, and look users up by recomputing the HMAC of the search term. HMAC(key, "[email protected]") is deterministic, so exact-match lookup works perfectly — and the index leaks nothing readable, because without the per-tenant key you can't compute a digest to compare against.

But notice what HMAC is for. Its entire design goal is that similar inputs produce unrelated outputs — flip one bit, get a completely different digest. HMAC("ali") and HMAC("alistair") have nothing to do with each other. The property that makes the blind index safe to leak is precisely the property that makes it unable to answer "starts with." Ordering is leakage. A blind index doesn't accidentally break prefix search; it breaks it on principle.

So the search box degraded to exact-match, silently, because exact-match was the only question the index could still answer.

The design: index every prefix as its own value

If the index can only answer "equals," then turn "starts with" into "equals."

Every prefix of the normalized email local part — the bit before the @ — gets its own blind-index row. For [email protected], that's rows for al, ali, alis, alist, and so on: PartitionKey = HMAC(prefix), RowKey = the user id. Now "starts with ali" is an exact-match lookup on HMAC("ali") — one point query, no ordering required. Our name search had already worked this way for the same reason; email just joined it.

Two constants keep it sane. Prefixes start at 2 characters (one-character lookups were never useful and double the rows) and cap at 16 (bounds the fan-out per email; a longer query just matches on its first 16 characters, and the handful of candidates get filtered after decryption). So each email costs at most 15 index rows — written on create, moved on email change, removed on delete.

That's the trade in one sentence: you buy back the ordering you refused to leak, and you pay for it in write fan-out. Storage and writes are cheap; leaked structure is not. It's a good trade.

One subtlety in the move-on-change path earned its own comment in the code: the prefix rows are keyed on the local part, so the rewrite has to trigger when the local part changes — independently of the domain. A same-domain rename, [email protected] → [email protected], looks like "domain unchanged, skip the index work" to a guard written with the domain index in mind, and would leave the old prefix rows pointing at the renamed user forever.

And to be honest about what we built: this index deliberately leaks prefix-equality — an attacker with the table can see that two users share a 3-character email prefix, though not what it is. Searchable encryption never eliminates leakage; it lets you choose it, consciously, per query shape. Equality and prefix-equality are the leakage we chose. That framing — pick your leakage, then engineer everything else around it — is the whole discipline.

The design worked. Then the systems problems started.

Trap one: the key that couldn't be created

Blind indexes need an HMAC key per tenant, provisioned in Vault's transit engine like our encryption keys. Creating one returned a 500: invalid key size for HMAC key.

Vault requires an explicit key_size for hmac-type keys — 32 to 512 bytes — where the fixed-size types (aes256-gcm96, ecdsa-p256) forbid it. Our key-creation call sent only {"type":"hmac"}. One missing field.

Here's why this was a trap and not a bug report: every tokenize operation threw — and the login path tokenizes, because finding a user by email at sign-in goes through the same blind index as admin search. Enabling encryption didn't break search. It broke login. The feature whose sales pitch is "your users are safer" took sign-in down on first enable in dev. The fix is key_size=32 (HMAC-SHA256) for hmac keys, omitted for the fixed-size types — and a standing rule: smoke-test the tokenize path against a real Vault before flipping encryption on anywhere. Mocks don't validate key-creation payloads.

Trap two: the update that could strand a user

Changing an email means index maintenance: remove the old rows, write the new ones. Our first implementation did it in that order — delete, then write. Natural, tidy, wrong.

Every new-row write now involves Vault (computing the HMAC PartitionKeys). Delete the old rows first, and a Vault hiccup during the write leaves the user with neither the old lookup rows nor the new ones. They exist, encrypted, in the table — and nothing can find them. Including login. That's not a degraded search; that's a locked-out user, until some future reindex sweeps by.

The fix is ordering, not error handling: write before delete, everywhere the index is maintained. A crash between the two steps now leaves an extra stale row — harmless, lazily cleaned — instead of a missing one. The failure mode moved from "user unreachable" to "one redundant row," for free. When a write path involves a remote dependency, pick the step order whose half-finished state you can live with.

Trap three: the partition that ate an import

We also keep a domain blind index — HMAC(domain) → members — so "everyone at acme.com" is one lookup. Deterministic hashing has a consequence nobody prices in until an import: every user of one domain lands in one partition. An Azure Table partition takes roughly 2,000 operations a second. A 50k-user single-domain import from Auth0 funnelled every domain-index write into exactly that bottleneck.

The fix is bucketing: members spread across 16 partitions by a hash of the user id, and domain reads fan out over the buckets — bounded, and rare enough not to matter. Two details carried the lesson. The bucket hash is a hand-rolled FNV-1a, because .NET's string.GetHashCode is deliberately unstable across processes — bucket by it and tomorrow's process computes a different bucket for the same user and can't find the row it's supposed to delete. And the read path still sweeps the legacy unbucketed partitions, so existing rows stayed findable with no forced backfill — new writes distribute immediately, old rows migrate whenever the user is next touched.

The lesson

Nothing in this story is novel cryptography. HMAC is decades old; "hash the value, index the hash" fits in a sentence. Everything that actually cost us was systems work: which query shapes the product genuinely needs (equality, prefix, domain — each got its own index, because a blind index answers exactly one question); how keys get provisioned and what happens on the login path when they don't; which order index writes happen in when a remote KMS sits in the middle; and where deterministic hashing concentrates load that plaintext never did.

Searchable encryption is sold as a crypto feature. Build it and you'll discover it's a distributed-systems feature wearing a crypto costume. The search box autocompletes again — ali finds Alistair after three keystrokes — and a stolen dump of the same table shows HMAC digests fanned across sixteen buckets, which is to say: nothing. Both at once was always the point.