Is it secure to use the HMAC of a thing as salt for another HMAC?

Question

Problem

I'm trying to explain the full scenario in the next few paragraphs. I think this is important to get some context in which the question is asked, so please bear with me, even if it is a wall of text.

I'm currently tasked with anonymizing data in a secure way. The idea is to use HMAC(<string to anonymize>, key) to anonymize the data in so that it cannot be reversed. For example if you have a customer ID (CUST299128218) this would be HMAC-ed using SECRET as the key to 543a36dd07fe4a3fa4a2db202546eaaccaef71f871ebafe11de3b54784ba266e. Since we want to run analysis over the anonymized data it is important that the same customer ID always yields the same HMAC digest. So we cannot throw away the secret key as we need to anonymize future data with the same key.

The key obviously needs to be stored somewhere safe so it doesn't get out. Otherwise someone knowing a customer-ID could easily find that specific customer in the anonymized data. For various technical/organizational reasons we cannot use a hardware security module for storing the key. So I had a look at HashiCorp's Vault, which seems to be a nice fit for this as it provides a REST API where you can give it a plaintext and it returns the HMAC of this plaintext using a previously stored key. The key never leaves the Vault which is much better than having the key stored in some configuration property of the anonymization software.

However we're talking about large quantities of datasets to be anonymized (a few hundred thousand up to a few millions per day) and it is foreseeable that calling the Vault API for each dataset (possibly multiple times if multiple items need to be anonymized) will result in a ton of overhead that may overburden the infrastructure we have available for this.

Proposed solution

Therefore I had this idea: What if I used some fixed string (e.g. 'customer_id_secret_bootstrap') and let Vault create an HMAC on this using the secret key. Then I use this HMAC as secret key for the actual HMAC on the data to anonymize. In functional terms:

temp_key = CALL_VAULT('customer_id_secret_bootstrap')
anonymized_text = HMAC( <plaintext>, temp_key)

This way I could only do one call to Vault and keep the temporary key in memory. I should always get the same temporary key back from Vault (since it's an HMAC), but the original key (which is used to derive the temporary key) never leaves the vault and when the program exits, the temporary key cannot be re-created without accessing the Vault. So this way I would ensure the security of the key while not having a million calls to the Vault.

Question

Now knowing that I'm not a security expert by far, this may be a terrible idea for reasons unbeknownst to me. Therefore I'd like to run this with you experts here - can you tell me if this is a good or bad idea and if it is a bad idea could you suggest some alternative approach that would ensure the security of the key and be scalable?

Update/Edit

As many answers point out it is not sufficient to just replace the IDs as there are other fields which can be used to correlate information down to a small set of persons or even a single person (e.g timestamps are great for this). We also take care of this by removing or replacing such information to ensure that this cannot happen (we have a very long checklist regarding such things which is based on anonymization standards). I just didn't want to bring in those details here as the question is already very long-winded.

Answer 1

As Luc points out, you are probably already doing this better than most people. You deserve cred for caring about your customers privacy!

So we have three different systems here, in order of security:

1. Just use a secret key stored in some config.
2. Your system - using a vault in combination with a key stored in the config.
3. Just using a vault.

The problem with #1 is obvious. Any attacker that has access to your system can steal the key, and then use it to brute force hash values on their own computer. Thats bad.

With #2 you get some more security. Someone must break into your system and steal CALL_VAULT('customer_id_secret_bootstrap'). This is harder, because they have to grab it from the working memory and not from the disk. Plus it is only available when the system is running. So it will not accidentally end up on back ups etc. But an attacker who gets the secret can use it on their own system to brute force HMACs offline.

This is where #3 is stronger. An attacker who gains access to your system can't steal anything, because the key will not leave the vault. The attacker can try to crack hashes of customer IDs on your system by calling the vault, but they can not simply steal all the hashes and try to crack them in the privacy of their own home.

So while #3 is safer than #2, it is up to you to judge if the additional security is worth the price (in reduced performance, etc.). That depends on your threat model and how important the security of this information is.

Answer 2

Let me list the assumptions/situation:

• You have a big database with customer IDs, and other fields each customer.
• You want to anonymize this to run analyses. The organization will still know the original customer ID (you don't delete the original ID permanently), but the person doing the analysis will not.
• Other fields for the customer will also have to be anonymized.
• You are asking whether you can just use the anonymized customer ID as key for the other fields' HMAC.

The answer is no, this would not be secure. The person doing an analysis knows the anonymized customer ID and can just use it when brute-forcing other fields.

Another option is to just create a random key for each customer, and store this in the database with the customer's data. This means you don't need a "vault" or hardware security module: just read some bytes from /dev/urandom and store it with the customer data. Then use this as a key to anonymize other fields.

I imagine the database will look like this:

+---------+------------+------------+-------------------+
| ID      | Name       | Money      | Anonymization key |
+---------+------------+------------+-------------------+
| CUST999 | Jon Jonson | 3.14159265 | b2aZSo2D9erqwanrf |
+---------+------------+------------+-------------------+

Then to anonymize:

customer = database.read();
anon = new Customer();
anon.ID = anonymize(customer.ID, customer.AnonymizationKey)
anon.Name = anonymize(customer.Name, customer.AnonymizationKey)
anon.Money = customer.Money //Assuming you don't want to anonymize every field.
print(anon)

The anonymize(data, key) function could be an HMAC like you suggested. However, I think Stephane's comment is really good: they mention using a slow hash to prevent brute forcing. You could use a password storage algorithm (Bcrypt, Scrypt, Argon2, or PBKDF2, in no particular order) to make things more secure. Since you talk about a lot of records, though, I could imagine this is not possible (or only with low cost factors), but you can look into it.

By the way, lots of people try to just hash the customer ID (e.g. a phone number) so the marketing department can say with a straight face that it's anonymized, even though it's trivially brute-forceable. This is better already, since it involves a secret key. And on top of that, you're thinking of appropriate measures to really keep that key a secret. +1 for that!