UUIDs in MySQL are really not random

https://blog.waleson.com/2019/02/uuids-in-mysql-are-really-not-random.html

by jtwaleson • 7 years ago

86 67 7 years ago

blog.waleson.com

They're not RUUIDs, after all. The article states that it's doing pretty much what the docs say it's doing.

foobarian• 7 years ago

So... guy shoots himself in foot, writes article about being surprised by how fast and sharp bullets are. This one deserves the Picard facepalm.

tombert• 7 years ago

Sure, but it could be a pitfall that someone else could fall into. I don't really ever use MySQL, but I didn't know about the UUID stuff.

There are a million things that get posted on Hacker News that are "beginner level". How many tutorials have we gotten about Rust on here? I don't think that's a bad thing.

gruez• 7 years ago

So, the lesson for today is: take warnings in documentation seriously. If you used UUID() for data that is supposed to be secret (like passwords), you have a serious problem, as these secrets can now be easily guessed.

No, the lesson here is to not assume a "random" function is cryptographically secure unless stated otherwise. The same article could be made about Math.random or rand.

hn_throwaway_993• 7 years ago

But the main problem is that he thinks UUIDs are supposed to be random when they're not - their only guarantee is uniqueness. MySQL uses (IIRC) V1 UUIDs, which combine a MAC address with time, while only V4 UUIDs are random.

ben5092• 7 years ago

The MAC address is a worse problem, honestly, than that they're not random. That means your database is leaking information about which host generated the UUID, which would be useful to someone trying to exploit a particular host.

Or if you have an application installed on personal machines, it's leaking identifying information about those machines.

the_mitsuhiko3• 7 years ago

Because 3 and 5 are based on hashes they will be random as well unless you know what the input value was.

gnu8• 7 years ago

I agree with the author, the lesson really is to take the documentation seriously. I think a lot of people might not be in the habit of doing that, because they find the documentation of many projects lacking, or because it’s easier just to read some walkthrough where the work is already done and they can just copy paste the commands. It’s important to fully understand what you are doing in all cases, not just ones touching cryptography.

cpburns2009• 7 years ago

Well it is a universally unique identifier not secret. There's no ensurance of it being random unless you're generating v4 UUIDs.

greiskul2• 7 years ago

And even if you are generating v4 UUIDs, they are not necessarily cryptographically secure. So it might be possible, if lets say, a user gets a bunch of UUIDs that your system generated, it might be possible for they to figure out other UUIDs that the same system generated. Which is totally fine for what they were built for.

agentx3r2• 7 years ago

If you used UUID() for data that is supposed to be secret (like passwords), you have a serious problem, as these secrets can now be easily guessed.

I've never used UUIDs for secrets, but I've often dependended on UUIDs to be uniform - as the primary identifier when passing data around inside distributed systems. If the chance of collision is implementation dependent, that could end really badly.

hn_throwaway_993• 7 years ago

UUIDs (of all versions) are guaranteed to be unique. They are not guaranteed to be uniformly distributed.

agentx3r2• 7 years ago

If you have two systems generating UUIDs, and their probability distributions are non uniform and overlap in any significant fashion, then your odds of collision are no longer on the order of 'heat death of the universe'.

TIL only version 4 is generated using a random source.

jve• 7 years ago

If you used UUID() for data that is supposed to be secret (like passwords)...

Since when someone on earth has recommended something like that?

UUIDs are time/mac address sensitive. They have version info within. They make an awful, guessable secret. It's just that: An unique identifier across the globe and not just your database.

whack5• 7 years ago

A V4 UUID has 122 bits of randomness. Assuming your RNG generator has sufficient entropy, it would be perfectly valid to use the resulting UUID as a secret.

https://en.wikipedia.org/wiki/Universally_unique_identifier#...

dragontamer2• 7 years ago

Assuming your RNG generator has sufficient entropy

Why would you ever assume that? UUIDs could be formed from a low-entropy LCGRNG and still match the specifications.

