Skip to content

Single HMAC Strategy

The Single HMAC Strategy

One column per HMAC

Introducing HMACs covered why a HMAC is what you actually search and enforce uniqueness on. The simplest possible design for storing one: one HMAC column per field, holding a single HMAC value, sitting alongside the encrypted record — a USERNAME_HMAC column next to the userName ciphertext, a PAN_HMAC column next to the pan ciphertext, and typically a column recording which HMAC key produced them, which rekeying (encryption, HMACs) needs later to find what's stale.

It's the design many applications default to — simple, relational-DB-friendly, no join required — but it inherits both of the HMAC key rotation challenges head-on.

The HMAC itself is unremarkable: a keyed hash, computed with whatever key happens to be current.

public String hmac(String value, SecretKey key) {
    try {
        Mac mac = Mac.getInstance("HmacSHA256");
        mac.init(key);
        byte[] digest = mac.doFinal(value.getBytes(StandardCharsets.UTF_8));
        return HexFormat.of().formatHex(digest);
    } catch (Exception e) {
        throw new IllegalStateException(e);
    }
}

The search problem

Rotate the HMAC key and every existing record's HMAC was computed with the old key. A search hashes the term with the new key and gets a different value — the row simply isn't found, even though it exists. Play through the sequence:

  1. You change the HMAC key.
  2. All searches going forward use the new key.
  3. Immediately, none of your existing records are findable — their HMACs were all computed with the old key.
  4. A background job starts rekeying record by record.
  5. Search results gradually improve as the job progresses.
  6. Only once the job finishes is search fully back online.

A single HMAC key per tenant means a rotation causes a functional search outage for however long the rekey takes. Most production systems can't tolerate this, and it's unavoidable with only one active key. The naive search itself hashes with whatever key is current, and nothing else:

/** Naive search: hash the term with whatever key is current right now, and look it up. */
public List<UserRecord> findByUsernameHmac(String usernameHmac) {
    return rows.stream().filter(r -> r.usernameHmac().equals(usernameHmac)).toList();
}

A partial fix exists: a key start time. Application instances typically cache their key configuration rather than reloading it on every request, so a newly introduced key doesn't reach every instance at once — it only takes effect, instance by instance, as each one's cache refreshes. A key start time accounts for this by setting the new key's start time to "now + the key cache duration," and holding off using it for writes until that time passes — guaranteeing every instance has picked it up before any of them relies on it. Searches, meanwhile, don't need to wait: as soon as an instance reloads its config and sees the new key, it starts hashing search terms with every known key, old and new, immediately. Because no record gets written with the new key until every instance is guaranteed to know about it, every record — old or freshly written — stays findable throughout.

The unique constraint problem

This is the more consequential of the two. Say userName has a DB-level unique constraint on its HMAC column. Walk through it:

  1. A user exists with username john.doe@test.com, HMAC'd under the old key.
  2. The HMAC key changes.
  3. A request comes in to create a new user with the same username, john.doe@test.com.
  4. Its HMAC is computed under the new key — a different value than the existing record's HMAC.
  5. The unique constraint doesn't fire, because the two HMAC values genuinely differ.
  6. Two users now exist with the same username.

Adding key start time doesn't fix this — it only narrows the window to a race condition, and even that requires an extra step: searching for the value under every known key before every write, to catch a record that might already exist under an old key. That search-before-write step has its own performance cost, and it makes the database's own unique constraint largely redundant for the cases it's meant to catch, since the application is now the one enforcing uniqueness. Even with it, a race remains: two requests for the same username, arriving on either side of the key-start-time boundary, can each search first, find nothing, and then write concurrently — one under the old key, one under the new one — leaving the same username duplicated in the system.

The write path that lets this happen: a plain unique index on the single HMAC column.

public void createUser(String username, String usernameHmac) {
    // Mirrors a DB unique index on USERNAME_HMAC: it can only ever see the hash
    // value itself, so two different hashes for the same underlying username
    // look, to the constraint, like two entirely unrelated rows.
    if (!uniqueHmacIndex.add(usernameHmac)) {
        throw new UniqueConstraintViolation("username_hmac already exists: " + usernameHmac);
    }
    rows.add(new UserRecord(username, usernameHmac));
}
View on GitHub

The constraint only ever sees the hash value, so createUser() for the same username under two different keys looks, to the index, like two entirely unrelated rows. See talk/naive-single-hmac/ for the full runnable demo that reproduces both the search outage and the duplicate.

Verdict
Pros Simplest possible design; relational-DB-friendly single-table layout; no extra write-path cost (one HMAC per attribute per write); little room for process error during a rotation
Cons Cannot support unique constraint enforcement and key rotation without serious drawbacks; without key start time, rotation causes intermittent search outages; even with it, unique constraint support costs performance and still can't guarantee integrity under all circumstances

If your application needs uniqueness enforced on any encrypted field, the Single HMAC Strategy is a design you'll eventually need to move away from. List HMAC Strategy covers the strategy that solves both problems.