Live data from Hacker News

Ask HN: We just had an actual UUID v4 collision...

news.ycombinator.com

141–150 of 369 posts

Re: Ask HN: We just had an actual UUID v4 collision...

#141

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.…

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

Re: Ask HN: We just had an actual UUID v4 collision...

#142
post #136
post #132

Earlier quoted context omitted.

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

True, but it makes the specific collision the post observed completely impossible.

I left a more detailed comment on the parent, but it's definitely not impossible!

Re: Ask HN: We just had an actual UUID v4 collision...

#143
post #82

Earlier quoted context omitted.

Actually asking ChatGPT this query led it giving me this UUID "550e8400-e29b-41d4-a716-446655440000" which happens to be a very common example UUID

The LLM is mechanistically unable to pick something actually random and outside of its training distribution, so... yep.

If you ask it to construct a UUID character by character you should get a somewhat random one, just because of temperature.

Re: Ask HN: We just had an actual UUID v4 collision...

#144

Please, do not use b6133fd6-70fe-4fe3-bed6-8ca8fc9386cd, I checked my database and I was using it already.

I knew it, we're all getting the same cheap UUIDs and the good ones are reserved for the big dogs.

You mean you’re not already entropymaxxing? n00b

Re: Ask HN: We just had an actual UUID v4 collision...

#145

Earlier quoted context omitted.

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?

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…

If the server or the user's phone had the wrong time and if the date is used in generating the ID...

Re: Ask HN: We just had an actual UUID v4 collision...

#146

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…

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?

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.

Re: Ask HN: We just had an actual UUID v4 collision...

#147

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’…

This is the software industry version of "The Onion".

Re: Ask HN: We just had an actual UUID v4 collision...

#149

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.…

Thanks for the insight! Mind expanding on what alternatives are being used in high reliability systems instead of UUIDv4?

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.

Re: Ask HN: We just had an actual UUID v4 collision...

#150

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.…

[deleted]
Post reply on HN