Exposing sequential IDs is bad Here is how to avoid it(petrepopescu.tech)
petrepopescu.tech
Exposing sequential IDs is bad Here is how to avoid it
https://petrepopescu.tech/2021/01/exposing-sequential-ids-is-bad-here-is-how-to-avoid-it/
3 comments
There are many data leaks that result from exposing the internal IDs of your data. These are easy to guess if you use sequential/auto-incremented values for the primary key of your data and later share it outside. here is how I think you can avoid it without sacrificing performance.
UUIDs are ... interesting. They offer both protections and some potentially unexpected affordances.
My comments here are informed by experience with three systems in particular:
- A 1990s era online publication's discussion forum which used sequential post IDs for its content.
- Google+, which utilised a form of UUID for both user IDs and submissions to the site.
- The somewhat notorious recent Parler web-scraping incident.
During the 1990s I was one of several participants in a forum that was being decommissioned, and which would be taken off-line entirely. Several years of what had seemed to be critically sigificant discussion history at the time (and in fairness, there are still bits I'd like to be able to call up now) would be lost.
The content management system (CMS) assigned a sequential post ID to each post on the site. Scraping the content was (mostly) as simple as running a bash loop of the form:
The recent Parler content archival used a similar characteristic:
donk_enby managed to exploit weaknesses in the website’s design to pull the URL’s of every single public post on Parler in sequential order, from the very first to the very last, allowing her to then capture and archive the contents.
Google+, by contrast, assigned 20- or 21-digit numeric sequences to users and content on the site (along with "vanity" text-based user identifiers for a small but generally active set of users, which turned out to confound ultimate archival efforts). This was larger than the actual populated target space by a factor of billions to quadrillions. Exhaustive search of either user or content space was simply infeasible.
But there was an interesting side effect.
As a search company, Google is (or at least was) remarkably conscientious about providing comprehensive sitemaps for many of its properties. This included Google+, and (when I accessed them), some 25 gigabytes of sitemaps for every single one of the then 2.2 billion user ID assigned at Google+. These were broken out into files of about 50,000 records each (the maximum permitted under the sitemap protocol). Yes, roughly 45,000 sitemap files.
Because reasons, possibly the algorithm used to generate UUIDs, the contents of any one sitemap appeared and tested via several methods to be a random sampling of user IDs. So when I got the bright idea after one too many fruitless arguments with someone that based on my sense, Google+ activity was nowhere near the levels the company was claiming, I realised that I could simply grab any arbitrary sitemap and sequentially scrape user profile pages, and look for the date of the most recent public posting activity, if any.
The key to valid sample-based statistical inference is having a random sample. And Google had just handed this to me. After only about 100 profiles, it became clear to me that at best about 9% of accounts had ever posted to the site. Another Very Simple Bash Script chugged through all ~50k profiles in the file I'd chosen, again on a Laptop of Very Modest Proportions, though over a rather nice broadband connection of the time, and again, a night's data pull and some crude awk scripts for reporting revealed the hard truth about Google+ activity: https://ello.co/dredmorbius/post/naya9wqdemiovuvwvoyquq
But I totally punted on the sampling, trusting (and yes, doing some rough checks) that any one sitemap file would actually be a validly random sample.
Eric Enge of (then) Stone Temple Consulting replicated the methodology on a much larger sample of 500k profiles, and doing some more robust resampling of the data as I understand it, validating my own rough estimates though providing additional detail. (A larger sample does not increase the accuracy of a statistical analysis by much, though it can increase resolution of that analysis, especially for rarely-occurring phenomena, such as, in this case, people actually using Google+, roughly 0.3% of the total registered profiles.) https://blogs.perficient.com/2015/04/14/real-numbers-for-the...
(I was impressed by the work, unaware of it prior to publishing, and somewhat relieved I hadn't made any stupid huge errors in my own effort. A key point in publishing my own findings was to note that pretty much anyone could quickly come up with a rough assessment of true G+ activity, a fact that made Google's own increasingly ludicrous statements, openly mocked in the trade and business press, easily disprovable and ultimately hurting the company's overall credibility.)
When G+ was in the process of shutting down, I accessed those sitemaps again, this time to find the list of categories Google had used to classify data (interestingly: these existed for English, as one might expect, and Spanish. Only.) and for the Communities (groups) feature of the site. In that case, an immediate interesting find was that rather than the 5 million or so groups that was generally claimed for G+, there were nearly 8 million when I first pulled the data, with that count growing to over 8 million by the time new Community creation was finally disabled in January of 2019. Again, by drawing samples of the full population, and being aware that I was looking for rare phenomena (here, large or active communities), and still undergoing large amounts of both creation and deletion activity. In the few hours between pulling a new communities listing and being able to scan a portion of that for size and activity data, a substantial fraction no longer existed. This suggested some interesting dynamics going on, likely around spam or disinformation. Another interesting finding of this research was that Google had managed to police G+ commmunities pretty effectively against extremist groups, with little apparent collateral damage. But that's another story.
But I got some pretty pictures of community membership and activity: https://joindiaspora.com/posts/23acfd90f05d01368b220218b79d8... https://joindiaspora.com/posts/ab6a5470f57001368d400218b79d8...
The methods aren't universally applicable. I haven't spent much time digging into, say, Facebook or Twitter numbers, though the simple approaches effective on G+ don't seem applicable to them. There might be other avenues to assessing activity or other characteristics independent of published statistics.
At the same time, the UUIDs also meant that the naive approach of archiving site content by simply iterating (or randomly poking) through the namespace would result in only one successful request for every few billions, or quadrillions, or worse, of requests. Without some means of identifying populated values, that approach was useless.
The upshot: UUIDs may protect user privacy. But depending on how deployed or exposed, could also provide a powerful tool for imputing true characteristics of site activity or behaviour.
My comments here are informed by experience with three systems in particular:
- A 1990s era online publication's discussion forum which used sequential post IDs for its content.
- Google+, which utilised a form of UUID for both user IDs and submissions to the site.
- The somewhat notorious recent Parler web-scraping incident.
During the 1990s I was one of several participants in a forum that was being decommissioned, and which would be taken off-line entirely. Several years of what had seemed to be critically sigificant discussion history at the time (and in fairness, there are still bits I'd like to be able to call up now) would be lost.
The content management system (CMS) assigned a sequential post ID to each post on the site. Scraping the content was (mostly) as simple as running a bash loop of the form:
for i in [1..$MAX_POST_ID]; do wget $BASE_URL/post_$i; done
The recent Parler content archival used a similar characteristic:
donk_enby managed to exploit weaknesses in the website’s design to pull the URL’s of every single public post on Parler in sequential order, from the very first to the very last, allowing her to then capture and archive the contents.
Google+, by contrast, assigned 20- or 21-digit numeric sequences to users and content on the site (along with "vanity" text-based user identifiers for a small but generally active set of users, which turned out to confound ultimate archival efforts). This was larger than the actual populated target space by a factor of billions to quadrillions. Exhaustive search of either user or content space was simply infeasible.
But there was an interesting side effect.
As a search company, Google is (or at least was) remarkably conscientious about providing comprehensive sitemaps for many of its properties. This included Google+, and (when I accessed them), some 25 gigabytes of sitemaps for every single one of the then 2.2 billion user ID assigned at Google+. These were broken out into files of about 50,000 records each (the maximum permitted under the sitemap protocol). Yes, roughly 45,000 sitemap files.
Because reasons, possibly the algorithm used to generate UUIDs, the contents of any one sitemap appeared and tested via several methods to be a random sampling of user IDs. So when I got the bright idea after one too many fruitless arguments with someone that based on my sense, Google+ activity was nowhere near the levels the company was claiming, I realised that I could simply grab any arbitrary sitemap and sequentially scrape user profile pages, and look for the date of the most recent public posting activity, if any.
The key to valid sample-based statistical inference is having a random sample. And Google had just handed this to me. After only about 100 profiles, it became clear to me that at best about 9% of accounts had ever posted to the site. Another Very Simple Bash Script chugged through all ~50k profiles in the file I'd chosen, again on a Laptop of Very Modest Proportions, though over a rather nice broadband connection of the time, and again, a night's data pull and some crude awk scripts for reporting revealed the hard truth about Google+ activity: https://ello.co/dredmorbius/post/naya9wqdemiovuvwvoyquq
But I totally punted on the sampling, trusting (and yes, doing some rough checks) that any one sitemap file would actually be a validly random sample.
Eric Enge of (then) Stone Temple Consulting replicated the methodology on a much larger sample of 500k profiles, and doing some more robust resampling of the data as I understand it, validating my own rough estimates though providing additional detail. (A larger sample does not increase the accuracy of a statistical analysis by much, though it can increase resolution of that analysis, especially for rarely-occurring phenomena, such as, in this case, people actually using Google+, roughly 0.3% of the total registered profiles.) https://blogs.perficient.com/2015/04/14/real-numbers-for-the...
(I was impressed by the work, unaware of it prior to publishing, and somewhat relieved I hadn't made any stupid huge errors in my own effort. A key point in publishing my own findings was to note that pretty much anyone could quickly come up with a rough assessment of true G+ activity, a fact that made Google's own increasingly ludicrous statements, openly mocked in the trade and business press, easily disprovable and ultimately hurting the company's overall credibility.)
When G+ was in the process of shutting down, I accessed those sitemaps again, this time to find the list of categories Google had used to classify data (interestingly: these existed for English, as one might expect, and Spanish. Only.) and for the Communities (groups) feature of the site. In that case, an immediate interesting find was that rather than the 5 million or so groups that was generally claimed for G+, there were nearly 8 million when I first pulled the data, with that count growing to over 8 million by the time new Community creation was finally disabled in January of 2019. Again, by drawing samples of the full population, and being aware that I was looking for rare phenomena (here, large or active communities), and still undergoing large amounts of both creation and deletion activity. In the few hours between pulling a new communities listing and being able to scan a portion of that for size and activity data, a substantial fraction no longer existed. This suggested some interesting dynamics going on, likely around spam or disinformation. Another interesting finding of this research was that Google had managed to police G+ commmunities pretty effectively against extremist groups, with little apparent collateral damage. But that's another story.
But I got some pretty pictures of community membership and activity: https://joindiaspora.com/posts/23acfd90f05d01368b220218b79d8... https://joindiaspora.com/posts/ab6a5470f57001368d400218b79d8...
The methods aren't universally applicable. I haven't spent much time digging into, say, Facebook or Twitter numbers, though the simple approaches effective on G+ don't seem applicable to them. There might be other avenues to assessing activity or other characteristics independent of published statistics.
At the same time, the UUIDs also meant that the naive approach of archiving site content by simply iterating (or randomly poking) through the namespace would result in only one successful request for every few billions, or quadrillions, or worse, of requests. Without some means of identifying populated values, that approach was useless.
The upshot: UUIDs may protect user privacy. But depending on how deployed or exposed, could also provide a powerful tool for imputing true characteristics of site activity or behaviour.
WOW! This was a really interesting read. I don't even know exactly where to start. I never looked into G+ (and was nowhere near as good as a programmer as I am now), but those were really cool findings.
Related to UUIDs, it does indeed protect privacy and protects the server from crapping and leaks. It is not enough for security, but it does make it harder. Internally you can still use sequential IDs for the PK so that speed is not impacted.
Related to UUIDs, it does indeed protect privacy and protects the server from crapping and leaks. It is not enough for security, but it does make it harder. Internally you can still use sequential IDs for the PK so that speed is not impacted.
Both of you are assuming random IDs protect user privacy. The only thing I can come up with where that to be true (without things that no one was ever seriously suggesting or using, such as a sequential identifier that increments on something per user) is that someone who is unable to see a resource otherwise will know when it was created (and in fact the time when something was created is now information about a thing "at all" when it otherwise might not have been). What am I missing?
Otherwise, the arguments against sequential identifiers seem to mostly come down to either people who somehow dislike scraping (which I might even argue is immoral, and I think this great comment from dredmorbiu come at it from the correct mentality; hell, I strongly prefer it--as a potential user--when a site is scrapable) or people who don't want anyone to know "true truths" about their service, with examples such as "our user growth figures" (but these help the site operator, not the users).
(I am also surprised to see Parlor brought up even in this great comment about "you didn't really stop me from figuring out what I wanted to know": to the extent to which you want to do "defense in depth"--which I honestly find frustrating as an argument by itself, as you can use that to justify almost anything, including absolutely ridiculous things we tend to claim are "security by obscurity"--you are going to then need to make sure you really really lean into the idea that "we wanted our site to not be scrapable, even to an administrator", which I can't imagine anyone ever actually doing for myriad reasons including how sites usually help search engines.)
Otherwise, the arguments against sequential identifiers seem to mostly come down to either people who somehow dislike scraping (which I might even argue is immoral, and I think this great comment from dredmorbiu come at it from the correct mentality; hell, I strongly prefer it--as a potential user--when a site is scrapable) or people who don't want anyone to know "true truths" about their service, with examples such as "our user growth figures" (but these help the site operator, not the users).
(I am also surprised to see Parlor brought up even in this great comment about "you didn't really stop me from figuring out what I wanted to know": to the extent to which you want to do "defense in depth"--which I honestly find frustrating as an argument by itself, as you can use that to justify almost anything, including absolutely ridiculous things we tend to claim are "security by obscurity"--you are going to then need to make sure you really really lean into the idea that "we wanted our site to not be scrapable, even to an administrator", which I can't imagine anyone ever actually doing for myriad reasons including how sites usually help search engines.)
Fair points, though some counterarguments:
- Not all systems make user data (or all user data) visible. UUIDs make guessing or traversing the address space harder.
- Certain types of attacks are easier given known, guessable, predictable, or sequential identifiers. UUIDs mitigate these attacks.
- Certain types of system confidentiality are generally easier to maintain with UUIDs. (Unless, of course, you then hand over the full listing, as Google did with G+.)
- Where merging systems, UUIDs may (or may not) help avoid namespace collisions. (Merging disparate systems with independent UID conventions is a notoriously fraught problem.)
On sites helping search engines: so far as I've been able to suss out, Facebook actually leans strongly the other way. I don't seem to get much insight to Facebook by trying to do site:facebook.com limited searches (through DDG, which is to say, Bing, or Google). FB's view seems to be that if you want to see or search content on the site, you create an account and go there through the account to find content. I don't often find myself interested in searching FB myself, but for as large a site as it is, it seems to turn up in results remarkably less often than other notably closed/annoying domains, say, Scribd or Pinterest.
Even as of 2015, FB's representation among various traditional and social-media options for a set of arbitrary interest queries was relatively modest (though higher than I'd recalled before going back to look at my results) and I believe (based on impressions rather than focused research) it's become more search-engine opaque since:
https://old.reddit.com/r/dredmorbius/comments/3hp41w/trackin...
- Not all systems make user data (or all user data) visible. UUIDs make guessing or traversing the address space harder.
- Certain types of attacks are easier given known, guessable, predictable, or sequential identifiers. UUIDs mitigate these attacks.
- Certain types of system confidentiality are generally easier to maintain with UUIDs. (Unless, of course, you then hand over the full listing, as Google did with G+.)
- Where merging systems, UUIDs may (or may not) help avoid namespace collisions. (Merging disparate systems with independent UID conventions is a notoriously fraught problem.)
On sites helping search engines: so far as I've been able to suss out, Facebook actually leans strongly the other way. I don't seem to get much insight to Facebook by trying to do site:facebook.com limited searches (through DDG, which is to say, Bing, or Google). FB's view seems to be that if you want to see or search content on the site, you create an account and go there through the account to find content. I don't often find myself interested in searching FB myself, but for as large a site as it is, it seems to turn up in results remarkably less often than other notably closed/annoying domains, say, Scribd or Pinterest.
Even as of 2015, FB's representation among various traditional and social-media options for a set of arbitrary interest queries was relatively modest (though higher than I'd recalled before going back to look at my results) and I believe (based on impressions rather than focused research) it's become more search-engine opaque since:
https://old.reddit.com/r/dredmorbius/comments/3hp41w/trackin...
Possessing an ID, shouldn’t give access, regardless of whether it’s a numerical PK or a UUID. (Unless that’s a feature, like shareable links) Still need to check if the user should be able to use that ID.
If that isn’t implemented, the system isn’t secure, doesn’t matter which path you use.
If that isn’t implemented, the system isn’t secure, doesn’t matter which path you use.
If the ID scheme mapping is sufficiently dense, traversal attacks on otherwise obscured namespaces become an option.
This might apply to user accounts, posts, payment accounts, or other elements.
Security isn't simply about compromising account credentials or access policies. It may be any unintended or unexpected data disclosure, inferred relationships (between accounts, activity, finances, offline attributes, access, reputation, and more), denial of access, stalking or harassment, and more.
These might not be unexpected in all cases, but could well be undesired in many instances.
This might apply to user accounts, posts, payment accounts, or other elements.
Security isn't simply about compromising account credentials or access policies. It may be any unintended or unexpected data disclosure, inferred relationships (between accounts, activity, finances, offline attributes, access, reputation, and more), denial of access, stalking or harassment, and more.
These might not be unexpected in all cases, but could well be undesired in many instances.
Using UUIDs externally is not only for privacy, but for security as well. There are attacks that are easier if you can guess the IDs that are being used. Also, not all systems are meant to be scrapped or deal with user-generated content.
I remember a few years back a data leak of stored financial information because the IDs provided for them in the "My Cards" section used sequential IDs. A simple script could scrape credit card data. Yes, I know that there were other security problems as well (not checking if a user has access to that card, storing it in a non-PCI compliant way, etc.), but still, the fact that the internal sequentially-generated PK was provided to the outside world, made things a lot easier.
Right. I'm referring here to the external affordances of UUIDs. Site performance is not my concern ;-)
The degree of programming involved in all of these exploits was laughably small. The Ello link literally includes the script I'd run for the G+ data pull, it's a bash one-liner. Parsing mostly consisted of a regex grabbing and isolating the posting date and follower counts from the rendered HTML.
The larger point being that if you provide a reference to the UUID set, sampling becomes easy, is ... well, come to think, if you're assigning sequential IDs and I know the upper and lower bounds of that range, I can still sample randomly from within it.
The problem of exhaustively searching a large-relative-to-references UUID space also apply, though I'm not sure if/how that might impact internal or site operations.
The degree of programming involved in all of these exploits was laughably small. The Ello link literally includes the script I'd run for the G+ data pull, it's a bash one-liner. Parsing mostly consisted of a regex grabbing and isolating the posting date and follower counts from the rendered HTML.
The larger point being that if you provide a reference to the UUID set, sampling becomes easy, is ... well, come to think, if you're assigning sequential IDs and I know the upper and lower bounds of that range, I can still sample randomly from within it.
The problem of exhaustively searching a large-relative-to-references UUID space also apply, though I'm not sure if/how that might impact internal or site operations.
One strategy (which incurs a little bloat on the wire) is to encrypt the value on the way in and out. You also have the option of incorporating per-session, per-user or per-group information into a computed ID obfuscating key so that IDs are not "shareable" across certain boundaries.
Do use a "key per table" (or "mix" the table name into a computed key) or else encrypted IDs for different types of entity will be the same (e.g. ID 1 from table A will map to the same value as ID 1 from table B).
ECB mode for this stuff is usually fine unless you are filling up a really big part of the key space. You probably do want an integrity mode if you are planning to use something like this to "pre-compute" access control checks (e.g. skip access control on an item lookup because that was done during item listing). Generally do not recommend skipping access control + visibility checks without a compelling reason even if your IDs are in theory unguessable / unforgeable.
The rub is key rotation, and how much you care about it. If your IDs tend to end up being stored permanently external to your system (e.g. it's a blog post ID or something) then a stored random ID is probably better.
For IDs which are not primary entry points to your application then the keyed approach can offer good flexibility, performance and storage characteristics.