11 ms·
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 def
by jandrewrogers 6mo ago
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.
- thecloud 6mo agoThanks for the insight! Mind expanding on what alternatives are being used in high reliability systems instead of UUIDv4?
- lazide 6mo agoSequences, generally.
- tremon 6mo agoThat depends on your definition of high-availability. If high availability includes distributed writers, (global) sequences are not the best solution because generating unique sequence values requires synchronisation between all writers. In those cases, you might need to explicitly partition the ID space so that individual writers are guaranteed not to get in each others' hair.
- lazide 6mo agoThat is merely a sequence generation strategy.
- filcuk 6mo agoThe 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.
- ffsm8 6mo agoConsidering 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
- nitsky 6mo agoTrue, but it makes the specific collision the post observed completely impossible.
- stanmancan 6mo agoI left a more detailed comment on the parent, but it's definitely not impossible!
- ryanmonroe 6mo agoThe scenario in this post is that the first uuid was created one year before the duplicate uuid. That isn’t possible with v7
- ffsm8 6mo agoYou're heavily leaning on "collision like this" to relate to the exact time stamps for your statement to be true. It's equality possible to interpret the "like this" to the collision itself, without a focus on the 1 year distance between the creation dates. So I guess both views are valid.
- calfuris 6mo agoThe inclusion of a timestamp in v7 makes collisions impossible unless the generating systems think that the time is the same down to the millisecond, which makes the temporal distance quite relevant.
- 6mo ago
- jandrewrogers 6mo agoIn 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 6mo ago> 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?
- jubilanti 6mo agoYes, because UUIDv7 gives up some random bits in order to include the timestamp, which is done in a way that makes UUIDv7s quick to sort by timestamp.
- matt-p 6mo agoUUIDv7 is arguably better, because it is entropy plus time.
- otherme123 6mo agoIt is what I usually use for its sorting, but some people don't want to leak time info.
- majorchord 6mo agoEntropy is not a requirement in the UUID spec.
- perching_aix 6mo agoHow is UUIDv4 to blame for a broken source of entropy? Or am I misinterpreting your words?
- hombre_fatal 6mo agoPresumably they mean using randomness as unique IDs.
- hmry 6mo agoI 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 6mo agoI 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.
- LocalH 6mo agoThis 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
- victorbjorklund 6mo agoIf I understand it the Lava lamps are 90% PR/fun. They have a lot of other sources for entropy that scales better.
- deleted 6mo ago[deleted]
- erikerikson 6mo agoSuper simple to detect and try again.
- jandrewrogers 6mo agoA 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 6mo agoOnly expensive if you have unsorted keys or lack an index. Neither of which are unscalable.
- orf 6mo agoAKA centralising a decentralised identifier generator?
- erikerikson 6mo agoThere are better approaches like pre -avoiding collisions but generating tends to be more expensive than checking.
- orf 6mo agoIn what world is generating a UUID more expensive than checking for duplicates? at any scale? Walk me through that please
- erikerikson 6mo agoYeah, that was a little sloppy but it's generating is more expensive than not generating. In more words, generating an id and validating uniqueness is more expensive than only validating uniqueness.
- Groxx 6mo agoYep - 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).
- Hizonner 6mo ago> 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 6mo agoIn 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.
- aaron695 6mo ago[dead]
- ranger_danger 6mo agoReading the UUID spec leads me to believe that good entropy is not even a requirement for any version: > Implementations SHOULD utilize a cryptographically secure pseudorandom number generator (CSPRNG) to provide values that are both difficult to predict ("unguessable") and have a low likelihood of collision ("unique"). From https://www.rfc-editor.org/rfc/rfc9562.html#unguessability https://www.rfc-editor.org/rfc/rfc9562.html#unguessability So I don't think technically we can say entropy or random numbers at all are even "required for UUIDv4 to work as advertised."
- toast0 6mo agoAny PRNG, including a CSPRNG is simple to predict if you know its inputs. You need entropy to seed your CSPRNG.
- ranger_danger 6mo agoI think you misunderstood the meaning of the word "SHOULD" in the spec. It means it's not strictly necessary, as in, a PRNG is not a requirement in order to support UUIDs in a compliant way. To me this means UUID itself is not a viable solution if randomness is a requirement for you, because even if one claims they are using a UUID implementation that is compliant with the spec, and it is in fact compliant, that doesn't mean it's actually random at all.
- adonovan 6mo agoFor 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.
- BrandoElFollito 6mo ago> We just had an actual UUID v4 collision... (...) > This is surprisingly common And there goes though the window my blind faith with UUID v4 :) I recently read about UUID v7 (https://en.wikipedia.org/wiki/Universally_unique_identifier#Version_7_(timestamp_and_random) https://en.wikipedia.org/wiki/Universally_unique_identifier#...) that became my favourite random identifier.
- iberator 6mo agowhat else so you suggest instead of uuuid4?