Get the top HN stories in your inbox every day.
jandrewrogers
This is surprisingly common.
The security of UUIDv4 is based on the assumption of a high-quality entropy source. This assumption is invalidated by hardware defects, normal software bugs, and developers not understanding what "high-quality entropy" actually means and that it is required for UUIDv4 to work as advertised.
It is relatively expensive to detect when an entropy source is broken, so almost no one ever does. They find out when a collision happens, like you just did.
UUIDv4 is explicitly forbidden for a lot of high-assurance and high-reliability software systems for this reason.
LocalH
This is why CloudFlare has done what they did with the lava lamp wall. Not that the wall is such a great source of entropy on its own - I'm sure it's not their only source, but you can never have too many sources of entropy - but it makes it visible in a way that can grab those who don't fully understand the concepts of RNGs and how entropy plays into that.
The more sources of entropy, the more closely you approach "perfect" randomization. And a large chunk of those entropy sources need to be non-deterministic. Even on the small level, local applications running on local systems, like games, can use things like the mouse coordinates, the timings between button presses, the exact frame count since game start before the player presses Start to greatly enhance randomness while still using PRNGs under the hood
Yes, for the latter, that's technically deterministic (and the older the game considered, the more deterministic it is, see TAS runs of old games obliterating the "RNG"). But when you have fifty different parameters feeding into the initial seed, that's fifty things an attack would have to perfectly predict or replay (and there are other ways to avoid replay attacks that can be layered on top)
If CloudFlare had less than 100 different sources of entropy, I'd be disappointed. And that's assuming their algorithm for blending those entropy sources into a single seed value is good
greiskul
> you can never have too many sources of entropy
This is so true. And the beauty is that with algorithms, we don't even need to know much about the entropy to be able to extract it.
There is the Von Neumann method of generating an unbiased coin from a biased coin. Of throwing it twice, and checking if you got HT or TH. And completely discarding all HH or TT results. It doesn't matter if the coin you are using is 20% or 80%, the result will be a true 50/50.
There are more modern algorithms that can be even better (in that they need less coin tosses if you have a very unbalanced coin).
And then there is modern cryptographic hashing. Feed it all the bits you can. Collisions end up only happening in the real world if every single one of those bits is identical. So if you have actual entropy being fed, that cannot be controlled, predicted, or replicated, modern cryptography tells you that the end result is unique.
ms_menardi
> There is the Von Neumann method of generating an unbiased coin from a biased coin. Of throwing it twice, and checking if you got HT or TH. And completely discarding all HH or TT results. It doesn't matter if the coin you are using is 20% or 80%, the result will be a true 50/50.
This blew my mind. Thank you!
I had to think about it a bit, so for anyone scratching their head right now trying to figure it out, consider it this way:
what matters is the ordering, of heads-then-tails, or tails-then-heads.
It doesn't matter that it's biased one way or the other, if you keep flipping pairs until you get a result with two different values, it's a 50/50 chance whether the less-likely result comes first, or second.
You might only have a 20% chance of any particular pair having a tails (for example), but in the cases where you do have a tails, it's a 50/50 chance that it comes first or second.
victorbjorklund
If I understand it the Lava lamps are 90% PR/fun. They have a lot of other sources for entropy that scales better.
pverheggen
Yes, they also have wave machines, pendulums, and mobiles :)
https://blog.cloudflare.com/harnessing-office-chaos/
https://blog.cloudflare.com/chaos-in-cloudflare-lisbon-offic...
nyrikki
The original from SGI back in the mid 90's, before CPUs had RDRAND instructions etc... was a an actually practical solution.
At the time I was at the Internet company that originally got online-gaming banned in the US, we were looking at CCDs and Cesium emitters that required a license etc...
While I am not sure, it seems cloudflare basically implemented one after SGI's[0] patent expired.
The patent and the licensing cost and adding SGI was a major blocker for us doing it, the startup closed before we found a real solution. But the best PRNGs like Blum Blum Shub were way too slow at the time. But things did improve quickly at that time.
euroderf
Ant farm ? Hamster wheels ? Anything critter-driven should provide some entropy.
bmitc
> This is why CloudFlare has done what they did with the lava lamp wall.
Interesting. I wonder how true it actually is that they use it like they claim here: https://www.cloudflare.com/learning/ssl/lava-lamp-encryption.... It's in one of their lobbies, so doesn't that make it susceptible to an attack in some way? I'm not knowledgeable enough to know, but I figured if they actually used that method, they'd have a more controlled environment.
I also don't fully understand it. A large part of that wall is static. And the camera isn't going to pick up on the stochastic properties of the lava as much as exists in the real world. So it feels like their images will be very statistically similar.
dheera
The lava lamps are just for show.
You can get entropy just by plugging an oscilloscope into a pile of dirt and cranking the gain up.
adrian_b
Any high-gain amplifier can be used, with its input connected to a resistor or a diode.
For instance you can use the microphone input of a PC, together with an additional external amplifier made with an audio amplifier integrated circuit or an operational amplifier integrated circuit and with a diode or a resistor at its input. The microphone input of PCs provides a 5 V voltage that can be sufficient as a power supply for a noise source plugged in it.
Such a true RNG can be made on a small PCB with an audio jack, so you can plug it into any PC with microphone input and have a true RNG that you can trust better than the RNG included in modern Intel and AMD CPUs. In the past, many AMD CPUs had defective internal RNGs. Moreover, both for Intel and for AMD it is impossible to verify whether the internal RNG does what it claims to do or it generates predictable pseudo-random numbers.
__s
Old games are RTA viable to RNG manip: https://m.youtube.com/watch?v=Bgh30BiWG58
Groxx
Yep - I've seen legitimate-looking dups on bad hardware, and "there are a ton of trailing zeros" is also an incredibly common duplicate mode for some UUID libraries (like earlier Go ones that didn't validate the "requested N bytes, returned 3, you must re-request to get N-3 more" return values. it doesn't happen on most hardware or OSes, so people never check it, so it just comes up in production some day with tens of thousands of collisions).
thecloud
Thanks for the insight! Mind expanding on what alternatives are being used in high reliability systems instead of UUIDv4?
jandrewrogers
In high-reliability systems a criterion for identifier design is easy detection of defective identifiers. This includes buggy systems and adversarial manipulation.
The problem with UUIDs that rely on entropy sources is that it is computationally expensive to detect if the statistical distribution of identifiers is diverging from what you would expect from a random oracle. I've written systems that can detect entropy source anomalies but you'll want to turn it off in production.
It is pretty cheap to sanity check most non-probabilistic identifier schemes. UUIDs that use broken hash algorithms (e.g. UUIDv3/5) or leak state (e.g. UUIDv7) are exposed to adversarial exploitation.
The identifier scheme is dependent on the use case. Does the uniqueness constraint apply to the instance of the object or the contents of the object? Is the generation of identifiers federated across untrusted nodes? How large is the potential universe of identifiers?
The basic scheme I've seen is a 128-bit structured value that has no probabilistic component. These identifiers can be encrypted with AES-128 when exported to the public, guaranteeing uniqueness while leaking no internal state. The benefit of this scheme is that it is usually drop-in compatible with standard UUID even though it is technically not a UUID and the internal structure can carry useful metadata about the identifier if you can decrypt it.
Federated generation across untrusted nodes requires a more complex scheme, particularly if the universe of identifiers is extremely large. These intrinsically have a collision risk regardless of how the identifiers are generated.
All of the standardized UUID really weren't designed with the requirements of scalable high-reliability systems in mind. They were optimized for convenience and expedience which is a perfectly reasonable objective. Most people don't need an identifier system engineered for extreme reliability, even though there is relatively little cost to having one.
eaf7e281
> leak state (e.g. UUIDv7)
But according to PostgreSQL, UUIDv7 provides better performance in the database, so is this essentially a trade off between security and speed?
filcuk
The latest UUID (7?) Uses half random gen, half timestamp. This not only makes it sortable by creation, but would also make a collision like this impossible.
stanmancan
It's still possible in most implementations of UUIDv7.
UUIDv7 assigns the first 48 bits for the timestamp in milliseconds. You can generate a lot of UUID's in a millisecond though!
Then you have another 12 bits that you can use as you wish; "rand_a". The spec has a few methods they suggest on how to use these bits including 12 bits of random data, using it for sub-millisecond timestamps, or creating a monotonic counter, but each have their downsides:
- Purely random data means you can still run into collisions and anything within the same millisecond is unordered
- Sub millisecond you can run into collisions; there's nothing stopping you from generating two UUID's with the same 62 bits of rand_b data in the same sub-millisecond timestamp.
- Monotonic counters can overflow before the next tick, then what? Rollover? Once you roll over it's no longer monotonic and you can generate the same random data within the same monotonic cycle. Also; it's only monotonic to the system that's generating the UUID. If you have a distributed system and they each have their own monotonic cycles then you'll be generating UUID's with the same timestamp + monotonic counter, and again, are relying on not generating the same random data.
You can steal some of the 62 bits in rand_b if you want as well; you can use rand_a for sub-millisecond accuracy, and then use a few bits of rand_b for a monotonic counter. There's still a chance of collision here, but it's exceedingly low at the expense of less truly random data at the end.
If you want truly collision free, you'd also need to assign a couple of bits to identify the subsystem generating the UUID so that the monotonic counter is unique to that subsystem. You lose the ordering part of the monotonic counter this way though, but I guess you could argue that in nearly 100% of cases the accuracy of sub-millisecond order in a distributed system is a lie anyways.
ffsm8
Considering the context I think it's worth pointing out that it's technically not impossible - it's just even less likely.
Everything in crypto is always a probability - never a certainty
majorchord
The spec doesn't require the use of actually random numbers though.
undefined
matt-p
UUIDv7 is arguably better, because it is entropy plus time.
otherme123
It is what I usually use for its sorting, but some people don't want to leak time info.
majorchord
Entropy is not a requirement in the UUID spec.
lazide
Sequences, generally.
perching_aix
How is UUIDv4 to blame for a broken source of entropy? Or am I misinterpreting your words?
hmry
I wouldn't say it's "to blame", but it is more susceptible to bad RNG.
If the RNG is bad, you'll get more benefit from adding non-random bits than you would from additional badly RNG'd bits.
The probability of future collisions also rises the more IDs you generate. If you incorporate non-random bits, you can alleviate that:
- timestamps make the collision probability not grow over time as you accumulate more existing UUIDs that could collide
- known-distinct machine IDs make the collision probability not grow as you add more machines
jandrewrogers
I never blamed UUIDv4 for broken entropy sources. A broken entropy source breaks UUIDv4 even if you are using it correctly.
There is a long history of broken entropy sources showing up in real systems. No matter how hard people try to prevent this it keeps happening. Consequently, a requirement for high-quality entropy sources is correctly viewed as an unnecessary and avoidable foot-gun in high-reliability software systems.
hombre_fatal
Presumably they mean using randomness as unique IDs.
adonovan
For a while we’ve been fixing telemetry-reported crash bugs in the project I maintain, and now hardware bugs are showing up with some frequency. I was amazed how common they are. Sometimes data values (e.g. SP register) are corrupted, but other times even infallible operations (e.g loads of rodata constants) crash, indicating that the instruction itself was corrupted. So, yeah, I believe you’ll eventually see UUID collisions, but not because the underlying cryptanalysis was wrong.
Hizonner
> UUIDv4 is explicitly forbidden for a lot of high-assurance and high-reliability software systems for this reason.
Hmm. What do those systems do for cryptography? Just assume it won't work and not rely on it at all?
jandrewrogers
In these kinds of systems the cryptographic components often aren't even accessible from the software. It isn't a thing you need to worry about.
This makes it easier to audit for use of entropy sources in the software since there really isn't a valid use case for it.
undefined
erikerikson
Super simple to detect and try again.
jandrewrogers
A collision is simple to detect but it requires you to actually check, which is expensive at scale. The entire point of UUIDv4 is that you don't have to check for collisions because it should never happen. But if you don't check and it does happen you are in UB territory which is generally very bad.
A risk of collision before it happens is non-trivial to detect but this is really what you'd want.
erikerikson
Only expensive if you have unsorted keys or lack an index. Neither of which are unscalable.
squirrellous
In this specific case. In the case of trace IDs (an example of which is [1]) where the equivalent of UUIDs are explicitly used to avoid coordination, it’s hard to imagine how you’d reliably detect and retry.
erikerikson
A lot of databases have a uniqueness constraint that is basically a register level compare and replace. Others have a if_not_exists which is nearly the same. If you're not targeting a serious throughput use case, it's enough. If you are then there are lots of solutions/alternatives that completely avoid coordination. On the other hand, maybe tracing protocols are robust to out of order delivery. If that won't do them sequence numbers tied to monotonic sequence IDs should be plenty. If not then I'd need very serious conversations to be convinced you're not wasting everyone's time
throwaway_19sz
Funny story no one will believe, but it’s true. A good friend of mine joined a startup as CTO 10 years ago, high growth phase, maybe 200 devs… In his first week he discovered the company had a microservice for generating new UUIDs. One endpoint with its own dedicated team of 3 engineers …including a database guy (the plot thickens). Other teams were instructed to call this service every time they needed a new ‘safe’ UUID. My pal asked wtf. It turned out this service had its own DB to store every previously issued UUID. Requests were handled as follows: it would generate a UUID, then ‘validate’ it by checking its own database to ensure the newly generated UUID didn’t match any previously generated UUIDs, then insert it, then return it to the client. Peace of mind I guess. The team had its own kanban board and sprints.
Aurornis
> One endpoint with its own dedicated team of 3 engineers
> The team had its own kanban board and sprints.
My early jobs were at startups startups with limited resources. Every decision to build something or hire someone was carefully made after much consideration. This story would have looked like fiction to me at the time.
Later in my career I joined a startup like this where every new concern someone could think up turned into a new microservice with new hires to form a new team. It didn't matter how small it was, everything was a reason to hire new people and form a new team. I sat in meetings where the express goal of the quarter was communicated as growing the engineering team.
It was as weird time. We had this same situation where there were 3-4 person teams who had their own sprints and planning sessions where they would come up with more ways to make work for themselves. Some of them moved so slow that they could spend entire sprints doing tiny changes. Others were working on the most over-engineered solutions you'd ever seen for trivial problems.
There was one meeting where I suggested we re-assign some people on a stable project to work on something that we needed urgently, but I got shut down. That would have removed another excuse to hire more people, which would have conflicted with someone's KPIs to grow the engineering team to a specific number
kypro
> My early jobs were at startups startups with limited resources. Every decision to build something or hire someone was carefully made after much consideration. This story would have looked like fiction to me at the time.
This was pre-2015
> Later in my career I joined a startup like this where every new concern someone could think up turned into a new microservice with new hires to form a new team. It didn't matter how small it was, everything was a reason to hire new people and form a new team. I sat in meetings where the express goal of the quarter was communicated as growing the engineering team.
This was post-2015
---
Am I right?
You're describing exactly what I've tried to express in various comments. There was a point in the latter half of the 2010s when it became genuinely hard to find tech work where you were building useful stuff. Startups become increasingly absurd and the focuses of their engineering teams even more so.
In 2019 I was working for a company who were so desperate to hire new engineers at one point they decided to just start offering jobs to candidates which failed interviews. It was absolutely insane.
swiftcoder
Ah, the heady days when we shipped a new AWS service with a team of 40, and when I came into work the next day we had 120 people and 80 of them were just inventing work out of whole cloth…
mihaaly
> someone's KPIs to grow the engineering team to a specific number
Sigh!
Specific numbers!
I believe a more common specific number is the yearly EBITDA or ARR (or some other acronyms in this alley I care zero about to memorize) nowadays, for investor's sake. Like in our company. Since we were acquired - and some time before - the only talk in company meetings are EBITDA, ARR, compared to a number dreamed up by someone and to be reached in 5 years time. Specific financial results in specific timeframe. Our goals are specific numbers being above today's numbers by a chosen margin. The company talk are marketing campaigns and reach, campaign efficiency measurements, pricing strategies, subscription centric licensing, sales strategies, churn, and other slang around customer bullying I also do not care about, also organizational streamlining - what a loaded word! -, bla bla bla, all for the specific sacred number put up on the pedestal.
What we have zero talk about? Functionality, engineering.
I seriously do not understand these people. Why are they fiddling around with selling software in a niche sensitive to global economic fluctuations insted of selling ... I don't know. Shoes? Or better yet sugary water ... no, better is vitamin water ... no, the trendiest is protein water. That is something that needs no balanced functionality and engineering that is laborous so it is resource intensive to achieve. And is in the way of reaching the sacred number put up there. Engineers are in the way towards our goals. We are pulling back the cart! We are cost center now!!
I do not stay long.
wongarsu
At some point someone optimizes the system to a global company-wide incrementing 128 bit counter. Instead of needing a costly database lookup against a growing database the microservice just fetches the current counter, increments it by one and hands out the new value. Easy, fast O(1) operation.
This even allows you to shard the service to provide high availability and distribute the service globally to reduce latency. Just give each instance a dedicated id range it can hand out. I'd suggest reserving some of the high bits to indicate data center id, and a couple more bits for id-generator instance within that dc.
Wait a second, this starts to look familiar ... does Twitter still do that, or did they eventually switch?
kuratkull
Define a random 128 bit key that you will never change. Use that key to encrypt 128 bit integers in sequence using AES-128, each one comes out as a, for all practical purposes, unique unpredictable ID.
pinkmuffinere
> each one comes out as a, for all practical purposes, unique unpredictable ID
I don't have much cryptography experience, but this seems _suuuuper_ suspicious. I think the "for all practical purposes" is doing a lot of lifting here? If it was this easy, surely this is what we'd use, and there wouldn't be UUID v4 to begin with.
sheept
Twitter snowflakes haven't changed. Most of the bits go to the timestamp, which I guess is a global incrementing counter as you described
throw0101c
> At some point someone optimizes the system to a global company-wide incrementing 128 bit counter.
Some UUID versions include time, so there's a bit of a counter in that.
kristjansson
What is the arrow of time if not a single global monotonically increasing sequence?
roryirvine
I've seen similar, buried deep within a major SV tech co.
Their process was a bit more complex because the master list of in-use UUIDs was stored in an external CMDB service run by a different department. They got a daily dump of that db, so were able to check that when generating a "provisional" id. Only once it had been properly submitted to the CMDB did it became "confirmed".
They had guardrails in place to prevent "provisional" ids being used in production, and a process for recycling unused "confirmed" ids. Oh, and they did regular audits which were taken very seriously by management.
Last I heard, they were 18 months into a 6 month project to move their local database cache to Zookeeper...
DonHopkins
They should upgrade to Zookeeper II: Zookeepier.
giancarlostoro
I can believe it, and I often wondered "can I win the UUID misfortune lottery" I wonder if this is equally common with Microsoft's flavor aka GUIDs.
tracker1
GUIDs are UUIDs are effectively the same thing... the issues often come down the the means of generation and storage... where UUID have versions with specific implementation details that aren't always followed, MS has internal implementations that also aren't always followed. Also worth being aware of are COMB, SequencialIDs (MS-SQL) and other serialization approaches as well as how they affect indexes in practice.
Alternatives include sequencial number generator services, or sequence services that may be entirely sequencial, etc, but may lead to out of order inserts in practice.
Also, generally worth considering UUIDv7 assuming your sotrage and indexing use the time portion at the front of the index process.
CodeWriter23
I get the microservice to ensure this. But 3 people dedicated to it? I guarantee you they spent their days trudging dungeons, playing CoD and ping pong.
halfcat
You need at least 3 for this. People go on vacation, turnover, can’t risk losing that critical institutional knowledge.
mrbonner
We have had a service to add two numbers. What make you think this is not realistic? :-)
morkalork
I too have witnessed a "add two numbers" service! Turns out you can be too extreme with rules for isolating out business logic..
Schiendelman
Same! It had validation on each number before adding them. Poor design, but that's how it worked.
ssalka
At one of my previous jobs, there was a function `createEntityWithRandomUUID` which would basically do the same thing as a light wrapper around database inserts. If a conflict occurred, it would generate a new ID and try again, up to 5 times I think. No logging to indicate whether any conflict actually ever happened.
other_herbert
No that kind of critical data would be sent to pendo so it could be reported on or shown in a dashboard!
LocalH
I'd believe it.
What I'd find harder to believe is that it wasn't really a table with more information than just "list of assigned UUIDs". I'd be really surprised (pleasantly!) if it was only that. I'd figure most startups would make sure that table links to customer info so that they know which customer has a specific UUID, for easy searching and crossreferencing with the main db
tomjakubowski
That sort of table can be quite handy when every entity in the business's data stew is identified with a UUID, and there is no way of telling just from looking at an identifier what kind of entity it is. Particularly when the business has disparate databases and/or microservices with their own sets of UUIDs.
In such businesses, inevitably, someone will ask you to run process X for widget 8dbcd950-14c1-4877-a8b0-90c081ce033c, and that particular identifier will actually be an ID of some associated data, not the widget. You can push back and say, "That isn't a widget identifier, can you please look up the widget identifier?" It's better to be able to look that ID up in your ID ⮕ entity type lookup table, and say "the ID you provided is a widget production run ID, which produced a copy of widget a84969be-137a-41ca-97c4-515497184df9. Can you confirm this is the widget you need process X done for?", with a link to the product-facing widget page.
(Also handy for the case where some code was intended to log an ID for one entity, but actually logs the ID for an associated entity with the wrong entity type indicated.)
CodesInChaos
This is usually caused by an insufficently seeded PRNG.
Are you generating the UUID in the backend, or the frontend? Frontend is fundamentally unreliable for many reasons, including deliberate collisions. So if that case you'll need to handle collisions somehow. Though you can still engineer around common sources of collisions, the specifics depend on the environment.
On the other hand making a backend reliable is feasible. What kind of environment is your code running in? Historically VMs sometimes suffered from this problem, though this should be solved nowadays. Heavily sandboxed processes might still run into this, if the RNG library uses an unsafe fallback. Forking processes or VMs can cause state duplication and thus collisions.
danpalmer
I remember hearing about Segment (analytics company) had their entire product based around UUIDs generated in web browsers. There were collisions all over the place, the product was seemingly incapable of producing useful data at a fundamental level because of it. Hopefully they've fixed that now.
_kst_
This reminds me of a passage from the book "Pro Git".
<https://git-scm.com/book/en/v2>
"Here’s an example to give you an idea of what it would take to get a SHA-1 collision. If all 6.5 billion humans on Earth were programming, and every second, each one was producing code that was the equivalent of the entire Linux kernel history (6.5 million Git objects) and pushing it into one enormous Git repository, it would take roughly 2 years until that repository contained enough objects to have a 50% probability of a single SHA-1 object collision. Thus, an organic SHA-1 collision is less likely than every member of your programming team being attacked and killed by wolves in unrelated incidents on the same night."
Deliberate collisions are addressed in the following paragraph.
SHA-1 hashes are not random, so the issue of poor pseudo-random number generation doesn't apply as it does to uuidv4. And SHA-1 hashes are 160 bits, vs. 128 for uuidv4.
But I love the idea of unrelated wolf attacks.
mega_dean
Reminds me of this page with an example for understanding how many permutations there are for a shuffled deck of cards: https://czep.net/weblog/52cards.html
> So, just how large is it? Let's try to wrap our puny human brains around the magnitude of this number with a fun little theoretical exercise. Start a timer that will count down the number of seconds from 52! to 0. We're going to see how much fun we can have before the timer counts down all the way. Shall we play a game?
> Start by picking your favorite spot on the equator. You're going to walk around the world along the equator, but take a very leisurely pace of one step every billion years. The equatorial circumference of the Earth is 40,075,017 meters. Make sure to pack a deck of playing cards, so you can get in a few trillion hands of solitaire between steps. After you complete your round the world trip, remove one drop of water from the Pacific Ocean. Now do the same thing again: walk around the world at one billion years per step, removing one drop of water from the Pacific Ocean each time you circle the globe. The Pacific Ocean contains 707.6 million cubic kilometers of water. Continue until the ocean is empty. When it is, take one sheet of paper and place it flat on the ground. Now, fill the ocean back up and start the entire process all over again, adding a sheet of paper to the stack each time you’ve emptied the ocean. Do this until the stack of paper reaches from the Earth to the Sun. Take a glance at the timer, you will see that the three left-most digits haven’t even changed. You still have 8.063e67 more seconds to go. 1 Astronomical Unit, the distance from the Earth to the Sun, is defined as 149,597,870.691 kilometers. So, take the stack of papers down and do it all over again. One thousand times more. Unfortunately, that still won’t do it. There are still more than 5.385e67 seconds remaining. You’re just about a third of the way done.
dalmo3
Damn, I got the paper stack wet with all that ocean water. Guess I'm starting again from scratch...
swiftcoder
On the other hand, it turns out that pre-image attacks are quite feasible, and as several people who have thoughtlessly committed the pre-image attack test case files to git can attest… quite problematic
TacticalCoder
Hasn't the Git team been hard at work to optionally offer other hashes, like SHA256, in addition to SHA-1?
ted_dunning
They have been not at work on doing that.
e12e
Some discussion here:
https://github.com/uuidjs/uuid/issues/546
Eg:
> FWIW, I just tested crypto.getRandomValues() behavior on googlebot and it is also deterministic(!)
D2OQZG8l5BI1S06
That makes sense. I'm not sure why anybody would generate UUIDs in browsers though, it seems to defeat the purpose.
danpalmer
Tell that to Segment. Hopefully they've fixed that, but they didn't seem to think it was a problem years ago (spoiler: it was a big problem).
adyavanapalli
What you're talking about is so extremely rare that it's much more likely that the entire Earth is destroyed by an asteroid right this inst...
thomasmg
It is not quite as rare. I calculated it to be less common than being hit by a meteorite, and added a section about that and the Birthday Paradox to Wikipedia, to the article about UUIDs. It got removed / replaced a few years ago however. (If my source was correct, there was actually a woman hit by a meteorite, but she survived, with a leg injury.)
If you do have a UUID collision, chances are extremely high that it's either a software bug, or glitch in the computer. It could be a cosmic ray. Cosmic rays messing with the computer memory or CPU are actually relatively common.
delichon
About as rare as an asteroid typing an ellipsis and clicking the add comment button.
throw0101c
Well, this joke dates back to (at least) the dial-up days where {#`%${%&`+'${`%& NO CARRIER
xerox13ster
That’s just a result of jounce from localized gravity effects and atmospheric pressure disturbances in the moments before impact.
Think the ultrasonic typing hacking scene in Pantheon combined with the keyboard bouncing due to rumbling.
spindump8930
It's very common if you improperly seed, as others in the thread brought up! Or in your framing, as rare as earth getting hit if it were surrounded by a sci-fi density asteroid field.
sebazzz
Well it would be statistically even rarer for that UUID collision to happen and the earth to be destroyed by an asteroid.
crazylogger
For a single database using UUIDs, yes, it's astronomically rare. But it's quite a different thing to say that no computer system on Earth has ever experienced a UUID collision. The number of systems out there is also astronomical.
nathanmills
>The number of systems out there is also astronomical.
Not even close
moi2388
Sure it does. Planets are astronomical, and we only have 8 of those in our solar system.
juancn
Something off on how the RNG is initialized? Lack of entropy?
If the rng is not customized it will use:
const rnds8 = new Uint8Array(16);
export default function rng() {
return crypto.getRandomValues(rnds8);
}
Hizonner
It's a near certainty that something is badly wrong with the RNG, and, yes, probably in how it's seeded.
It's probably messing up the cryptography, too.
Onavo
But defaults should be sane and safe. RNG isn't the sort of thing you want to be messing up. Every JS dev was taught that Math.random is not safe by default, but the crypto package is.
undefined
Geee
According to the many-worlds interpretation of quantum mechanics, there's bound to be one branch of universe where every UUID is the same. Can you imagine what those guys are thinking?
BobaFloutist
Not only that, there's vastly more where every UUID except one is the same, but they never got to that one because they didn't ever use them.
Or where the first two are unique, but every following one is one of the first two.
nyantaro1
This is why I am not a fan of the Everett approach
zeeveener
"Huh, this is just an identity function. Cool. Let's move on."
pif
All the comments I've been able to read are missing the elephant in the room: no high-quality entropy source can turn a "should" into a "must".
If you want something that is difficult to guess, ask the cryptography guys. But if you need something that is -_guaranteed_ unique, you must build it yourself.
mittermayr
I fully agree. It makes no sense. Yet...
The only guesses I'm having is that we originally generated UUIDv4s on a user's phone before sending it to the database, and the UUID generated this morning that collided was created on an Ubuntu server.
I don't fully know how UUIDv4s are generated and what (if anything) about the machine it's being generated on is part of the algorithm, but that's really the only change I can think of, that it used to generated on-device by users, and for many months now, has moved to being generated on server.
AntiUSAbah
You let users generate a UUID?
To be honest, the chance that you are doing something weird is probably higher than you experiencing a real UUID conflict.
How did your database 'flag' that conflict?
mittermayr
user-generated (as in: on the user's phone) was only at the very early stages of this product, and we've since moved to on-server. It's a cash-register type of app, where the same invoice must not be stored twice. So we used to generate a fresh invoice_id (uuidv4) on the user's device for each new invoice, and a double-send of that would automatically be flagged server-side (same id twice). This has since moved on to a server-only mechanism.
The database flagged it simply by having a UNIQUE key on the invoice_id column. First entry was from 2025, second entry from today.
tracker1
Assuming the phone is using the default JS engine, it's whatever is being shimmed for node:crypto package's random bytes method... which is likely weaker.
I wrote a different implementation that cheats by using browser's methods of getting a uuid.
https://github.com/tracker1/node-uuid4/blob/master/browser.m...
bitsandbits
If the server or the user's phone had the wrong time and if the date is used in generating the ID...
wongarsu
If it's UUIDv4 and you validate that the UUID is valid and not conflicting I don't really see the issue with user-generated UUIDs. Being able to generate unique keys in an uncoordinated manner is the main selling point of UUIDs
Sure, it's something I'd flag in any design to spend two minutes to talk about potential security implications. But usually there aren't any
JambalayaJimbo
The whole point of UUIDv4 is that you don't need to check if it's conflicting and can just use them right away. This falls apart if you let untrusted sources of UUIDv4's enter your system IMO
AntiUSAbah
Validation etc. every thing which should not be controlled by a user, will not be controlled by a user.
tracker1
Likely a unique index... duplicate insert on a primary or 1:! foreign key. I am currently shimming out a process that will add a trackingid for a job service, and just had my method stub retorn Guid.Empty... second time I ran my local test it blew up on the duplicate key... then I switched it to null, then it blew up again... I neglected to exclude null from the unique index on the foreign key.
In any case, it's easy enough to do. I mostly use UUDv7, COMB or NEWSEQUENTIALID ids myself though.
nubinetwork
The smart way would be to check if the id is in use, and generate a new one... Repeat a few times if you're extremely unlucky, and bail out with an error if you have the absolute worst rng. It also works for locally generated ids as well.
wongarsu
If it was two on-device generated UUIDs I could see a collision happening. There have been instances of cheap end devices not properly seeding their random number generators, leading to colliding "random" values. And cases of libraries using cheap RNGs instead of a proper cryptographic RNG, making it even worse
But on a server that shouldn't happen, especially not in 2026 (in the past, seeding the rngs of VMs used to be a bit of an issue). Even if one UUID was badly generated, a truly random UUID statistically shouldn't collide with it. You'd need an issue in both generators
tracker1
The library is using node:crypto, but with a phone target, that's likely shimmed with a JS implementation...
stubish
The UUIDv4 collision is statistically extremely unlikely. What is more likely is both systems used the same seed. This might be just a handful of bytes, increasing the chance of collision to one in billions or even millions.
tracker1
The shim for node:crypto in the browser is likely a weaker implementation in JS than the node implementation... you can cheat and use the browser itself to get a UUIDv4...
function uuid4() {
var temp_url = URL.createObjectURL(new Blob());
var uuid = temp_url.toString();
URL.revokeObjectURL(temp_url);
return uuid.split(/[:\/]/g).pop().toLowerCase(); // remove prefixes
}lazyjones
Better check what crypto.js is actually doing in your exact setup. Weak polyfills exist...
dweez
Good moment to revisit this fun article: https://jasonfantl.com/posts/Universal-Unique-IDs/
If the entire universe were turned into a giant computer and did nothing but generate uuids until its heat death, how many bits would you need for the ID space?
CodeWriter23
If you're gonna go there, this is obligatory https://www.decisionproblem.com/paperclips/
ipaddr
"But are you worried that every human on Earth will be hit by a meteorite right now? That probability is also non-zero, yet it is so infinitesimally small that we treat it as an impossibility."
This might be a bad example because one meteorite could take out the world and given enough time is likely to.
beejiu
Are your UUIDs generated client side or server side? If it's client side, it could be due to a crawling bot. Googlebot for example executes Javascript using deterministic "randomness".
adzm
Googlebot's lack of randomness was the conclusion of a previous incident for that package https://github.com/uuidjs/uuid/issues/546
AgentME
Yeah, the answer almost certainly has to be this, or that they were using an old version of the package which didn't use the system RNG correctly (the current version appears to do it correctly, but I didn't dive into older versions), or their project has loaded an old broken polyfill re-implementing the JS crypto API, or they were running this on a hosting setup that does something jank like resuming the same VM snapshot with its RNG state on multiple servers. This category of explanation is many orders of magnitude more likely than a true random collision.
Get the top HN stories in your inbox every day.
I know what you're thinking... and I still can't believe it, but...
This morning, our database flagged a duplicate UUID (v4). I checked, thinking it may have been a double-insert bug or something, but no.
The original UUID was from a record added in 2025 (about a year ago), and today the system inserted a new document with a fresh UUIDv4 and it came up with the exact same one:
b6133fd6-70fe-4fe3-bed6-8ca8fc9386cd
We're using this: https://www.npmjs.com/package/uuid
I thought this is technically impossible, and it will never happen, and since we're not modifying the UUIDs in any way, I really wonder how that.... is possible!? We're literally only calling:
import { v4 as uuidv4 } from "uuid";
const document_id = uuidv4();
... and then insert into the database, that's it.
Additionally, the database only has about 15.000 records, and now one collision. Statistically... impossible.
Has that ever happened to anyone?! What in the...