Engineering · 2026-08-13

Keying Every Identifier Hash Without Breaking Correlation

By J. W. Bouckaert

The claim that has to be earned

"We store only irreversible hashes of personal identifiers" is one of the most common sentences in privacy documentation, and one of the least examined. Whether it is true depends entirely on what is being hashed and how. For a random 256-bit API key, an unkeyed SHA-256 digest genuinely is one-way in every practical sense. For a phone number, it is close to a plaintext copy with extra steps.

This post is the engineering story of making that sentence true at PasskeyBridge: moving every low-entropy personal identifier we store, phone numbers, email addresses, CAEP subjects, IP addresses, and behavioral fingerprints, from unkeyed SHA-256 to keyed HMAC-SHA-256 under a server-held pepper, without breaking the deterministic correlation the whole platform depends on. Including the parts that could not be migrated, because honest scope is part of the control.

The arithmetic of enumeration

A cryptographic hash is one-way only when the attacker cannot afford to try every input. That premise holds for high-entropy inputs and collapses for identifiers, because identifier keyspaces are small:

Input class                 Keyspace (order of magnitude)
────────────────────────────────────────────────────────
256-bit API key             2^256  (enumeration is fantasy)
IPv4 address                2^32   ≈ 4.3 × 10^9
NANP phone number           ~10^10 valid combinations
Email addresses             not enumerable in general, but
                            attackers hold billion-row breach
                            corpora: a dictionary lookup
────────────────────────────────────────────────────────

A commodity machine computes SHA-256 at hundreds of megahashes per second per core without trying hard; GPU rigs add three orders of magnitude. Against a 2^32 IPv4 space, an unkeyed digest is reversible on a laptop in minutes. Against the phone-number space, an attacker builds the rainbow table once and looks up every phone digest they ever encounter, forever. Against email, the breach corpora circulating publicly are the dictionary.

Hashing itself is fine. What the arithmetic shows is that an unkeyed hash of a low-entropy identifier is a pseudonym and never an irreversible transform, and any copy that claims otherwise is writing a check the math will bounce. Under GDPR's definition of pseudonymisation, data that can be re-attributed with reasonably available means is still personal data, and "hash the phone number" without a key is exactly that.

Salts do not help

The reflexive answer is "add a salt," imported from password storage. It fails here in both directions, and the failure is instructive because it explains the actual design constraint.

A random per-record salt destroys correlation. Password hashing wants every stored digest to be unique even for identical inputs; that is what the salt is for. An identity platform wants the opposite: the same phone number arriving in a carrier webhook today and an authentication request next week must produce the same digest, or nothing can be matched to anything. Deterministic equality is the product. Random salts are correctness bugs here.

A shared or derivable salt adds nothing. A single global salt, or a rotating date-based one, preserves determinism but is public knowledge the moment the system is inspected. An attacker who knows the salt scheme rebuilds the enumeration table with the salt included. Our behavioral fingerprints use a daily salt to unlink days from each other, and the design documentation is blunt that this salt is a linkability control with no bearing on enumeration. It never was one.

What the system actually needs is a function that is deterministic for us and unpredictable for everyone else, and the name for that is a key.

Keyed and deterministic: HMAC under a pepper

The construction that shipped is HMAC-SHA-256 with a single server-held secret, the pepper, as the key. Properties, in the order they mattered:

Equality survives, precomputation dies. The digest is deterministic under the pepper, so correlation works exactly as before. Without the pepper, no rainbow table can be built and no candidate input can be tested. A leaked digest column now discloses equality relationships, same identifier, same digest, and nothing else. Equality is the property we need; it is also the only one we keep.
Drop-in shape. Output is 64 lowercase hex characters, the same shape as a SHA-256 hex digest, so every existing column, index, and format validator kept working unchanged. Migration cost lives in the write paths.
Identifier classes are domain-separated. The identifier's class (phone, email, subject, IP, fingerprint) and a version tag are bound into the HMAC message alongside the normalized value. The same raw string used as two different identifier types yields unrelated digests, so a cross-type join can never happen by accident.
Normalization happens before hashing, per class. Phone numbers are reduced toward E.164. IP addresses are lowercased and stripped of the bracket-and-port decorations proxies append, so [2001:DB8::1]:443 and 2001:db8::1 correlate as one host. Emails and subjects are trimmed and lowercased. A digest function is only as deterministic as the canonicalization in front of it.

One subtlety worth stealing: the helper that hashes IP addresses returns null for placeholder values, absent addresses, "unknown", per-request anonymous buckets, instead of hashing them. Hashing a placeholder manufactures a digest that looks like an identifier and identifies nothing, and every downstream correlation, insider-threat "new IP" detection especially, would count each one as a brand-new host. Refusing to hash nothing is part of hashing something.

Version stamps

Every stored digest now carries a hash version: version 1 is a legacy unkeyed SHA-256, or a digest a tenant computed client-side and sent to us pre-hashed; version 2 is a server-side keyed HMAC. The stamp makes every row self-describing, and it draws a line the copy has to respect: version-1 digests are never cited in a privacy claim. They are enumerable, and no amount of adjacent good engineering changes that.

Here is the part most migration stories omit: version-1 rows can never be upgraded in place. Re-keying a digest requires the plaintext, and the plaintext was never retained, by design, the same design the whole control exists to serve. The zero-PII property that makes the platform defensible is precisely what makes its own history unfixable. Legacy rows age out on retention schedules instead. The one exception was a migration path that briefly held plaintext at migration time anyway, and could therefore re-key what passed through it honestly.

