How to properly anonymize data, if hashing isn't enough?

Today there are news on Bruce Schneier's blog and ArsTechnica about how NY City released information about Cab/Taxi drivers, their trips, and so on.

Basically, sensitive information was simply MD5 hashed. Since the input was limited (3 numbers, 3 letters, at most), it was easy to make some brute-force attack: generate all possible combinations and then do a look-back.

Considering the nature of the information (very small input, to easy to generate all combinations), how could this data be properly anonymized?

Some approaches that have occurred to me::

• Security through obscurity (use a "secret" number of iterations) is just security through obscurity.

• Append a general, unique salt, would increase the brute-force by 0%: simple append the salt and done.

• Appending a unique salt per user, would increase the brute-force, but not too much: take the salt and calculate the 3 digit 3 letters for each salt.

What could be done?

-
It's worth reading down the comments on the Schneier post. Not all of them are correct, but in particular note that the data probably cannot be anonymized just by concealing the plate number because the data itself contains identifying trends. This is by the same principle that if you publish location data for mobile phones but "anonymize" the number, then someone can still trivially use it to track me because my phone is one of only two that spend most of their time in my house. The identity can be de-anonymized if you can characterize whoever you're looking for. – Steve Jessop Jun 25 '14 at 21:52
This question is unfortunately too broad to answer here. People have written entire dissertations and books on how to anonymize sensitive data. The short answer is, it's famously difficult, and the way to anonymize data will depend upon the nature of the data that you want to anonymize and the degree of anonymity/privacy that is desired. You might like to look at de-identification, the Netflix challenge, differential privacy, Arvind Narayanan's blog, and this CACM article. – D.W. Jun 25 '14 at 22:10
I suggest you edit your question to focus on a specific situation, and give us information about that situation (e.g., what information you want to reveal and what you don't). Do you want us to answer about only the taxi database? Or do you want us to answer in general about all situations where hashing is insufficient? Right now it sounds like you are asking about the latter, but that is too broad. A question about a single specific situation would be more suitable for this site. – D.W. Jun 25 '14 at 22:11
@D.W. your edit was perfect. – woliveirajr Jun 26 '14 at 15:40
@woliveirajr, unfortunately I'm afraid I wasn't able to address any of the issues raised in my comments above. All my comments still apply: we still need to know the specific situation to know how to anonymize. – D.W. Jun 26 '14 at 15:51

You can use tokenization. Meaning you create a seperate database with randomly generated IDs mapping to 3 numbers and 3 letters. You then insert the token instead of the real identity.

Another option, if you don't need to map the data back, you can use, for instance, a HMAC (hashing algorithm) with an long random generated secret. Without the secret you can't bruteforce the original IDs, even when they even only consist of 1 single character.

Using a HMAC is actually the correct way of using a "secret salt" (a salt is actually never considered secret in cryptohraphy).

-
HMAC (or any other secret-based hashing scheme) has the same issue as using a salt, if the secret gets compromised BOOM goes the dynamite. I think the OP is assuming that happens. – sazr Jun 25 '14 at 14:59
The point is that you do not supply the secret along with the anonymized report. Using a secret and throwing it away is the same as using a salt and throwing it away, except that a HMAC is the correct way of doing so. If you are supplying the secret, why bother using it at all? I mean any algorithm will be broken if you supply the key. The only other way then is tokenization. – Lucas Kauffman Jun 25 '14 at 15:16
Oh my bad, I assumed the company needed to be able to replicate the operation. If it's a one time thing then HMAC is definitely the way to go! – sazr Jun 25 '14 at 16:10
What about giving each row a random salt, rather than one table-wide salt? – AlexQueue Jun 25 '14 at 21:25
@AlexQueue: if you do that then there's no point hashing. Just use the "random salt" as the ID, i.e. tokenize. – Steve Jessop Jun 25 '14 at 21:46

The way to not release the data is to not release the data.

Tokenization wouldn't work very well, because all I have to do to know everywhere and when a driver was is to know anywhere and when a driver was, and then I know that driver's token.

If you don't want me to be able to figure this out, then don't release that data in any form.

-

If the input is that limited you will always have this problem.

The only solution is for you to add more "stuff" to diversify the input. As you said the salt is an option, but if it's compromised it won't do much good. Same thing goes for using secret keys or passwords.

``````Nonce | Driver Name | Driver's License | License Plate | ...
``````

Basically a richer input to compensate for the easy brute forcing of the license plate. Oh, and obviously, use a cryptographically secure hash function :-)

-

If you want to anonymize it, you don't provide a key at all. No nonced hash of private data, no surrogate token, nothing.

You just say 'A Driver', 'Another Driver', 'Another Driver', etc.

If any particular driver needs to be referenced back to it's personal data, then you'd want that surrogate token (A guid/uuid for each driver in the database). But if the only objective is to present to the public some stats about anonymous drivers, no key is necessary, just list non-sensitive data.

-
This is the same as Lucas's tokenization? – schroeder Jun 25 '14 at 16:31
The guid/uuid to refer back to the driver, yes. – Andrew Hoffman Jun 25 '14 at 17:08