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

Guid Smash

guidsmash.com

Post reply on HN
Print view View original

51–60 of 72 posts

Re: Guid Smash

#51

Post by Xelbair »

twiss wrote: post #5

> The chances of generating two GUIDs that are the same is astronomically small. > The odds are 1 in 2^122 — that’s approximately 1 in 5,000,000,000,000,000,000,000,000,000,000,000,00. This is true if you only generate two GUIDs, but if you generate very many GUIDs, the chance of generating two identical ones between any of them increases. E.g. if you generate 2^61 GUIDs, you have about a 1 in 2 chance of a collision…

i have seen in my life two guid collisions already. and i'm not that old.

One of them was genuine - generated by different systems, and it was caught when loading data from one to another - object had same ID, but different underlying type.

Other one was due to 'error' - two systems(by different companies, supporting the same data exchange standard) used magic hardcoded guid that turned out to be the same.

Both of those systems have full audit trail - each change created new row in database and IDs were formatted as {NAMESPACE}.{GUID}.{TIMESTAMP}. Mutation of an object created new entry with different {TIMESTAMP} part. Namescapes are mandated by standard, so different systems can have the same namespace value.

Re: Guid Smash

#52

Post by kaoD »

8organicbits wrote: post #25
kaoD wrote: post #22

Earlier quoted context omitted.

You have to generate 2^37 (137,438,953,472) UUIDv7s in the exact same millisecond to have a 50% chance of collision. (Not disagreeing with you, just adding perspective.)

The math is interesting here as you'll probably want to run your system for several years, not just a single millisecond. So it's a repeated trials problem. I spent some time trying to figure out the ID generation rate that would be a "break even point" between UUIDv4 vs UUIDv7, but I didn't trust the answer I got. (Agreeing with both parents)

Good observation. Could you share the math even if you don't trust it? I don't have pen and paper here and I'm curious.

After thinking it more, I have the feeling (against my initial intuition) that v4 might dominate either way unless you consistently generate tons of UUIDs for an impractical number of years.

Re: Guid Smash

#53

Post by Vvector »

Spooky23 wrote: post #49
arcanemachiner wrote: post #41

Earlier quoted context omitted.

I always assumed that intuitively... I think the number is 20 people for the birthday paradox. 20 x 20 = 400, and there are ~365 days in a year. Is that how that works?

I was always surprised the math maths for birthdays. Human birthdays are not random, and cluster around various dates and seasonal patterns.

Here is a statistical analysis of birthdays https://www.zippia.com/advice/most-least-common-birthdays/

Re: Guid Smash

#54

Post by _alternator_ »

Xelbair wrote: post #51
twiss wrote: post #5

> The chances of generating two GUIDs that are the same is astronomically small. > The odds are 1 in 2^122 — that’s approximately 1 in 5,000,000,000,000,000,000,000,000,000,000,000,00. This is true if you only generate two GUIDs, but if you generate very many GUIDs, the chance of generating two identical ones between any of them increases. E.g. if you generate 2^61 GUIDs, you have about a 1 in 2 chance of a collision…

i have seen in my life two guid collisions already. and i'm not that old. One of them was genuine - generated by different systems, and it was caught when loading data from one to another - object had same ID, but different underlying type. Other one was due to 'error' - two systems(by different companies, supporting the same data exchange standard) used magic hardcoded guid that turned out to be the same. Both of th…

There are either bugs in the system or the GUID isn’t random. The first case you mention is probably both TBH; the second case is probably due to non-randomness (generating via namespace/timestamp leads to collisions when two objects are generated simultaneously).

Re: Guid Smash

#55

Post by Zambyte »

kaoD wrote: post #52
8organicbits wrote: post #25

Earlier quoted context omitted.

The math is interesting here as you'll probably want to run your system for several years, not just a single millisecond. So it's a repeated trials problem. I spent some time trying to figure out the ID generation rate that would be a "break even point" between UUIDv4 vs UUIDv7, but I didn't trust the answer I got. (Agreeing with both parents)

Good observation. Could you share the math even if you don't trust it? I don't have pen and paper here and I'm curious. After thinking it more, I have the feeling (against my initial intuition) that v4 might dominate either way unless you consistently generate tons of UUIDs for an impractical number of years.

I ran some numbers by GPT-5[0], and for the scenario of generating 10k UUIDs in one ms every 10ms, over three years, it came up with a 0.0025% chance of collision for UUIDv7, and a 0.000000084% chance for collision with UUIDv4.