If you are planning the same migration: accept this before you start, budget for the aging-out window, and write the version stamp from day one so the boundary between the old world and the new one is a database fact rather than a guess.

Fail closed

The hashing helper throws when its pepper is missing or too short. It does not log a warning and fall back to an unkeyed digest.

This was debated and is worth defending, because the alternative feels safer and is not. A privacy control that silently turns itself off is worse than one that is absent: the stored version stamp would say "keyed" while the bytes said otherwise, and every downstream claim, documentation, audit evidence, breach-notification analysis, would inherit the lie. An outage is visible and fixable. A quiet downgrade is a false compliance record that compounds daily. Presence of the pepper is checked by the platform's self-tests, so the failure mode surfaces in monitoring rather than in production surprise.

Rotation without a flag day

A pepper you cannot rotate is a pepper you will one day be unable to revoke. But rotating it changes every future digest, which would orphan every stored one. The shipped protocol:

The outgoing pepper moves to a previous-pepper slot; the new pepper takes over all writes immediately.
Equality-matching reads compute candidate digests under both peppers for the overlap window, so rows written under the old pepper still match.
When every equality-matched row from the old era has aged out or been rewritten, the previous pepper is cleared and the window closes.

Steady state costs one HMAC per lookup, identical to before; only the rotation window pays for two. One implementation detail that earns its keep: the imported HMAC key is cached by the pepper's value rather than as a singleton, so a rotation takes effect on the very next call in an already-warm serverless isolate instead of waiting for the isolate to recycle.

Deliberately unkeyed

A migration that keys everything indiscriminately breaks things that were correct. Three classes stayed on plain SHA-256 on purpose:

High-entropy secrets. API keys, agent and bearer tokens, DPoP access tokens. Their keyspace is 2^256-shaped, so unkeyed digests are not enumerable, and they are looked up by digest: re-keying would invalidate every stored hash for zero privacy gain.
Content digests. Payload hashes, provenance hashes, canonical JCS digests. These exist so an independent party can recompute and verify them. A keyed digest is verifiable only by the keyholder, which destroys their entire purpose.
Credential-subject identifiers inside signed artifacts. DID-class subject values feed content-addressed composites embedded in already-issued signed provenance. Keying them in place would break historical correlation and the signature semantics of artifacts that already exist. They are DID-class strings well outside the phone/email enumeration class, and they stay as they are.

And one audit finding worth passing on: a column whose name ended in _hash turned out to be populated from a plaintext column, the name claimed a digest, the bytes were an address. The rule that survives is: audit what flows into a column rather than its name. Renaming is not hashing.

No pepper in a client

An SDK cannot hold the pepper. Ship a server secret in a browser bundle or a mobile binary and it becomes a slow disclosure.

The consequence is a real API-design fork. Our ingest path still accepts a client-computed phone hash for backward compatibility, but such digests are stamped version 1, enumerable, excluded from privacy claims, and, because the client's unkeyed digest can never equal the server's keyed one, they correlate only with other client-hashed values. Tenants who want the actual property send the raw identifier over TLS and let the server key it. "Hash it client-side so the vendor never sees it" sounds privacy-preserving and quietly buys the weakest version of both worlds: enumerable digests and broken correlation. The pepper draws the boundary: the keyed transform happens where the secret lives.

One pepper, or one per tenant

The pepper is global, one secret for the platform rather than one per tenant, and that was a deliberate choice. Per-tenant peppers would make the same identifier produce different digests in different tenants, which sounds like isolation and is, but it would also make cross-tenant threat correlation structurally impossible. The platform's anonymized threat-sharing depends on recognizing that the same (hashed) identifier is being attacked across multiple tenants without knowing what the identifier is. Same pepper, same digest, correlation without disclosure.

The cost of that choice is concentration: one secret now underwrites the enumeration resistance of every identifier digest on the platform. Which is why pepper custody graduated from an implementation detail to a first-order control: it lives in the platform secret store and never in the database, so a database compromise yields ciphertext, digests, and no pepper; its presence is monitored; its rotation is a rehearsed procedure rather than an aspiration. That custody story is audit evidence now, ask us about it in a security review and you will get the runbook.

Boundary of the control

The honest boundary of the control, stated plainly:

Equality still leaks structure. A leaked digest column reveals which rows share an identifier, graph shape, frequency, co-occurrence, even though it reveals no identifiers. For our threat-sharing design that equality is the feature; your threat model may differ.
The property is conditional on the pepper. If the pepper itself is compromised, keyed digests degrade to exactly the enumerable case the migration fixed. The claim is "irreversible without the pepper," custody is what makes the qualifier small.
Version-1 history is what it is. Legacy and client-supplied digests remain enumerable until they age out. We stamp them, exclude them from claims, and wait, there is no third option that does not involve retaining plaintext we never kept.
This is pseudonymization, and it is not encryption. Nothing here can be decrypted back, by us or anyone. That irreversibility is the property the control exists to provide, and it is also the limitation.

If you are making a zero-PII claim anywhere in your own product, the one-sentence audit is: for every stored digest, what is the keyspace of its input, and where does the key live? If the answer to the first is "small" and to the second is "there is no key," the claim is marketing. It took us a version stamp, a pepper, a fail-closed helper, and an aging-out window to make ours engineering. The broader architecture this control lives inside is documented in our zero-PII architecture post and the CISO guide to zero-PII verification; the compliance surfaces it feeds, processing phone-derived signals without storing numbers and signal residency under Schrems III, are covered separately. The mechanics above are in production today; the docs describe the tenant-facing surface, including exactly what to send raw and what arrives pre-hashed at your own risk.

Start free · Test the API