Moving Away from UUIDs (2018)
neilmadden.blog
neilmadden.blog
If you're using them for providing a unique id in a distributed system, with very little chance of collision & fitting them in a db column, then they are great.
Seems like author made some bad choices in previous systems and now just figured out why tbh.
A guess means making a request to your server. You won’t be concerned with ~2^64 guesses per second.
I’m not suggesting anyone do it, if you have a choice. (Especially consider you’ll probably have to go through the trouble to justify it to people who read articles like this but don’t understand the math.) But if you have an existing system, consider whether you can let it stand.
But here the problem is not forging an ID, it's guessing an ID, and hashing does not widen the search space, does not increase randomness.
I think the poster you replied to was meaning using the hash output as the token, not that you would maintain the original token and a salted hash for verification.
If they are thinking SHA(GenerateUUID()) would have better entropy then they are incorrect even though all SHA variants output more than the 128-bits in the source UUID. I assume such misunderstanding comes from the fact that some PRNGs are based upon repeated application of cryptographically assured hash functions against the seed data.
Using some unreversible transform would solve the issue of potentially leaking information in the UUIDs, but if that is an issue then instead use a UUID variant based on purely random data (v4?) as that would be more efficient and not result in value that is longer but contains no extra entropy.
You have a 128 bit value. That's 128 binary digits. Each digit can be zero or one. That means you have 2^128 possible distinct values. (Ignoring the fixed bits in UUIDs since it's not important for sake of this argument.)
Now you use a one-way cryptographic hash on top, like sha256. This will return a specific hash for any given input. It is always the same for a specific given input, and it is nearly always distinct. The output that a hash has may have more bits, but the number of distinct values can't increase; it can only ever decrease. That's because you could only ever give it 2^128 different values. How could it ever return more outputs if each input corresponds to one output?
To make it more clear, let's say you have a database where you want to store a customer's zip code so you can use it as some kind of validation later on to ensure it matches, but you don't want to store it in plaintext, so you hash it. The hash is 160 bits. Secure, right? Wrong. There are less than 50,000 zip codes. It would be trivial to calculate the hash of every single one and use it as a simple hashmaps from hashed value to plaintext.
You may be thinking this is impractical for an input domain as large as 2^128, but realistically it only adds a slight roadblock. Knowing the only valid values will be hashed UUIDs, instead of picking 160 random bits, you'd be much better off picking a random UUID, hashing it, and trying that for each attempt.
So pretty much the same as every other damn thing in software that gets an "X Considered Harmful" article? :-D
UUIDs are not designed to be secrets, so they are a poor choice. They'll probably work, but there are better options.
There's nothing whatsoever wrong with using a cryptographically secure mechanism to generate a random 128-bit number and then representing that as a UIID in plaintext.
The issue would be using a UUID generator (there are many versions, and several of those use MAC addresses and time for a bunch of the "entropy" - so they are not cryptographically secure / random).
Your comment is overly reductive.
Nobody is referring to “UUID” and just meaning the representation. I would think it’s obvious people are referring to using a UUID generator e.g. `uuid.uuid4()` so no, I’m not being overly reductive. I’m just following the common understanding that everyone has when we say “UUID.”
To get clicks?
https://en.wikipedia.org/wiki/Universally_unique_identifier#...
Love this chart tho.
It's also not given that it'll be a performance benefit, you probably receive UUIDs as strings from some client and probably want to return UUIDs as strings to the client, and that conversion isn't free.
https://docs.djangoproject.com/en/4.1/ref/models/fields/#uui...
https://docs.djangoproject.com/en/1.8/ref/models/fields/#uui...
It may not have worked correctly on your project for some reason?
This is effectively a simplistic stand-in for a CRC type system -- useful to detect if the data has been corrupted, but not useful to avoid collisions.
The check digit wouldn't really help with collisions, since if the strings are the same the digit will be too. They are primarily useful when we need to ensure correctness on human input.
Given how easy it is to generate a UUID in most languages, and given the low likelihood of a collision within a system - it wouldn't be a huge leap to think UUID's could replace homebrewed random string generators for things like password reset tokens, etc.
That's near enough to true for anyone not operating at "web scale".
FAANG/BAT engineers need to care. My systems with 10s or 100s of thousands of users (or, you know, a few thousand users tops) are without doubt going to be re-written (probably several times) well before I have to worry about having so many UUIDs in the wild that this becomes a reasonable thing to worry about.
For me, at the scale of systems I run (or will conceivably run in the medium term future), I think the simplicity/understandability of code that uses native language UUID functions is "the right thing". Whoever does the next big rewrite to support a few million MAU will be thankful they don't have to work out WTF I was thinking when I decided to roll my own random access tokens.
It doesn't matter what computing resources your attacker has; the limit is how much your infrastructure can handle, and the author casually overestimates that by about 10 orders of magnitude. So replace 35 minutes with 350 billion minutes, or about 660,000 years.
I find it hard to believe that there is a problem with a (cryptographically random) 122 bit session key considering that a brute force attack on it will result in a DDoS, which is obviously self limiting.
Lots of people here are saying “never use a uuid for a session key”, but I don’t understand this. What’s the accepted entropy for a session key?
Then you realize the author is just talking out their rear end with no thought...
"Yes I often find my cracking buddies with their super computers just give up hacking my online user service when I bumped my user token length from 159 to 160 length", said nobody, ever.
Reminds me of this sketch: https://youtu.be/IHfiMoJUDVQ
[0]: https://en.wikipedia.org/wiki/Universally_unique_identifier#...
But yeah, even that is very very low risk. The article had to make some outrageously pessimistic assumptions to get it's "38 minutes!" number. Issuing a million tokens a second with two year validity, and getting attacked with the entire hash rate of the bitcoin mining community. And having both enough backend capacity to handle all those requests while at the same time having no observability or rate limiting to mitigate a brute force attack.
Assuming random UUIDs:
If you're counting all the UUIDs anyone makes, then valid<->attacker matches are a subset of all possible collisions and therefore less likely.
If your baseline is only the collisions between valid UUIDs, then whether an attacker is more or less likely to collide depends on whether they're generating UUIDs at least half as fast as the system they're attacking.
I’d argue even then it’s really not much a concern. You’d need to generate 1 billion UUID v4’s per second for over 75 years to have a 50% chance of there being a single collision.
There are other versions that are sequential/time-based though, but using these could open the door to de-obfuscating whatever data you wanted to protect via UUID's in the first place (like how many sales orders you receive per hour, etc).
People like to reach for UUID's when obfuscation is needed because inventing your own duplicate-aware random string algorithm isn't what most folks want to spend their time thinking about. Plus, these days, many databases come with UUID-aware data types that make using UUID's fairly straight forward.
This is obviously, and egregiously, false.
A go ref impl: https://github.com/segmentio/ksuid
https://datatracker.ietf.org/doc/html/draft-peabody-dispatch...
>>> Depends on the version used. Some of them do encode time.
Encoding time isn't enough, it has to be big endian (unless you write a special sorting function for uuids). Timestamped uuids store the timestamp as [timestamp_low, timestamp_mid, version(!), timestamp_high][1] which doesn't sort right.
[1] https://en.m.wikipedia.org/wiki/Universally_unique_identifie...
If UUIDs contain time information, then they can be sorted by time. The details of the encoding, while important for actually implementing the sorting algorithm correctly, don't really seem relevant when reasoning at a high level?
UUIDs are for uniqueness and involve implicit trust. Cryptographic libraries are what you need to generate entropy blobs without weakening security/confusing the next developer etc.
UUIDs are 128 bits. Which is beat by a 5 character a-z random string.
It's certainly possible that they're better than the median password - especially if there isn't a check against a common password list. But it's pretty easy for user chosen passwords to be much, much better.
I strongly doubt that your 6 9s estimate is accurate.
A sibling gives the actual math that shows how wrong this is, but this doesn't even pass the most rudimentary sniff test. The most common encoding for a lowercase string would be in 8 bits per character, so a 5 character string can get you at most to 40 bits.
And that's assuming you allowed every one of the 256 possible characters. You're restricting it down to 26 characters.
EDIT: I was curious, so I checked. Even if you allowed every current Unicode character, 5 characters only gets you to ~86 bits of entropy:
log2(149186^5) ~= 85.9
As for the original 6 nines claim, I also calculated the entropy for a 14 character random password that allows all 62 letters+numbers plus 8 special characters:
log2(70^14) ~= 85.8
It's not until 20 characters that it matches a UUID v4. So, yeah, I'm okay with OP's 6 nines.
About storage, at least PostgreSQL has been using 16 bits of storage since at least version 8 many years ago.
https://www.postgresql.org/docs/current/datatype-uuid.html
https://www.jacoelho.com/blog/2021/06/postgresql-uuid-vs-tex...
For example, in a REST system that needs UUIDs I'd use the REST URL of the object as the UUID.
{opaqueTokenTypePrefix}_{crockfordEncodedEntropy}
Also: pass token through a bad words and "credit card lookalike" filter.
Optionally encode author cluster/region details in the low order bytes to resolve before eventual consistency in active-active systems.
Why? I like to use them for private/secret URLs ...
To be honest, we get something like this kind of attention (Tbps of forged requests / brute-force registration attacks per day), and all we do is provide a free API that's rate-limited per user account for multitenant-QoS reasons. People do all sorts of crazy stuff to try to sneakily drip-register a thousand accounts over several weeks so they can then launch some big job that uses all the keys in tandem to evade the rate limits.
Little do they know, they don't get any benefit from that, even while they're nominally "getting away with it"; doing that just makes our servers fall over! :P
---
Separately, you should really consider a level between "Mossad" and "not-Mossad": the sorts of people who hack crypto exchanges. They tend to use exactly the kind of "saw it in a movie"-level techniques that you'd think wouldn't happen because "you can just use rubber-hose cryptanalysis." Except if you're a socially-anxious math-genius fifteen-year-old living in Belarus, and there's a cryptosystem that you have unlimited access to a local copy of, maybe the rubber-hose cryptanalysis is actually harder!
Bad example, since the biggest crypto hacker is North Korea.
> North Korean government-backed hackers have stolen the equivalent of billions of dollars in recent years by raiding cryptocurrency exchanges, according to the United Nations. In some cases, they’ve been able to nab hundreds of millions of dollars in a single heist, the FBI and private investigators say.*
https://edition.cnn.com/2022/07/10/politics/north-korean-hac...
It must be a group of outside parties who use North Korea as a mask and/or employer, right?
The New Yorker ran a piece on this recently-ish[1]:
The most promising students are encouraged to use computers at schools. Those who excel at mathematics are placed at specialized high schools. The best students can travel abroad, to compete in such events as the International Mathematical Olympiad. Many winners of the Fields Medal, the celebrated prize in mathematics, placed highly in the contest when they were teen-agers.
[1] https://www.newyorker.com/magazine/2021/04/26/the-incredible...
North Korea has been ruled by the Kims for 74 years at this point.
A few computers aren't expensive for even a low-wealth country, and math is cheap to teach.
The short version: they take their best math-inclined students, and send groups of them in China, to learn about computer hacking (and the world at large, to know what or who to hack). The group aspect serves as a self-surveillance check, to minimize risks of defections.
It’s not ideological, it’s practical; get a cybersecurity degree in the states/Europe and live “lavishly” with your family or flee and never see anyone you love again (they don’t kill them they’re just poor and in NK).
These groups know how to buy exploits, attach payloads, and be persistent. Not trivial per se but hardly PhD math stuff…
* It's long been know that UUID should never be used as a security mechanism. While the math is interesting, the fact they're using it as justification for moving away from UUIDs is concerning. It'd be like publishing a post titled "we're moving away from MD5"
* If you're using these tokens for human-entered purposes, you should implement account based rate limiting. It's nearly impossible for a brute force attack if a single account can only have, say 100 attempts per day before contacting support. There are very very use cases where a human-based token will ever need more than 20 attempts per day.
* Use long, high-character count tokens if they're intended to be machine/copy-n-paste only. Storage is cheap. Use something big and long.
Seriously, rate limit your shit. The second that rate limits are introduced you control all of the major variables in your security posture.
The minute is rate limited it’s crumble.
(Depending on how many accounts there are that they can try.)
At least, I don’t feel bad saying my server would melt if it had to serve that many requests.
If you assume that every person on earth was hooked to your service 24/7 and ignore the significant bandwidth limitation, it would still take more than 6 months for the entire Bitcoin network to hijack 1 random user's session. But it doesn't make sense to ignore bandwidth limitation anyway since it's the bottleneck. The Bitcoin network computes all these hashes in parallel and there is no way that anything close to this degree of parallelization can be achieved at the network layer.
Plus any deployment that is so large that a user could actually generate a reasonable amount of traffic will likely also have some variant of a DDOS/fraud/rate-limiting protection or at least alarms and manual interventions that will kick in once such a traffic flood is observed.
Your current systems might not be able to validate quintillions of UUID's per second, but your future systems might be able to (or at least get a lot closer).
Cryptography is a moving a target. Any cryptographic method except an OTP used with perfect opsec is brute forceable, and will need to be changed when your threat model changes (for example, when computing speed advances significantly).
An id is not a password.
Hash rate is totally not comparable with just trying every combination.
You can generate combinations instantly, you dont need a gpu for that.
The delay is how long the server takes to respond and how many connections it can have at the same time.
You're also blocked by the server after trying a couple of thousand.
I don't find any variable of TFA's hypothetical UUID-breaker scenario convincing either. Not the number of tokens issued, nor the adversary having Bitcoin network levels of compute, nor the ability to verify tokens at anything close to that speed.
Not sortable. Takes a lot of space. Table relationships are annoying. Etc.
What we do instead is have a secondary UUID key and keep Bigint as primary keys. Then use the UUID column in the external context instead.
UUIDs are fine for 99.99999% of the time in your own domain.
Don’t expect universal uniqueness across all domains.
UUIDs are sortable, but don’t give you creation-order sorting (of course, its abusing bigint PKs to rely on them for that, too.) If you want creation-order sorting, storing a creation timestamp and sorting on that works, and I’ve never had a db that had a business requirement for creation order sorting and didn’t also have one for actual creation time.
Maybe concurrent inserts to multiple data stores so you don't need to wait for an initial ID from the database. You'd have to trust the client to give you a “good” UUID as well as the normal distributed problems of one of the RPCs failing. I know both Twitter (called Snowflake iirc) and Google have unique ID services for this use case.
If I have a set of linked records in a relational schema representing a complex object, I can create them all with one round trip rather than multiple.
Also, large numbers of clients can insert in that way without contention, whereas if you use a sequence generator for PKs, it becomes a resource around which there is contention when creating rows.
> You’d have to trust the client to give you a “good” UUID
Sure, this lets you scale, e.g., backend service instances (which are db clients) without (as much as otherwise) contention in the db layer, its not usually something you would do with external, untrusted clients.
> I know both Twitter (called Snowflake iirc) and Google have unique ID services for this use case.
Snowflake was one of the inspirations for the newer (draft) UUID versions [0] (though, unlike them, it had a design constraint of fitting into 64 instead of 128 bits.)
[0] https://www.ietf.org/archive/id/draft-peabody-dispatch-new-u...
I see. I'd lean towards using common table expressions. The first insert statement returns the primary key and other inserts can depend on the key. I do understand it's not a panacea and composing queries can be problematic.
> a sequence generator for PKs, it becomes a resource around which there is contention
As I understand, Postgres sequences don't block which leads to a different problem [1].
That's not correct; its trivial to come up with an ordering, and I don't know of a database in practice that doesn't permit sorting on a UUID.
> Table relationships are annoying
… in SQL,
user_id REFERENCES users
> Takes a lot of space
Yes … but also no. It's 16 B vs. a serial's 4 B, I grant, but compared to a varchar, it's immaterial. (And particular in comparison to the number of times I see people use a varchar for an enum…) Certainly there could be a case where a row is wide b/c of UUIDs, but in practice, rows are wide either because of the data, or because of poor design.
Where date > y or (date eq y and id > x) order by date, id
This can't be completely fulfilled by an index. It'll have to sort/merge somevresults in memory, very CPU expensive.
More examples here https://www.mixmax.com/engineering/api-paging-built-the-righ...
The clustered index is actually the physical order of the data stored on disk, so any new guid causes tremendous amounts of churn.
Not sure how modern this concern is, but I would guess a LOT of SASS companies have to consider this.
Quick edit: sequential GUIDs are obviously a thing and I believe alleviate a lot of these concerns. I do not believe that was an option in sql server 2008 r2 (a version that lived a LONG time).
The performance impact of randomly distributed keys on any ordered index on that key is certainly real though, so I agree with you there.
OP called them "not sortable", which is a poor phrasing, as they're sortable. What he's likely getting at is that they're not ordered by generation time, which matters to some folks.
When do you need primary keys?
a better reason and justification to not use UUIDs is that they take up needless space if you're space constrained. they also have worse performance
1. Sort by ID if you want to see things by insert order and are using serial/autoincrement for the PK.
2. Writing (or reading, or talking about) SQL queries in which the IDs are present.
I solved the first problem by using ULID at one point but in future I’d probably not use a UUID until I had a specific need for it. And as others have mentioned, if that need is about the outside world I’d probably go with an extra column.
Most RDBMSes (possibly all of the big ones?) do this by default if you opt for no ORDER BY clause, however that IS then depending on undefined behavior which is bad.
Wait, did you store them as strings instead of as a native UUID type (or any sort of 128 bit integer type)?
As with all things, there are tradeoffs that must be considered before building the system.
And an auto incrementing bigint doesn't guarantee order.
What people want is for it to be sortable by generation time, i.e., they want it to share the "larger values were generated later" property of timestamps (but without collisions) or SERIALs (but without the locking on the serial / independent generation).
If you aren't generating a thousand IDs per second for every person on the planet, you're fine.
Even from a guess-ability standpoint, it's more important to put reasonable rate limits on your endpoints than worrying about someone putting bitcoin-network-level of resources against your endpoints.
Please, for the love of God, leave cryptography to the cryptographers.
You can use a different formatting. I would suggest looking at https://github.com/oculus42/short-uuid Of course if you just want a random ID, then you might not need a UUID. But UUIDs have the advantage that there are different versions and you can distinguish them; e.g. you might want a unique ID that gives you some debugging information (where/when was it created), so you use v1 and later you can decide to switch to v4 if decide you want the IDs to carry no information.
Indepedent of how you generate the ID, I think the base-57 encoding that shortUUIDs use is quite good when the IDs are user facing. Not using O,0,l,1,I in the alphabet makes IDs more readable.
- https://github.com/ai/nanoid
It should also be standard to understand the birthday paradox and when it's relevant.
In a ton of cases 122 bits is totally acceptable and it's really up to you to understand when it isn't. In fact, in lots of cases you can get away with less, like 96bits, etc.
It should be pretty easy to answer "how much do you need?" by asking what your tolerance for collisions is.
This article is about scenarios where it IS under your control.
Unless your concern is more that they may not be unique enough due to bad choices in their derivation function, but this will not change no matter what representation you store them in.
BESIDES not having any particular way to validate a token without asking the service, making the rate a hell of a lot slower than 2^64 tokens per second (lol wut) doesn’t it also assume that you have 2^46 valid tokens in existence? Isn’t that 70 TRILLION valid tokens, or nearly 9000 tokens per human on earth?
I'm not sure it's worth it to use more than a UUID for some use cases, but for a lot, it's fine. Maybe CUID if there's a decent library for your language/platform.
Aside... Whoever makes such a system that is generating/receiving OAuth tokens at that rate, and won't see/detect/feel a brute force attack of that scale probably didn't do anything to protect their SMS verification codes (only 6 digits), you'll definitely brute force that against a known password breach far more quickly, but okay, in either case.
Guaranteed globally unique in concurrency, built in data integrity check, and non-blocking read-modify-Bork resistant error detection
You are welcome, =)
However, I think article missed the point that you shouldn’t use UUIDs as a security measure anyway.
How you choose to encode the bits doesn't affect the security; if you use UUID form it's just as secure as if you use Base64. Regardless, if I had my 122 random bits, you would require 2^121 guesses to have a 50% chance of guessing it.
Edit: this is in the non-quantum case cf. https://en.m.wikipedia.org/wiki/Grover%27s_algorithm
Edit 2: (3:32 ET) done editing
Can anyone explain this?
The entire point is that different computers can generate ID's that can be merged in a database later on and not collide.
And the way they're designed is less likely to collide than random numbers are. (But you need to pick the appropriate UUID version to ensure that, depending on your system's architecture.)
If you're generating ID's that originate in a single centralized table, you don't need UUID's -- autoincrement or random integer is the simpler choice.
1. We want a single truly universal namespace.
2. We want to have different methods of generating IDs, since there are a lot of different people in the whole universe and they may have different needs.
3. Each single method is designed to not generate collisions.
4. But there could be collisions between different methods. So some bits are added to show what method was used to generate the ID to guarantee IDs generated by different methods don't collide. This is also why we need a spec that defines what each method is, the versions are like a scare global namespace that needs to be allocated carefully.
I think the reason I found this difficult is most of the times I see UUIDs, (1) and (2) aren't actually needed (this article being representative).
But version 1 of UUID's, for example, concatenates a MAC address, a timestamp, and a "uniquifying" clock sequence.
As long as you're ensuring your MAC addresses are all unique (which they should be, except for manufacturing error) and only one UUID library per device, collisions are impossible.
Whereas with random numbers, there's always a chance of collisions. (There are also other versions of UUID's that do include randomness, with collision potential, in exchange for not revealing information such as timestamps and MAC addresses.)
[1] https://en.wikipedia.org/wiki/Universally_unique_identifier
Just wondering, can v1 guarantee uniqueness with multiple processes using the same network adapter or within containers?
You don't need a UUID for that. A 128 bit random integer will work just fine.
You don't need a UUID for that. A UUID will work just fine.But if we're talking about UUID v4, it seems that 122 out of 128 are indeed random. [1] So why not just go all the way? Who cares about these 6 bits of meta data?
That what I'm trying to ask, what is the purpose of this disjoint union, when would you ever use the "UUID-ness" of UUIDs (which is not the same as asking about the virtues of UUIDs of a particular version).
If you want to start doing your own thing, a random number is good. It's hard to get a good random number. I suggest starting with, hey you guessed it, the UUID library.
They were nonsequential and sparse.
For those of us looking to 1) quantify activity and 2) migrate users and data off the system, they were pretty confounding.
Fortunately, Google also provided lists of those UUIDs by way of robots.txt sitemap files.
I used one sample of ~50k of those to estimate total G+ active users as of ~2014 (another group polled a random sampling of 500k for a more precise measurement). And when G+ folded in 2019, I'd provided that information plus some additional bits gleaned over the years and from some additional sources to estimate just how large the archive dataset might be, for ArchiveTeam.
One place where the sparse population might prove really useful is in telephony. Phone numbers as we know them today are densely populated, and in fact, frequently re-used (which is why your new phone is receiving debt-collection calls for its previous holder). It also makes war-dialing or random-dialing viable for robocallers.
If only 1 in 10 billion numbers was valid (about the saturation rate of G+ UUIDs), war-dialing / random dialing would be all but ineffective. If you could dial one number per second, you'd have a 50% chance of hitting a live number ... in 158 years.
(Of course, if you had a listing of valid numbers, again, see G+'s robots.txt files, your search space would be far smaller.)
123e4567-e89b-12d3-a456-426614174000
^^^^^^^^ ^^^^ ^^^^ ^^^^ ^^^^^^^^^^^^
time lo time time seq node id
mid hi
See: https://en.wikipedia.org/wiki/Universally_unique_identifier
It's easy to get and for any non sec application nearly impossible to replicate.
A charge looks like: ch_3M0k8bFSpHML0ApB0Pd8Zxmq
These use-cases you're implying seem to be the real problem.
The author's recommendation is to make UUID's longer and encode them with base 64 instead of hexadecimal. That's it. Somehow that means "moving away from UUID's."
If you want future proof random/unsorted ids just use 512 bits. That's large enough to maintain a 128 bit search space with existing hash algorithms even in a world with practical quantum computers that run Shore's et all. This is approximate reasoning not a formal proof but is reasonably grounded. In the big picture 64 byte vs 16 byte ids are unlikely to be the thing that kills your company. A security breach or corruption of a key database record very well could.