0
$\begingroup$

We have a trusted application that observes sensitive identifiers, e.g. credit card numbers. We want to send data associated with these identifiers to an untrusted analytics service that will occasionally generate and send alerts back to the trusted application.

We've considered storing a table mapping sensitive identifiers to an opaque ID (e.g. UUID) to pass to the untrusted analytics service. But since there are billions of sensitive identifiers, the application can't store all the mappings due to storage constraints. We need the opaque ID to be stable over time, since the analytics service will be keying off of that to correlate data we send it. We also need the opaque ID to be reversible, so that the trusted application can determine what sensitive identifier was involved in an alert.

What we're planning on instead is to use a deterministic encryption scheme, though we're concerned about how well it fits our use case: often deterministic encryption is discussed in the context of key wrapping schemes, but the identifiers we see are far less random and have structure. On the other hand, we also see that chosen plaintext attack (CPA) is typically a concern, but in this case we aren't going to allow the attacker (i.e. the analytics service) to ask the telemetry service to encrypt arbitrary plaintexts.

We also don't want the untrusted analytics service to be able to figure out plaintexts or the key(s) used in a deterministic encryption scheme, even if it sees a large number of ciphertexts.

Given these constraints, what scheme best satisfies our use case? In particular, is AES-SIV applicable in this case?

|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ What is the expected format of these identifiers? Does it have to match the expected format of the untrusted application? For example, if the untrusted application is requesting a credit card number, does it have to look valid? Or can it be a random string of characters? $\endgroup$ – Daffy Jun 29 '17 at 2:08
  • $\begingroup$ No particular format is needed for the untrusted application. It just needs to be a stable identifier over time, and when the untrusted application sends back events the events will contain this identifier, which needs to be reversible by the trusted application. $\endgroup$ – Ben Jun 29 '17 at 3:11
  • 1
    $\begingroup$ If your plaintext can be represented in 16 bytes or less, AES-ECB is usable. Otherwise, any trusted deterministic algorithm works, like AES-SIV like you mentioned. $\endgroup$ – Daffy Jun 29 '17 at 3:24
  • $\begingroup$ Some identifiers are over 16 bytes. One question -- perhaps this is better as a different post -- is that RFC 5297 says this of AES SIV: "If, however, the nonce is reused SIV continues to provide the level of authenticity described above but with a slightly reduced amount of privacy" Should we be worried about "slightly" here? Is there a more rigorous description of how much privacy is lost? $\endgroup$ – Ben Jun 29 '17 at 3:56
  • 1
    $\begingroup$ While I'm not an expert, my somewhat educated guess on that is that the loss of privacy is the lack of IND-CPA, which I believe you indicated you don't care about. $\endgroup$ – Daffy Jun 29 '17 at 4:47
1
$\begingroup$

Yes, deterministic encryption would be a good solution to the problem you outlined.

Do however note, that an analytics service for credit card transactions will probably get information about payments like the time, location and amount. This can easily be used to create a profile for a specific ID. Given some extra information, for example from marketing companies, a deterministic ID can often be related to people. Whether this is an interesting consideration or not probably depends on the rest of the system.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ That's a very good point and one that's been on our minds. Do you have a specific recommendation for a deterministic encryption scheme? We are worried about the number of unique identifiers we will encrypt and if we will get too close to any security bounds of certain schemes. $\endgroup$ – Ben Jun 29 '17 at 16:12
  • $\begingroup$ That makes me uncomfortable. :) AES-SIV or AES-GCM-SIV should be fine. $\endgroup$ – Elias Jun 29 '17 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.