Any secret should be generated with cryptographically secure random number generators. Calling "UUID" instead of like, BCrypt or something would be a major red flag to me. Heck, a modern cryptographically secure secret can be generated from Intel's "RDSEED" assembly instruction, which provides a hardware-random source of entropy, as well as entropy guarantees. (You'll probably use this assembly instruction if you are using /dev/urandom)

munk-a• 7 years ago

Please don't ever roll your own security. Use a language feature (if available) or a third party library... though do a bit of due diligence on the third party library to make sure it's endorsed by a trusted source.

krig4• 7 years ago

Ehm, this is just a fundamental misunderstanding. UUIDs are not and are not supposed to be random. They are not even unique. They are just reasonably likely to be unique enough for most purposes.

whack5• 7 years ago

https://en.wikipedia.org/wiki/Universally_unique_identifier#...

V4 UUIDs are supposed to be random.

beefhash2• 7 years ago

If you parse out the UUIDs presented (e.g. 4331cc4c-1d91-11e9-be2c-45923c63e8a2), you'll see there are a lot of version 1 UUIDs.

crehn• 7 years ago

And MySQL docs clearly state they're using v1.

krig4• 7 years ago

Nope. The V4 RFC does specify and recommend a method for generating UUIDs that uses randomness, but it also provides other methods, and explicitly warns against relying on the UUID being random:

"Do not assume that UUIDs are hard to guess; they should not be used as security capabilities (identifiers whose mere possession grants access), for example."

chapium• 7 years ago

This is quite funny. Anyone who has used UUIDs for a while realizes that they tend to cluster. Relying on them for randomness is effective as the old xkcd joke: https://xkcd.com/221/.

They are certainly useful for creating unique id's, but for randomness? No.

the_mitsuhiko3• 7 years ago

Anyone who has used UUIDs should be aware that there are different UUIDs. In fact, UUID3,4 and 5 are all generally random. UUID4 depending on the quality of your RNG and 3 and 5 depending on the quality of the input data.

beefhash2• 7 years ago

If you are even more like me, you will think that this is like the difference between /dev/urandom and /dev/random

/dev/urandom does not produce such non-random results; the comparison is rather far-fetched. /dev/urandom is suitable for virtually all tasks, including cryptography[1]. It's the same as /dev/random on various BSDs, even.

[1] https://www.2uo.de/myths-about-urandom/

the_mitsuhiko3• 7 years ago

That's because the UUIDs returned by mysql are documented to be version 1 which are based on timestamp and node (mac address often enough). Of course they are not random.

wil4212• 7 years ago

What’s the use case for a random UUID? I’ve never had a need for them to be random just unique.

ben5092• 7 years ago

There isn't one for them, really.* The reason they exist is that non-random UUIDs rely on unique information about the host. Since UUIDs are used heavily in consumer applications (ubiquitous on Windows) and are transmitted without encryption, they're leaking identifying information about the host that generates them.

* One that is better served with a UUID than a random binary blob.

gtsteve• 7 years ago

Some developers use them in the place of random password generation for example. In this article, we discovered why it's not a good idea.

In other words, you shouldn't use a non-cryptographic RNG for security purposes.

jpalomaki• 7 years ago

Assigning random identifiers for things. Benefit being that this can provide additional layer of security since somebody can’t just guess the ids for things he is not supposed to access.

Thing for example getDocById.php?id=...

Of course it does not have to be UUID, but this can have some benefits as you DB for example may have a nice datatype for it.

crdrost• 7 years ago

So supposing you have multiple clients you might have shared access to an image or client-data database. You might not want someone to see an identifier and guess other "close" identifiers.

For example, a company I used to work for named IntegriShield is essentially a for-hire private Internet police company. When I got there, we would take an automatic screenshot of a web site and then send it to the people who were doing something "bad" (for whatever the definition of "bad" was) and you would essentially visit some sort of link like

    https://api.integrishield.com/(api route)/12345.png

Of course if these folks were to increment the identifier they would see other screenshots we were capturing -- though at the time that was not very helpful as we would routinely capture every web site that we crawled, so most of them didn't have anything interesting on them.

