Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

news.ycombinator.com

Post reply on HN
Print view View original

321–330 of 369 posts

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

#321

Post by ranger_danger »

toast0 wrote: post #317
ranger_danger wrote: post #267

Earlier quoted context omitted.

Reading 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 So I don't think technically we ca…

Any PRNG, including a CSPRNG is simple to predict if you know its inputs. You need entropy to seed your CSPRNG.

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

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

#322

Post by pyuser583 »

ms_menardi wrote: post #284
greiskul wrote: post #233

Earlier quoted context omitted.

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

> 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, conside…

Oh wow that’s really amazing. What’s the source - I love Von Neumann.

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

#323

Post by pyuser583 »

nyrikki wrote: post #270
victorbjorklund wrote: post #166

Earlier quoted context omitted.

If I understand it the Lava lamps are 90% PR/fun. They have a lot of other sources for entropy that scales better.

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…

SGI was pretty amazing. I know some folks who worked there - Cray too. There’s a loyalty that just doesn’t exist any more - and arguably isn’t earned anymore.

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

#324

Post by pyuser583 »

amelius wrote: post #231
BSVogler wrote: post #181

Earlier quoted context omitted.

I once read that noise of camera in total darkness is apparently a good source.

You can already have a good entropy source from a single resistor. https://en.wikipedia.org/wiki/Johnson%E2%80%93Nyquist_noise

This is what gets me - entropy is hard, but not that hard. I get it goes against everything a computer is built to do, but so does telling time.

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

#326

Post by cdaringe »

taegee wrote: post #294
susam wrote: post #289

Earlier quoted context omitted.

And for people who like equations, here is my attempt at explaining it. Assume each flip is independent and the bias remains same in each flip. Let P(H) = p, P(T) = 1 - p. Then P(HH) = p^2, P(HT) = p(1 - p), P(TH) = (1 - p)p, P(TT) = (1 - p)^2. Therefore P(HT or TH) = 2p(1 - p). Now calculate P(HT | HT or TH) = p(1 - p) / (2p(1 - p)) = 1/2, P(TH | HT or TH) = (1 - p)p / (2p(1 - p)) = 1/2.

You don't need conditional probability here, as the flips are independent. It's just p(H)p(T). And p(H)p(T) = p(T)p(H), thus 2*p(H)p(T) = 2p(1-p).

Thats how i noodled thru it internally

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

#327

Post by zimmund »

smokel wrote: post #200
mh2753 wrote: 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

Actually, asking this multiple times to ChatGPT gives me different UUIDs every time, and it checked with a web search that they are not found in public data.

That's because of tokens (and temperature). You could piece back the tokens to parts of existing tokens in public data. And given enough iterations, GPT will probably start showing noticeable patterns (since it's not actually random).

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

#328

Post by erlkonig »

I keep telling the dev teams I'm on that with enough data points, all those random numbers will (probably) eventually collide, and *then* we'll see how robust their software really is. At least your database flagged it, and hopefully nothing major exploded.

And yet, plenty of experienced devs, including team leads and CIOs, are convinced it's impossible. As in, they absolutely don't write code to deal with the condition. So a bad RNG can randomly destroy the system far sooner than expected at any time, and it won't be noticed, caught, re-genned, or anything, with concurrent corruption being entirely possible. They're fine with it. I feel like these are the same guys who don't check to see if malloc() succeeds.

I like to ask them, "If it's impossible, you're using too many bits, right?". I haven't talked any of them into hedging with a brownian motion detector, or a lava lamp or something for better randomness yet, but I'm still trying.

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

#329

Post by erlkonig »

filcuk wrote: post #124
thecloud wrote: post #113

Earlier quoted context omitted.

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

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.

Almost impossible, it depends on how fast they're being generated and the precision of the timestamp. The real problem is two years later when someone finds and removes that usleep(10000); /* sleep 10 µs */ that was the hard speed brake needed for the UUID generator, and suddenly duplicate IDs start showing up a few times per day or something similar.
Post reply on HN