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
- For every
id
create a random byte arrayentropy
between 4 to 16 bytes long. - Derive 64 byte key material
km
withHKDF-Expand(secret-key, entropy, 64)
- Split the 64 bytes into:
roundSecretKey
=km[0-16]
iv
=km[16-32]
macKey
=km[32-64]
- Encrypt the
id
withAES-CTR(iv, roundSecretKey)
->encryptedId
- Create mac with
HMAC_SHA256(macKey, encryptedId | iv )
->hmac
- Truncate mac to 4-16 bytes ->
truncated_hmac
- 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.