One of my jobs there was to improve this process: reduce image storage costs and increase the productivity of the humans who had to look at these web sites to determine what had gone wrong. With my contribution, we could intelligently flag language that might be "bad" and then capture enough metadata that we could later reconstruct screenshots which highlighted those "bad" things, after a human being had looked at them and said "no, these things are okay but those things really are bad" and deleted half of our highlights. So the screenshots were now only generated after we were done and clearly highlighted what was wrong, and then it becomes a serious problem if folks from one of these companies can see what their peers are doing.

We did not switch to UUIDs but rather just encrypted the counter with a server key, but the point is still that you would now visit

    https://api.integrishield.com/(other-api-route)/2121a46a4c24c512965671f8fb269f0b.png

and that would give you access to this image, but now if you just change that to a random identifier there is only a 2^-64 chance that you would successfully alight upon a valid image, and if you don't we can increment a counter in the database and if that gets too large too fast we can send out emails saying "warning, lots of 404s are happening".

UUIDs v4 (chosen securely randomly) have the same properties from the very start. You can easily use them in cases where the security model demands that some non-client must be able to access some sort of information simply by knowing the identifier.

We could have chosen something more complicated, of course, like creating a many-to-many table relating screenshots to email addresses and then embedding the email address somehow in the URL,

    https://api.integrishield.com/(more-api)/12345.png?email=someone%40example.com
    https://api.integrishield.com/(more-api)/12345.png?emailBatch=67890

Of those the first is worrisome -- there's no reason that one company couldn't have access to another company's email addresses for their legal compliance department and indeed in many cases they should. And if we try to obfuscate that with an auto-incrementing ID like in the second case then we're actually legit broken: remember, I told you that the screenshots are generated shortly before the emails get sent out, so they both would tend to increment in lockstep, you might have to try only 5-10 screenshot/batch pairs before alighting upon one you weren't meant to see. So the batch needs to be protected by, what, UUIDv4? And you have the same problem that you had before.

wil4212• 7 years ago

I appreciate the response. A legacy system at my company actually exposed data this way recently. A user guessed values and was able to see a small bit of data from other customers.

hangonhn• 7 years ago

A uniformly random ID is really useful when you're implementing a distributed system and you want to evenly distribute the load. You can make certain useful assumptions when your IDs are uniformly random -- which is basically how hyerloglog works and how the article's author was able to approximate the progress of his jobs.

sarabob• 7 years ago

Yay, you're one of today's lucky 10,000 [0]!

There are different types of UUIDs [1]. MySQL generates version 1 UUIDs - you can tell by the first digit of the third block. It looks like something else is also generating UUIDs, using the v4 format - so you have two different types of UUID in your database:

4331cb9e-1d91-11e9-be2c-45923c63e8a2 # v1

c7e2f124-f6ba-4434-843f-89958a7436ec # v4

v1 UUIDs are typically based on the MAC address of your computer and the current time. Online tools exist [2] that decode the uuid and tell you it was created at 2019-01-21 10:28:55 (UTC)

v4 UUIDs are random.

[0] https://xkcd.com/1053/

[1] https://en.wikipedia.org/wiki/Universally_unique_identifier

[2] https://realityripple.com/Tools/UnUUID/

leni536• 7 years ago

The article's gripe with UUIDs is with uniformity and not randomness. A low discrepancy sequence [0] is an example for something uniform but not random in an sense.

[0] https://en.wikipedia.org/wiki/Low-discrepancy_sequence

mavdi• 7 years ago

So basically UUID V1 instead of V4. Misinformation presented as a lesson.

lialuna• 7 years ago

The reason they are not uniform is that the first part is essentially a time stamp. From the docs:

UUID() returns a value that conforms to UUID version 1 as described in RFC 4122. The value is a 128-bit number represented as a utf8 string of five hexadecimal numbers in aaaaaaaa-bbbb-cccc-dddd-eeeeeeeeeeee format:

The first three numbers are generated from the low, middle, and high parts of a timestamp. The high part also includes the UUID version number.

