Is this protocol for masking DB ids sound?

Question

Problem Statement

I don't want to expose my internal database ids (or other internal private ids) so to make it harder to abuse them, by e.g. guessing the next id of a sequence or similar. It is not feasible for me to add a new field with a public, non-guessable UUID for every entry in my DB. I therefore require a protocol that can mask my ids (reversibly).

Desired Properties

• Ids in a sequence should be hard to guess and recognize when masked
• Ids should be very hard to forge when masked
• compromise of a single masked id should not make it significantly easier to comprise other masked ids
• Masking the same Id should generate different outputs decided by chance
• Masked Ids should not be too long
• Masking should be reasonably fast

Current State-of-the-Art

There is a popular library that tries to tackle this issue: https://hashids.org/ with a e.g. Java implementation here. HashIds basically encodes the id with an specific alphabet which is dependent on a "salt" that is provided by the caller. Additionally they try to omit certain letters so the chance of generating an id with an english curse word is minimized. Ids are fully deterministic ie. the same number with the same salt creates the same output.

New Cryptographic Approach

I found the described issue interesting but was disappointed by the miserable security properties actually masking the id (to be fair HashId never claims to be more than obfuscation). My idea is probably similar a specialized version of key wrapping.

So my approach would be:

id         .... 8 byte number
entropy    .... 4, 8, 12, 16 byte random value
secret-key .... 16 byte high quality random key assumed to be stored in a safe manner

Primitives:
AES-CTR(iv, key)
HMAC_SHA256(key, data)
HKDF-Expand(PRK, info, L) -> OKM

1. For every id create a random byte array entropy between 4 to 16 bytes long.
2. Derive 64 byte key material km with HKDF-Expand(secret-key, entropy, 64)
3. Split the 64 bytes into:
   • roundSecretKey = km[0-16]
   • iv = km[16-32]
   • macKey = km[32-64]
4. Encrypt the id with AES-CTR(iv, roundSecretKey) -> encryptedId
5. Create mac with HMAC_SHA256(macKey, encryptedId | iv ) -> hmac
6. Truncate mac to 4-16 bytes -> truncated_hmac
7. Create output message with: masked_id = entropy | encryptedId | truncated_hmac

Discussion

AES-CTR as encryption primitive was chosen because:

• Basically every programming language has standard implementations for it
• Is a stream cipher and can efficiently encrypt data smaller than 16 byte
• AES can be reasonably fast (and is often hardware accelerated)

The big drawback is however that AES-CTR with key k1 must never be used with iv1 more than once.

HMAC is used to add integrity and authenticity for the generated id to prevent forging.

The random entropy part ensures that id1 masked multiple times will most probably create different masked ids.

Compromises

To keep the masked id short, entropy and the hmac is kept short (or very short depeding on configuration). Assuming the worst case: 4 byte entropy. The chance of a repeated iv is realistic, however seldom. The attacker should not be able to decrypt since the iv and the roundSecretKey is dependent on the secret secret-key which would requireing brute forcing it first. An option would be to switch to AES-CBC, but that would make the minimum output length 16 byte (most ids are either 8 or 16 byte).

Keeping the hmac small makes it easier to forge messages, however it should make it easier to get macKey.

Both of these issue can be solved by increasing the length of entropy and hmac to 16 byte. This would increase the output length to 40 byte however.

---

So the question to the community: Does this protocol make sense in accordance with the desired properties? Are the compromises reasonable? Is this basically a sound protocol. I am looking for general feedback, security issues, possible improvements - currently I am not looking for different ways to solve the public id issue.

---

Update for the interested reader: Here is the reference implementation of the id encryption schema on Github and here is a article about it.

Answer 1

What you are looking for is a randomized authenticated cipher of short bit strings, 64 bits long. You seem to be willing to accept between 64 and 256 bits of ciphertext expansion.

• With an $r$-bit randomization string, the probability of a collision after $n$ ciphertexts—which would, at the very least, reveal equality of masked ids—is at best bounded by about $n^2/2^r$.
• With $t$-bit authentication expansion, the probability of forgery after $f$ attempts is at best bounded by about $f/2^t$.

You could use any randomized authenticated cipher you like, e.g. NaCl crypto_secretbox_xsalsa20poly1305, which has a 192-bit nonce and a 128-bit authentication tag; if you use a 128-bit nonce chosen uniformly at random (padded with zeros up to 192 bits), you're safe as long as you limit yourself to well below $2^{64}$ ids, e.g. limit yourself to a billion ids. You could use AES-GCM, but the limits are even smaller because the nonce is 96 bits, so you need to limit yourself to well below $2^{48}$ ids. A nonce collision here is catastrophic, of course.

If you want to build it out of AES and SHA-256, you could just use AES-CBC with encrypt-then-MAC and the 128-bit truncation of HMAC-SHA256. Since the input is fixed-length, there's no need for padding; effectively, it would just be $$E_{k_1,k_2}(\rho, m) := c \mathbin\| \operatorname{HMAC-SHA256-128}_{k_2}(c), \quad \text{where} \quad c = \rho \mathbin\| \operatorname{AES}_{k_1}(\rho \oplus m).$$ In the case of a collision in $\rho$, this still leaks only equality of masked ids. Obviously, you can derive $k_1$ and $k_2$ from a single 32-byte master key $k$ with HKDF-SHA256.

Here's a very simple approach that uses a single call to AES with a single key, to encrypt a 64-bit id $m$ with 64-bit randomization $\rho$ under key $k$: $$E_k(\rho, m) := \rho \mathbin\| \operatorname{AES}_k(\rho \mathbin\| m).$$ Here $r = t = 64$, so we're using 192 bits to encrypt a 64-bit id. Let $\pi$ be a uniform random permutation; for any forgery attempts $\rho_1 \mathbin\| c_1, \dots, \rho_f \mathbin\| c_f$, the probability that there is any $i$ such that $\pi^{-1}_{64}(c_i) = \rho_i$ is bounded by $f/2^{64}$, where $\pi^{-1}_{64}(c_i)$ is the first 64 bits of $\pi^{-1}(c_i)$. Consequently, the distinguisher and forgery advantage of any algorithm against $E_k$ is bounded by $(n^2 + f)/2^{64} + \varepsilon$ where $\varepsilon$ is the best advantage at AES from a uniform random permutation. If you mask a million ids and your bandwidth limits the adversary to a trillion forgery attempts, the odds are less than one in eight thousand that the adversary will win. Even if there is a collision in $\rho$, again this only leaks equality of masked ids, although forgery might be a bigger issue.

What about the scheme you described? It's more complicated than necessary: you could do away with the IV, for example, and always use zero instead. If you use a 32-bit randomization string like you suggested, then you'll see a collision with high probability after only a few tens of thousands of ids, and when this happens, this leaks not only equality of two masked ids, but the xor of the two masked ids.