Facebook app-scoped identifiers and similar - implementing stateless ID obfuscation

Question

After certain privacy concerns Facebook rolled out a bunch of changes to their APIs, one being "scoping" user identifiers per app. In effect, this means that Alice's canonical facebook user ID is never shared through facebook APIs, but each app sees a unique never-changing value.

To formalize this through two functions:

• mask(user_id, app_id)
• unmask(masked_id, app_id)

These functions should satisfy some properties:

• reversible: user_id == unmask(mask(user_id, app_id), app_id)

• secret: given y = mask(user_id, app_id) it should be 'hard' to obtain the original user_id.

• deterministic: mask(user_id, app_id) == mask(user_id, app_id), where user_id == user_id and app_id == app_id

• collision resistant: for all user ids, given the same app_id, it should not be the case that mask(user_id1, app_id) == mask(user_id2, app_id)

After a lot of reading, I have come up with two possible implementations:

1. Stateful: store a triple (user_id, app_id, hash(user_id, app_id)).
2. Stateless: for each app_id generate & store a secret, and encrypt(user_id, secret) on the fly. the encryption should be a deterministic cypher, such as AES-SIV.

From the get go, I'd like to avoid a stateful implementation. I am not sure however as to the validity of the stateless approach as I'm not very familiar with deterministic symmetric cyphers, and their security implications.

Is there some other approach I might be missing here? I think this is a deceptively easy problem, looking forward to get some insight.

Answer 1

Reversible implies collision-resistant, as you have defined it. The criteria you have written down are essentially the criteria of deterministic encryption; if you add the criterion that it be hard for anyone without an app's key to forge a masked user id, then deterministic authenticated encryption[1] is exactly what you seem to be looking for.

If a user id is at most 64 bits, you could simply use AES itself as a deterministic authenticated cipher: $$\operatorname{mask}(\mathit{user\_id}, \mathit{app\_id}) := \operatorname{AES}_{k_{\mathit{app\_id}}}(0^{64} \mathbin\| \mathit{user\_id}).$$ The masked user id is 128 bits long. If, on decryption, you verify that the upper 64 bits are all zero, what you get is a deterministic authenticated cipher with distinguishing and forgery advantage bounded by about $2^{-64}$.