UUIDs in MySQL are really not random

First published on
Universally Unique Identifiers (UUIDs) are great. I love how you can tell the progress of a batch job just by looking at the current UUID. If it starts with 0..., the task is less than 1/16th done. If it starts with 7d.., we're almost halfway there. At ff... we are nearing the end. The fact that you can tell this rests on two principles: 1) you sort your jobs by their uuid and 2) UUIDs are random, as in, distributed uniformly.

However, last week, I noticed a strange thing: a clearly visible pattern in the uuid column of a database table. It should be impossible, but there it was. It looked like this:

> SELECT uuid FROM example ORDER BY id;
4f95de28-0fd1-48db-ad2e-34ecd169c483
4331cb9e-1d91-11e9-be2c-45923c63e8a2
4331cc4c-1d91-11e9-be2c-45923c63e8a2
4331ccec-1d91-11e9-be2c-45923c63e8a2
4331cd7e-1d91-11e9-be2c-45923c63e8a2
c7e2f124-f6ba-4434-843f-89958a7436ec
4331ce10-1d91-11e9-be2c-45923c63e8a2
4331ce9e-1d91-11e9-be2c-45923c63e8a2
4331cf28-1d91-11e9-be2c-45923c63e8a2
4331cfaf-1d91-11e9-be2c-45923c63e8a2
4331d017-1d91-11e9-be2c-45923c63e8a2
4331d0c6-1d91-11e9-be2c-45923c63e8a2
4331d139-1d91-11e9-be2c-45923c63e8a2
4331d1a7-1d91-11e9-be2c-45923c63e8a2
4331d20e-1d91-11e9-be2c-45923c63e8a2
4331d271-1d91-11e9-be2c-45923c63e8a2
4331d2d7-1d91-11e9-be2c-45923c63e8a2
3e18f8dd-b1d3-4e16-8a81-4bdceac91772
4331d33a-1d91-11e9-be2c-45923c63e8a2
f6b8658d-846b-4418-a79c-713db516203e
4331d3a8-1d91-11e9-be2c-45923c63e8a2
4331d40d-1d91-11e9-be2c-45923c63e8a2
4331d48e-1d91-11e9-be2c-45923c63e8a2
4331d4fe-1d91-11e9-be2c-45923c63e8a2
4331d567-1d91-11e9-be2c-45923c63e8a2
4331d5cb-1d91-11e9-be2c-45923c63e8a2
4331d630-1d91-11e9-be2c-45923c63e8a2
4331d691-1d91-11e9-be2c-45923c63e8a2
14a5cb4c-f336-4240-aff3-4ffcfa8d135f
4331d6f9-1d91-11e9-be2c-45923c63e8a2
4331d762-1d91-11e9-be2c-45923c63e8a2
4331d7c8-1d91-11e9-be2c-45923c63e8a2
4331d83d-1d91-11e9-be2c-45923c63e8a2


Hm, that is very weird. Did we maybe convert an old auto-incrementing integer column into UUIDs in a very stupid way? Did we maybe use UUID version 3 or 5? Did our library corrupt the first bits of the binary representation of the UUID? After a while, I remembered that we initialized this column like so:

UPDATE example SET uuid = UUID() WHERE uuid IS NULL;

I also remembered reading this in the MySQL documentation:
"Warning: Although UUID() values are intended to be unique, they are not necessarily unguessable or unpredictable. If unpredictability is required, UUID values should be generated some other way." 
If you are like me, you won't use UUID() for secrets after reading this (and I didn't!). If you are even more like me, you will think that this is like the difference between /dev/urandom and /dev/random and that the uniform distribution law still applies here. However, to my great surprise, the UUIDs generated by UUID() are not uniform at all! The result is that a significant portion of UUIDs in our database are not uniform:

> SELECT COUNT(*), LEFT(uuid, 1) FROM example GROUP BY LEFT(uuid, 1);
+----------+---------------+
| count(*) | LEFT(guid, 1) |
+----------+---------------+
| 1943     | 0             |
| 1871     | 1             |
| 1913     | 2             |
| 1843     | 3             |
| 3050     | 4             |
| 1943     | 5             |
| 1889     | 6             |
| 1866     | 7             |
| 1865     | 8             |
| 1903     | 9             |
| 1868     | a             |
| 1898     | b             |
| 1854     | c             |
| 1897     | d             |
| 1941     | e             |
| 1836     | f             |
+----------+---------------+

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.

Edit: read this follow-up post

Popular posts from this blog

The unreasonable effectiveness of i3, or: ten years of a boring desktop environment

First published on
Image
My wife uses Windows and over the years I've helped her move things to new systems. Win8, 10 and now 11. With every change the UI changes. Now I can't right click the bottom right corner anymore to open Task Manager. The UI feels "fresh" and up-to-date I guess, but does it really matter? My desktop has looked like this since 2008. I love the picture of the gearbox, it's a testament to the hidden precision engineering that goes on inside the built world all the time. I don't see much of the gearbox though, because most of the time my screens look like this: The environment around my background picture has changed a little more, but has been stable for the last 10 years. My experience is very different to my wife's constantly changing system. In 2009 I moved from Windows to Ubuntu, then to Debian using Gnome. Then finally to i3 in 2013 after a brief affair with XMonad in 2012. So by now in early 2024, I've had the same minimal UI for more than 10 years,
Read more

Idea time: RFID+E-Ink, electronic price tags without batteries

First published on
I got this idea years ago, somewhere in 2004 after I had heard both of RFID and E-Ink. The order is irrelevant ;) The idea is simple, we take: 1) RFID readers, which send radio waves to tags, which pick up some of the energy in the wave, do some computations and send a reply. The tags are brilliant: no batteries, no connected power source of any kind except for the antenna. 2) E-Ink displays, which need power only to change pixels. After the power is cut off, the pixels remain in their current state. The result: a small tag with a display. The display gets initialised and updated by an RFID-reader and after that retains its state indefinitely. Perfect for price tags on shelves in supermarkets, which need to be updated every now and then but are hellish to replace. I soon found out in 2004 that Epson had already done this:  http://gizmodo.com/026090/epsons-electronic-ink-%252B-rfid--21st-century-price-tags
Read more

Parsing 10TB of Metadata, 26M Domain Names and 1.4M SSL Certs for $10 on AWS

First published on
Last May I was working on hobby project similar to this:  https://github.com/zakjan/cert-chain-resolver/  . As I found the cert-chain-resolver project a couple of days later I did nothing with the results, but I got some nice comments on how I used 1 VM to download & process 10TB in a couple of hours on this HN thread recently so I decided to do a write up on the process and publish the data. See the parts below: Part 1: downloading 10TB of metadata in 4 hours Part 2: fetching a ****load of certificates Part 3: playing with the data Total costs My approach was somewhat different from the github project above, instead of using the AIA extension I wanted to brute-force the solution by finding all known intermediate and root certificates in advance. Based on the checksum of the issuer/subject fields I could look up which certificates "claimed" to be the signer of the certificate and then using the signature I could filter out which ones actually were. You can us
Read more