When Masking Isn't Enough
In 2006, AOL released "anonymized" search data for research. They removed usernames and replaced them with random IDs. Researchers at the New York Times took user #4417749's search history, queries about landscapers in Lilburn, Georgia, people with a specific last name, and medical conditions, and within days identified them as Thelma Arnold, a 62-year-old widow in Lilburn.
The data was masked but not anonymized. Enough contextual information remained to uniquely identify individuals. This is the re-identification problem: even without names or IDs, combinations of seemingly innocent attributes (zip code + birth date + gender) can uniquely identify 87% of Americans. That statistic comes from Latanya Sweeney's foundational 2000 research at Carnegie Mellon, and it still holds.
Netflix ran into the same problem in 2007. They released "anonymous" movie ratings for a recommendation algorithm competition. Researchers at UT Austin cross-referenced the ratings with public IMDB reviews and identified specific Netflix users, including their political preferences and other sensitive viewing habits. NYC taxi data released in 2014 with "anonymous" medallion IDs was de-anonymized by hashing all possible medallion numbers and matching them to the "anonymous" hashes.
The taxi attack is worth running rather than retelling, because the numbers are so much smaller than people expect. I hashed the whole medallion format on this laptop and matched a target back out of it in 320 milliseconds.
A date of birth took 30 milliseconds. There are only 37,123 of them since 1925, so an attacker hashes the lot and reads yours off the list. Nothing about SHA-256 gave way here. The algorithm did exactly what it promises, and it did not matter, because the input was drawn from a space you can print.
The dashed bars are the spaces too big to sit through in a lab, so they take the rate measured here and divide it into the published size of each space. A Social Security number is 9 digits, which is 8 minutes. An Indian mobile number is 30 minutes. Those are one core of Python with no GPU and no stored tables, so treat them as the slowest an attacker could possibly be.
The last panel is the fix. Swap the plain hash for HMAC with a secret key and run the identical attack: a million candidates, 0.87 seconds, nothing recovered. The identifier is still only a million values. The key is 32 random bytes, and the attacker has to guess that instead.
Two consequences follow for anything you build. Hashing an identifier is pseudonymization, not anonymization, and GDPR treats it that way. And the protection lives entirely in the secret, so a key that leaks takes every historical hash with it.
True anonymization makes re-identification impossible, not just difficult, but mathematically provable impossible. This is significantly harder than masking, and it always degrades data utility. The challenge is finding the balance between privacy protection and analytical usefulness.