The fourth number preserves temporal uniqueness in case the timestamp value loses monotonicity (for example, due to daylight saving time).

The fifth number is an IEEE 802 node number that provides spatial uniqueness. A random number is substituted if the latter is not available (for example, because the host device has no Ethernet card, or it is unknown how to find the hardware address of an interface on the host operating system). In this case, spatial uniqueness cannot be guaranteed. Nevertheless, a collision should have very low probability.

The MAC address of an interface is taken into account only on FreeBSD and Linux. On other operating systems, MySQL uses a randomly generated 48-bit number.

jrochkind13• 7 years ago

Aha, UUID v1! The author really wanted/expected a UUIDv4 there probably. It's confusing that we talk about "UUIDs", when there are a variety of different kinds -- called "versions" but they're not really "versions" in the sense of updated/replaced algorithms, just different approaches.

I don't know if MySQL has built-in UUIDv4 though. pg does.

jerf2• 7 years ago

UUIDs have the same problem RAID levels do; they use numbers to identify different types, but the types aren't related to each other in the way numbers are related to each other (some sort of sequential operation where "thing 3" has less of whatever it is than "thing 4" does, be it age, quality, benefits and costs like certification levels, whatever). I can never keep straight which level of RAID is which either, since I only brush them every couple of years, but if they were named for what they are instead of by number I wouldn't have this problem. I would know what "RAID Full Mirroring" or "RAID Striped" were much more easily.

We really ought to use names for them, not version numbers. If someone wrote "Timestamp-based UUIDs Are Not Fully Random", well, by the time you've typed out the title of your blog post you'd have figured out what the problem was.

dvlsg• 7 years ago

Is it built in to pg now? Last time I set up pg I had to add an extension to get UUID support.

It was relatively painless, sure, but I seem to remember having to add it.

Waterluvian• 7 years ago

I think "version" is the right word if you take it in the traditional sense, not the common technical meaning.

tracker12• 7 years ago

That was my first thought looking at them. And depending on how the binary values are indexed, probably much more efficient for inserting into a primary key than a UUIDv4.

iooi• 7 years ago

If you want UUIDv4 in MySQL, this Stack Overflow thread is pretty useful: https://stackoverflow.com/q/32965743

tracker12• 7 years ago

Note that this will probably result in a more sparse index and longer inserts if using UUIDv4 for a primary key where UUIDv1 is available in the dbms.

weinzierl• 7 years ago

This reminds me of the day I noticed that some records in our database had UUIDs with uppercase letters while others had lowercase letters. It didn't require much digging to find out that it was dependent on their origin. One kind was generated by the database the others by Java code.

In our case it wasn't a problem, but I couldn't help thinking that this was a nice information leak where you could find out some property of a dataset that was never intended to be retained. Just imagine that you mobile sign-ups had one kind of UUID and your web sign-ups the other kind. Though you might not explicitly store the information how someone signed up you inadvertently really do.

And now if you are tempted to ask why we stored our UUIDs as strings - just don't...

ciupicri• 7 years ago

They don't seem to have the same type (according to uuidparse from util-linux):

  UUID                                  VARIANT TYPE       TIME
  4f95de28-0fd1-48db-ad2e-34ecd169c483  DCE     random     
  4331cb9e-1d91-11e9-be2c-45923c63e8a2  DCE     time-based 2019-01-21 17:28:54,631107+02:00
  4331cc4c-1d91-11e9-be2c-45923c63e8a2  DCE     time-based 2019-01-21 17:28:54,631124+02:00
  c7e2f124-f6ba-4434-843f-89958a7436ec  DCE     random     
  3e18f8dd-b1d3-4e16-8a81-4bdceac91772  DCE     random

Explanation of the output:

  Variants
   DCE   The Open Software Foundation's (OSF) Distributed Computing Environment UUIDs.

  Types
   time-based   The DCE time based.
   random       RFC 4122 random.

anth_anm• 7 years ago

The UUID specification only has a small part of it random.

UUIDs in MySQL are really not random

Related Stories