[0] https://kagi.com/assistant/dd7d8c48-44e4-499b-9f2f-33663d125...

Re: Guid Smash

#56

Post by somat »

twiss wrote: post #5

> The chances of generating two GUIDs that are the same is astronomically small. > The odds are 1 in 2^122 — that’s approximately 1 in 5,000,000,000,000,000,000,000,000,000,000,000,00. This is true if you only generate two GUIDs, but if you generate very many GUIDs, the chance of generating two identical ones between any of them increases. E.g. if you generate 2^61 GUIDs, you have about a 1 in 2 chance of a collision…

2^61 guids is... 36 exabytes, if my napkin math is correct. when storing them in binary format(16 bytes each) if doing the javascript thing and storing them as strings... (shudders) I don't even want to think about it.

Anyhow that was my first thought when you mentioned 2^61 guids, where are you even going to put them? second thought, I don't think enumerating 2^61 guids is trivial, in fact, I suspect it would take longer than anyone would be willing to spend, and if you are not storing them why are you generating them?

And what even is a guid collision attack? it is not like they are a hash, and since they tend to be public identifiers it turns out despite their stated use to prevent collisions, you can't really use guids generated by others(if they wanted collisions they would straight up just copy yours) so you end up regenerating them anyway.

Re: Guid Smash

#57

Post by ivanstepanovftw »

Xelbair wrote: post #51
twiss wrote: post #5

> The chances of generating two GUIDs that are the same is astronomically small. > The odds are 1 in 2^122 — that’s approximately 1 in 5,000,000,000,000,000,000,000,000,000,000,000,00. This is true if you only generate two GUIDs, but if you generate very many GUIDs, the chance of generating two identical ones between any of them increases. E.g. if you generate 2^61 GUIDs, you have about a 1 in 2 chance of a collision…

i have seen in my life two guid collisions already. and i'm not that old. One of them was genuine - generated by different systems, and it was caught when loading data from one to another - object had same ID, but different underlying type. Other one was due to 'error' - two systems(by different companies, supporting the same data exchange standard) used magic hardcoded guid that turned out to be the same. Both of th…

Sorry, when I was young I did not know what these `public static final UUID` mean, so I copied them.

Re: Guid Smash

#58

Post by phyzome »

Xelbair wrote: post #51
twiss wrote: post #5

> The chances of generating two GUIDs that are the same is astronomically small. > The odds are 1 in 2^122 — that’s approximately 1 in 5,000,000,000,000,000,000,000,000,000,000,000,00. This is true if you only generate two GUIDs, but if you generate very many GUIDs, the chance of generating two identical ones between any of them increases. E.g. if you generate 2^61 GUIDs, you have about a 1 in 2 chance of a collision…

i have seen in my life two guid collisions already. and i'm not that old. One of them was genuine - generated by different systems, and it was caught when loading data from one to another - object had same ID, but different underlying type. Other one was due to 'error' - two systems(by different companies, supporting the same data exchange standard) used magic hardcoded guid that turned out to be the same. Both of th…

Both vendors probably copied that GUID from the same place.

Re: Guid Smash

#59

Post by 8organicbits »

Retr0id wrote: post #42
mmoskal wrote: post #30

Earlier quoted context omitted.

Counting to 2^61 probably is. To actually find a collision in 128b cryptographic hash function it would take closer to 2^65 hashes. Back of the envelope calculations suggest that with Pollard's rho it would cost a few million dollars of CPU time at Hetzner's super-low prices. Not nearly mere mortals budget, but not that far off I guess.

A GUID is not a cryptographic hash function. In any case, in 2023 I back-of-the-envelope estimated that you could compute 2^64 SHA256 for ~$100K, using rented GPU capacity https://www.da.vidbuchanan.co.uk/blog/colliding-secure-hashe...

That's great analysis. As you call out in the post, the 2^64 value is used to attack SHA256-128 (SHA256 truncated to 128 bits). NIST recommends at least SHA-224, which makes sense given your conclusions.

Re: Guid Smash

#60

Post by senko »

charcircuit wrote: post #9
e1g wrote: post #8

Earlier quoted context omitted.

You need to be generating >100M of them within the same millisecond before even remembering that collisions can theoretically happen.

>You The entire universe. Else it's not universally unique.

Obviously, just the part within our light cone.
Post reply on HN