Debunking the Myth of "Anonymous" Data
eff.org
eff.org
More sophisticated methods of privacy also anonymize indirect identifiers, and in some cases personal attributes. They do this by adding noise to the data in such a way that the noise has relatively* minimal impact on the results of computations made over the dataset, but a significant impact on the ability to re-identify someone using indirect identifiers or attributes.
*There is always a tradeoff between privacy and utility. The only way to achieve 100% private data is 100% noise, but the privacy-utility tradeoff curve isn't linear, and you can still achieve very good utility and very good privacy in many cases, especially with the best tools. Methods are also improving over time, reducing the impact of the tradeoff.
Time and time again people think they've anonymized data and they're always proven incorrect.
Just come to grips with the fact you're participating in the sale of my (or whoever's) private data. Hope you sleep well!
Generally the state of the art for adding noise to data is differential privacy or microaggregation. In the case of differential privacy it's typically gaussian or laplacian noise, but it is not a trivial application. Noise applied through microaggregation is not a mathematical function because microaggregation targets k in k-anonymity, and the "noise" can only be measured after treatment, through various distortion measures.
My company doesn't sell private data or facilitate the sale of private data. We improve privacy within organizations to reduce the risk of privacy leaks. Data brokers and ad targeters would have no interest in our software. But thanks for the condescending comment!
I don't understand how you could help companies protect the private data they collect from users and think that you're not facilitating the collection and sale of it.
Most companies don’t want to sell their user data because they consider it competitive, and most data brokers don’t want to anonymize because why would they if they’re already selling raw data? They aren’t interested in our software because we prevent singling out of identities.
That's a lie we developers like to tell ourselves. But the reality is that most companies track data because some sold them software to track data.
It's ridiculous how every single small business website has cookie banners, GDPR consent, and includes multiple tracking scripts on their website to collect all the user data they can get their hands on.
Yet these small businesses have no idea what data they are collecting. The owners are completely clueless. They have all this data collection shit on their website because someone else who has no clue put it there.
They see facebook and google collecting all this data, and think they need to collect data too. But they have no idea what to do with it. At best they look at a few numbers and get a feeling that all the money they spent on their website was worth it.
But it's all bullshit. 90% of businesses don't need invasive tracking, don't know what to do with the collected data, and could save money if they didn't bother to track all that useless data.
User tracking actually requires linking to associate online activities with user personas. Anonymization systems are designed to break linking.
Can you maybe share your mathematical opposition to differential privacy? It's provably effectively.
This is pretty obvious survivorship bias. You think that they’re wrong because you only hear about the cases when they were. There are tons of examples of breaches where the anonymization held up, it’s just that it’s not interesting so nobody talks about it.
If I have a lock on my door that successfully prevented 99 people from breaking in, but one skilled lockpicker subverted it, then my lock has failed.
This isn't saying that locks are worthless, but it is saying that thinking of them as secure is a false confidence. This sort of truth is why there's a saying in the security field that you're at the greatest risk the moment that you think you're secure.
In terms of data security, the only way to be actually secure from data leakage is to not be in possession of the data.
Edit: my source for this is that I have been involved with hundreds of data breaches where the EU was satisfied that the privacy controls were sufficient to say that no personal data was compromised.
Your source doesn't make the case that I was incorrect about any of my assertions. That doesn't mean I'm right, of course, but I don't see how examples of privacy controls successfully protecting data disproves them. There can still be cases where the controls failed.
All parts of it. You are asserting that a sufficiently skilled attacker can magically overcome all privacy controls. This fundamentally misunderstands how privacy controls work. Don’t make absolute statements, they’re always incorrect (see what I did there?).
When data is compliantly anonymized, the ability to deanonymize it has been irrevocably destroyed. When evaluating privacy controls, you evaluate them against a trusted insider with full access and unlimited time. There are lots of organizations whose controls meet this bar.
What an uncharitable response in that it forecloses on the original commentator even explaining their argument better or clarifying. I mean what? Fuck a bit more honest debate and just jump to pre-assumed moral judgement?
I think it's really sad that the open source community has historically cultivated a culture which doesn't recognize this kind of paranoia as a lack of mental wellness. I think it's because the zealotry comports well with the extreme amount of energy needed to bootstrap the ecosystem into existence.
You can care about privacy while being unrealistic about why you don't truly have it and never will, because of how much of a risk it is to the powers that be. You can live in a world ruled by proxy wars between gigantic political superpowers and empires who control the upstream levers of the macroeconomy to ensure that the world will always go in a direction opposite to what you'd prefer it to be. It's been like this for thousands if not tens or hundreds of thousands of years.
But moreover, you can and likely do live in a society, full of people who will always value convenience over the freedom you seem to cherish. But even you likely are willing to give up some freedom and privacy for some convenience, unless you employ private security personnel to guard your private compound. And my guess is that if you were inclined in that direction, you wouldn't really be posting on HN. Short of that, to live in a modern society is to some degree accept this compromise and to accept one's own hypocrisy -- and my heart goes out to you as much as to myself because the existential anguish of this never goes away. Nonetheless, it is generally historically accepted that as we grow older, we are to develop the ability to constructively manage around this and gain the wisdom to do so.
Perhaps the reason you sarcastically asked GP that you "hope you sleep well" is because you are projecting and you know that you yourself do not. My advice to you and those of your ilk: stop obsessing over theoeretical purity and get on with enjoying your life in the scarce time you have left on this planet. You'll have far less regrets at the end. And you will finally sleep well.
So unless your city is named "success", it's going to be missing from the dataset.
It's a bit bewildering to actually run the app in this mode, but here's a lot of diagnostically relevant information you can get out of a database like that. You can even confirm bug fixes. Meanwhile, somebody looking to harm the user would need to already know quite a lot about that user before they could make any use out of such a thing.
Good faith efforts to protect user privacy exist, is not helpful to lump them in with the rest like this:
> Sometimes companies say our personal data is “anonymized,” implying a one-way ratchet where it can never be dis-aggregated and re-identified. But this is not possible—anonymous data rarely stays this way.
Is it not possible, or not common?
People need to be informed about how to apply scrutiny to anonymization techniques, not scared into assuming ill intent when they see one.
You've made the typical mistake of thinking that just because you've made it harder, you've also made it anonymous.
For instance, you might have replaced "Chicago" with 9cfa1e69f507d007a516eb3e9f5074e2, but if for instance a lot of people with that tokenised city name also have transactions for a store that only exists in Chicago, you can infer with a reasonable degree of accuracy the reverse mapping. A couple such data points, and you can be almost certain.
If you know when you made a couple of transactions that are in the database, and you can find a set of likely options for each time, and then see what fields they have in common. Once you know your data, you can infer a whole load of the reverse mappings for various fields.
If those transactions involve another user, you can start to correlate those mappings with data you know about them, and start to build up a web of transactions that person had even if you don't necessarily know yet who the other users they interact with yet.
All this is possible without the use of rainbow tables, but chances are your hash function is a standard one, so with a single known mapping you can work out which hash function you chose, and look for speculative entries in the data. e.g. let's just look for MD5("Chicago"), SHA1("Chicago"), SHA256("Chicago") and see if there are any matches. If there are, we can use that hash function and trivially create a rainbow table for every city in the US, first names, surnames, etc.
Deducing relationships between metadata elements (city field, and purchase store) ends up being the tricky part, and highly domain specific.
Hashes with salts make it a bit harder too.Your example of “transactions in Chicago” is much more salient; there’s clearly a cat-and-mouse dynamic where data can be de-anonymized, especially if the dataset is public. How much that will actually be possible will be specific to the data in question; but the risk is non-zero. There’s certainly a case that no amount of obfuscation is sufficient if a user has not explicitly consented to their data being used this way.
Actually let's not, because adding salting doesn't actually get it right either. Rather it's just another easily-broken system that is only good enough to fool its own designer. It's still trivial to run through a list of the most common city names, and recover nearly all of the entries. And if there is just a single "salt" per DB, which would be necessary for the apparent requirement that matching city names stay matching, even cycling through all combinations of letters is nearly practical. There just isn't enough starting entropy to make hashing meaningful.
> Meanwhile, somebody looking to harm the user would need to already know quite a lot about that user before they could make any use out of such a thing.
The one thing I see EFF did wrong in this article is, they picked a bad quote to start with. That line from Matt Blaze, it's almost a pure tautology. There's a better line (though I don't know who to credit with it - I picked it up on HN some time ago): there is no such thing as "anonymized data", there's only "anonymized until correlated with enough other datasets".
You say "somebody" would need to already know a lot about the user to make use of your database. But from my perspective - perspective of the user - that "somebody" could just as well be your company. Or your customer buying that data from you... and buying similar data from other companies.
Well yes, noticing problems in these databases and providing consulting towards their mitigation (ideally before the pain shows up) is more or less what we're selling. Some degree of analysis must remain possible because otherwise it would be unclear what the user is paying us for.
My point is just that different situations call for different privacy postures. "Anonymization = Untrustworthy" glosses over this in a way that doesn't help us find ways to improve the situation.
True. Privacy is a special case of security, and it's only useful to talk about security in terms of what threats are of concern.
> "Anonymization = Untrustworthy" glosses over this in a way that doesn't help us find ways to improve the situation.
If your concern is to be as anonymous as possible, then "Anonymization = untrustworthy" is not an unreasonable stance. The only way I know of that data can be collected and handled in an anonymous way is to aggregate the collected data immediately and discard all individualized data.
Replacing data with something like a hash is useful in many ways, but there are many things it isn't that useful with.
I think the better focus for the article would be on transparency. I didn't write the script because I was conforming to some well defined policy about what's in bounds and what's out. I wrote it because somewhere in my heart I felt a vague duty to improve the situation. I'm getting a little pushback on my defense of the script--which is fair--but better would be to scrutinize the policies under which I had to ask my gut about it in the first place.
Often, it's because there is no other choice. When I'm revealing personal data to companies and such, that's usually why. Very few companies that I'm aware of are actually trustworthy on these matters, but I can't live without doing business with many of them regardless.
I absolutely do decide to reveal data to some companies that are optional, though. Like with all security matters, there's a cost/benefit calculation to be done here.
> I wrote it because somewhere in my heart I felt a vague duty to improve the situation.
Which is entirely laudable, and I think a worthwhile activity. It is, however, an effort that mitigates some risk rather than making things safe. People like the EFF are focused more on the goal of safety. It's almost certainly not a goal that can be fully achieved, but I'm glad that they're shooting that high anyway.
Make mock data inputs or snapshot data based on internal/QA usage, please!
I'm not sure I understand. Wouldn't it be trivial to hash the name of every known city, thereby reversing your cryptographic hash? As is done for passwords, only with a much smaller space of possibilities.
*And presumably, somehow, there being no way to recover this meaning. E.g. if an attacker is reversing hashes, they could try several sources of guesses - city names, country names, common first and last names in several languages, heights and weights in metric and imperial in the human range, valid phone numbers, IPv4 addresses, dates, blood type, license plate and post numbers or entire addresses, e-mail addresses if the attacker has a list of known-valid emails... all of these, and I'm sure many others that I forgot, are sufficiently small that they can be brute-force guessed by simply trying all possibilities, so no matter how generic the name of a column is, if it contains any of this data, the hashing can be reversed.
> Baltimore=>0x01a1...1ef7=>01a
> Aaron=>0x17bf...86f1=>17bf
>{"Foo":”Bar"}=>0x19f4...9af2"=>19f
This would create lots of false positives if one attempted to reverse it, but it's still a 1:1 map, so data which satisfies unique and foreign key constraints would still do so after the transformation. As for the utility, it makes it so that you can run the app and see what the user sees--except their data is hidden from you. So suppose the user's complaint is:
> two weeks ago, workflow xyz stopped reaching its final state, but never explicitly changed status to 'failed' so we weren't alerted to the problem.
I can hash "xyz" and get its handle and then go clicking around in he app to see what stands out about it compared to its neighbors. Perhaps there's some should-never-happen scenario like an input is declared but has no value, or there's a cyclic dependency.
I don't need to know the actual names of the depended upon things to identify a cycle in them. The bugs are typically structural, it's not very common that things break only when the string says "Balitmore" and not when it says "1ef7".
Privacy wise, the goal is to be as supportive as possible without having to ask them to share their screen or create a user for us so we can poke around. And when it's a bug, to have something to test with so we can say "It's fixed now." instead of "Try it again, is it fixed now? How about now?"
I'm the third party here, and I'm trying to prevent my users from sharing their users' data with me. Maybe it's not strictly "anonymization" because I'm not sure that this data references people. Remaining unsure is kind of the point.
https://geotargit.com/called.php?qcity=Success
> There are 11 places in the world named Success!
Negligence of all possible corner cases is common in handcrafted, "well-intentioned" approaches such as this. I put well-intentioned in quotes because assuming you know all the issues and premature confidence in the solutions demonstrates a lack of intention to actually get it right. Hubris permeates the mindscape of move-fast-break-things types.
Sometimes the failures are more obvious such as those pointed out by sibling comments. Part of the EFF's general point is it's a complicated business with so many pitfalls that it's a shame we have to learn by trial and error when people's private data is on the line. There's a reason many large companies have entire departments exclusively focused on privacy in their data stores.
That is usually referred to as "pseudonymization"
This is the crux of the problem. In every situation where I've seen it deployed, "anonymization" is as far up the utility curve as the corporate interest can get while still credibly calling their data anonymized. The standards and rules that are in place for restricting what types of data can be called "anonymized" to the public are so far up the utility curve that there's functionally no privacy at all.
I don't know what your startup does or what steps it takes to make that tradeoff responsibly, but assuming that you are responsible, you are one of the few, and most of the customers in the world would rather use a client that is using the word "anonymous" more irresponsibly because:
1. they can get away with it
2. there's a lot more business value in obfuscating data as little as possible
The EFF article is bang-on here, because the majority of the "anonymization" in the space isn't being done by responsible folks (like yourself, presumably), it's being done by psychopathic business interests.
If you treat indirect identifiers with our system, the minimum level of anonymization would ensure that there are always a minimum of two matching combinations of indirect identifiers, i.e. k=2, for every record in the dataset. This is far from foolproof for preventing data leakage, but it does prevent singling out and provides a lot of protection in the case of breach.
> There is always a tradeoff between privacy and utility. The only way to achieve 100% private data is 100% noise
The point is that the people whose data is being "protected" rarely have a say that their data is in the data set in the first place, and to what level their data is noised when it is.
> However, in practice, any attempt at de-identification requires removal not only of your identifiable information, but also of information that can identify you when considered in combination with other information known about you.
So, anonymization may be well intended and sophisticated, but is only effective as long as you control and anonymize all the data available to your adversary. Which you obviously cannot. The best you can achieve with anonymized data is to allow non-malicious users to run some analysis on your data in a controlled environment without exposing them to information they should not see. If that's your employer's business model, well, there may be a market niche for that.
TFA is obviously referring to the general case where you can't really put arbitrary restrictions to the adversary.
The original datasets are brokered anyway. [citations disclosed]
Pseudonymized data is for all intents and purposes completely anonymous as long as the people you share the data with cannot access the linking table.
That constraint can be enforced technically, contractually, or legally, depending on how important the breach would be.
Pseudonymized data is not completely anonymous. For example, your name, address, date of birth, and other identifiable information are likely available in public datasets like property tax records or voter registration data. There are also mostly-legal datasets available for purchase with more complete demographic and personal information. If your birthday, gender, and zipcode are present in the pseudonymized dataset, I have an ~87% chance succeeding in a linkage attack matching you in of those public datasets.
By definition in any modern privacy specification, the only difference between anonymous and pseudonymous is that you can recover the true identity.
I believe a decade plus ago Pseudonymized meant simply making something less identifiable, but not any more.
See section about the new definition under GDPR.
Like I said, modern privacy standards. The US is still quite far behind: I've had to do HIPAA training and it shows.
I'd advise you to set your bar a lot higher than your national standards if you ever plan to do international products: nobody in the US will complain if you use stricter definitions but you'll instantly be rejected in Europe if you call that pseudonymization.
I’m familiar with GDPR, we work with EU companies, and all the ones we work with use original definition. NIST link aside, these terms are hardly standards anyway. They are nearly colloquial vocabulary, which unfortunately in this space I expect to remain imprecise and vague. This why we generally only use it in marketing and comms, while in the actual product we drill down into specifications for direct and indirect identifiers, distortion, and risk.
There are a bunch of regulatory box-checking exercises like this that don't actually provide anonymization if the attacker is sophisticated.
Short of us buying up data in bulk and then doing the de-anonymization in-house I am not seeing an easy way to do this. Or even an advertised partner, seems like all the articles are really careful to not do free marketing for companies in this space.
You could try to ask independent consultant(s) who you trust to work on that problem and let them grow that practice. The problem is that they would need to have access to marketing platforms.
If I am dependent on the curator to determine the level of privacy then I've already lost.
This is a really useful argument, because it’s the equivalent of the FDA’s “generally believed to be safe”. If you look into something and this is the risk you find, then it’s safe.
From my perspective this article leans too heavily into the FUD, and really doesn't succeed at keeping the call to action ticking over. On a good day, the EFF can be really good. Today, not so much so.
The EFF is completely correct in their assessment - there's no way to make your data anonymous and usable by the third party at the same time. The root issue lies elsewhere.
There's FHE, which does allow your data to be processed without accessing it, but it has prohibitive compute requirements and isn't practical for most purposes. I'm not sure if it allows the data to be usable enough without revealing it, either.
This is absurd hyperbole, here’s a trivial proof. The US population is 51.1% female. If you live in the US your gender information is included in this data point, but it cannot be de-anonymized. It is however useful for determining TAM for many products.
Anonymity is a spectrum, and there are many points along that spectrum which are solutions to usable data which also respects privacy.
Most modern techniques for ensuring anonymization make assumptions that won't constrain sophisticated blackhats. They are good policy in a legal ass-covering sense and increase the cost required to de-anonymize but that is about it.
But do you think your average ad tech company gives a fuck? They are going to keep the original data because that's where the money is. Yea, maybe they'll have privacy datasets they sell/release to other groups, but all the real data will remain in a database, and with most companies in this industry, be given to government agencies on demand.
Edit: Not trying to start a DP vs ZKP (or Homomorphic Encryption) flame war. We're all on the same side of privacy, right? Different tools for different situations.
-- Cynthia Dwork, one of the invertors of Differential Privacy, Knuth Prize and Gödel Prize winner.
"The principles of data protection should apply to any information concerning an identified or identifiable natural person. Personal data which have undergone pseudonymisation, which could be attributed to a natural person by the use of additional information should be considered to be information on an identifiable natural person. To determine whether a natural person is identifiable, account should be taken of all the means reasonably likely to be used, such as singling out, either by the controller or by another person to identify the natural person directly or indirectly."
Under EU law, there is no special class of "personally identifying information". Any data that relates to a person or could be related to a person is protected. It isn't enough to just strip the name and SSN field out of the database and call it anonymous, you need to demonstrate that the data couldn't be attributed to anyone through any reasonably practical process.
> 4To ascertain whether means are reasonably likely to be used to identify the natural person, account should be taken of all objective factors, such as the costs of and the amount of time required for identification, taking into consideration the available technology at the time of the processing and technological developments.
This has been interpreted that any objectively possible way to de-anonymize is reasonable. In particular, considering that all the data of the organization doing the anonymization can be used to try to de-anonymize.
I’m not sure that I could imagine a detailed database with personal activity at a reasonable scale that couldn’t be de-anonymized, at least partly, if one assumes that people use related services and that one has access to them via public social media, mostly.
- Emails: of course;
- social media: easy;
- search queries: LOL;
- transport: through commute;
- any cultural good: you can connect to contemporary commentary;
- fashion shopping: pretty much trivial with OOTD posts;
- medial record: not everyone, but most major diagnostics could be matched to social media for many people;
- https blobs via VNP: most people would connect to the same four sites again and again, but exact timestamps and public statements on social media;
- grocery shopping: harder, but doable as you’d have neighborhood from the store address and a lot of surface…
Is the letter of that law against pseudonymous databases?
It makes your job harder? Tough shit. It makes law enforcement tougher to do? Ohhhh nooo, they might have to work for a living instead of pushing buttons.
Stop trying to defend companies that do this in service of capital. It is heinous. Some, if not most of us, want to be left alone and not have our addresses and medical history and YouTube stats available for the whole world.
There is no such thing as an anonymous dataset. It has been proven again, and again.
> do this in service of capital
Sir, this is ycombinator.com
If the intent is that no database with an individual-level breakdown falls under GDPR IID protections, I presume that far more processes and declarations would have to be applied to circumstances where there never was an intent or a credible option to de-anonymize them. This is not how it is enforced, understood, or applied today.
The large companies that you criticize so readily would have an issue automating the paperwork or building hashing solutions that divert the problem, but their privacy-respecting competitors would fall under a lot more paperwork and legal risk than they could handle.
Thankfully, there are solutions: a lot of people are now handling internal data processes with the same open-source tool, dbt. That platform could help change standards if they knew current patterns do not respect the letter of the law. But their lawyers seem to think otherwise.
It is a very tough problem to solve. Especially when you consider the richness of the datasets you use to put the pieces together.
In my experience the only effective means is to poison the data, in addition to the common sense steps mentioned here.
Poisoning a dataset means seeding a wide variety of the datasets you use to discover PII with fictional look alikes that resist debunking.
Additionally you can poison the core set if you are very clever about it.
Of course k-anonymity and differential privacy can help you with a closed data set, but once you add records to a dataset over time everything breaks down.
I once tried to find a way to anonymize data on different clients and then connect the records of the same entity on the server. This method had the main problem that one could artificially generate a new non-identifying data point for an individual and then see in which record it will end up in the central data base.
Barely even comparable.
« To determine whether a natural person is identifiable, account should be taken of all the means reasonably likely to be used, such as singling out, either by the controller or by another person to identify the natural person directly or indirectly.
To ascertain whether means are reasonably likely to be used to identify the natural person, account should be taken of all objective factors, such as the costs of and the amount of time required for identification, taking into consideration the available technology at the time of the processing and technological developments. »
https://en.wikipedia.org/wiki/AOL_search_log_release
https://web.archive.org/web/20130404175032/http://www.nytime...
https://scholar.google.com/citations?view_op=view_citation&h...
https://systems.cs.columbia.edu/private-systems-class/papers...
many I would have been fine with. most? no way.
Figuring out which of those traces belonged to which employee was a real puzzle /s