At ConsentKeys I designed how we generate pairwise subject identifiers for OpenID Connect. This note covers what the spec leaves open, the constraints we had to meet, why we went with HKDF and per-app salts, and the two problems that took the most design time: rotation, and customers who want to link their own apps.
What the spec leaves out
OIDC defines two subject identifier types. With public, every client sees the same sub for a user, so two apps can compare their user lists and match people up. With pairwise, each client (strictly, each sector identifier) gets its own opaque sub, and comparing lists tells them nothing.
The spec gives an example derivation: hash the sector identifier, the local account ID and a salt together. It doesn't say what the salt should be, where it's stored, how it rotates, or what happens to existing users when any of that changes. Pairwise IDs are the core of what ConsentKeys does, so we had to answer all of those ourselves.
The four constraints
- Deterministic. The same user at the same app gets the same
subevery time, across deploys, migrations and database restores. No mapping table as the source of truth. - Uncorrelatable. Two clients comparing their full user lists learn nothing, even if one of them can make unlimited queries.
- Fast. The derivation runs on every token issuance, not once at signup, so it has to fit inside the token endpoint's latency budget.
- Recoverable. If a key is suspected compromised, we need to be able to replace it without changing any user's
sub.
Options we ruled out
A mapping table. Generate a random opaque ID for each (user, app) pair and store it. It's easy to reason about, but the table becomes the identity system. It grows with every pair, and a restore that loses a row loses that user at that app. That breaks the first constraint.
Deterministic encryption. Encrypt the local account ID per client with something like AES-SIV. That's deterministic and needs no table, but it's reversible. Anyone holding the key can decrypt a sub back to the real account ID, so a key leak means full de-anonymisation instead of a correlation risk.
The spec's hash with one global salt. This is the right general idea, but a single global salt is one secret whose leak breaks uncorrelatability for every app at once. A bare hash also gives us no clean way to separate contexts or rotate.
Why HKDF
HKDF (RFC 5869) has two steps. Extract takes a master secret and a salt and produces a pseudorandom key. Expand takes that key and an info parameter and produces output bound to that context.
We use HKDF with SHA-256. Each app's salt goes into the extract step as the HKDF salt, and the sector identifier and local account ID go into info in the expand step. The master secret and the salts are kept in an HSM.
The properties we needed are ones HKDF already gives you. Outputs for different contexts are computationally independent, so colluding clients can't link users without the master secret. Because each app has its own salt, the blast radius of a leaked salt is that one app's namespace. And the whole derivation is a few HMAC calls with no database lookup. We also run it on workers, which keeps it comfortably inside the latency budget.
Rotation
Changing the master secret or an app's salt changes every sub derived from it. From the client's side, every user disappears and is replaced by a new one, and their existing accounts at that app stop matching.
So at ConsentKeys the master secret and the per-app salts are designed never to change. What we rotate are the HSM keys that wrap them. Rotation adds a new wrapping key and sweeps out the oldest ones, which doesn't touch any derived sub. We've run it in production.
Restores matter here too. Since nothing is stored per pair, a restore can't lose IDs, but it does need the same master secret and salts available, so key backup is part of the database recovery plan.
Customers who want to link their own apps
Some customers run two apps and legitimately need the same user to have the same ID in both. The spec already covers this with the sector identifier: register both apps under one sector and they get the same sub. The linking is declared up front and visible.
We don't link users across two sectors after the fact. If a customer registered two apps separately and later wants their users matched, that's the kind of correlation pairwise IDs are there to block, so we won't do it.