Repeatable encryption for pseudonymisation

Question

Is there a good way to do repeatable (with the same result) encryption for pseudonymisation where the pseudonym can be decrypted?

I want to set up a system to allow multiple services to communicate about subjects without them being able to join their data together themselves. They would send their requests through a "middleman" service which would translate the IDs to enable communication between the services.

So for instance, a score service and a user info service where the score service could ask for the user's first name without having to know the actual id for this user.

Because I don't want to store a large lookup-table for each service in the middleman I would like to generate the pseudonyms on the fly. So far I've looked at some RSA (OAEP) and AES (CTR, GCM) algorithms. The problem with these (I believe) is that they add some random padding or require a unique initialisation vector (which is there to prevent information about the key to be leaked) which makes the encryption non-repeatable. (Data stays the same but the result changes for every time we encrypt)

The data would be something like secret:service_uuid:object_type:object_id to make these unique for each object-service pair.

A (maybe ignorant) solution I came up with was to use something like AES and create iv from the data (d) by doing something like this:

$iv = hash(d) \bmod m$

Where m is the max value for iv

But I'm not sure if this compromises the strength of the encryption algorithm.

Long story short, I have not been able to find any "standard" to solve this, and I have the feeling I might be introducing some vulnerabilities by forcing some algorithm to do something it wasn't designed to do. Does anyone know if there is a better way to do this?

Answer 1

AES with $\text{IV}$ created from the data $d$ by $\text{IV}=\operatorname{hash}(d)\bmod m$, where $m$ is the max value for $\text{IV}$

That seriously compromises confidentiality, and does does not provide authentication:

• The $\text{IV}$ is typically in clear at the beginning of the cryptogram, and that allows someone without the key to test a guess of $d$, which is a total disaster for a login!
• Someone without the key can prepare a cryptogram that will decipher (at least, to garbage, but that can still be damaging, causing denial of service or worse, see below).
• If there is a test of acceptability of what's deciphered (e.g. a syntax check), that's ideal grounds for a padding oracle attack that might very well allow decryption without a guess (depending on details of the encryption, availability of a decryption oracle/server, test of acceptability and insight on its result an adversary gets thru side channels like error codes, network states, or timing).
• Depending on AES mode and availability of valid cryptograms with known plaintext, someone without the key may be able to prepare cryptograms that will decipher to something under control of the attacker.

Making symmetric encryption deterministic (the academic name for "repeatable") is bound to allow a test that two messages are identical by comparing the ciphertexts, but all other drawbacks can and should be avoided.

---

A good option would be a Nonce-Misuse-Resistant Authenticated Encryption with a public fixed nounce, e.g. the key index (symmetric keys should be rotatable, and identified by key index for this purpose).

A modern such scheme is AEAD_AES_256_GCM_SIV of RFC 8452. We are straight in the designed-in usage: "encrypting two messages with the same nonce only discloses whether the messages were equal or not". The theory behind the scheme is described in Shay Gueron and Yehuda Lindell's GCM-SIV: Full Nonce Misuse-Resistant Authenticated Encryption at Under One Cycle per Byte, in proceedings of CCS 2015.

If performance is not an issue, there are ways to obtain similar functionality from more available primitives, such as a hash and/or an encryption-only mode of operation. Edit the question stating available primitives if that's needed.