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

41–50 of 72 posts

Re: Guid Smash

#41

Post by arcanemachiner »

habibur wrote: post #36
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…

The birthday paradox simplified : if you generate n bits of random data, you can at most generate n/2 bits of random numbers before clashes start to occur. That's square root of number's range. So if you need 1000 random numbers, generate from 1 to 1 million.

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?

Re: Guid Smash

#42

Post by Retr0id »

mmoskal wrote: post #30
Retr0id wrote: post #6

Earlier quoted context omitted.

2^61 isn't even that large, well within the compute budget of mere mortals.

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

Re: Guid Smash

#44

Post by Retr0id »

vlovich123 wrote: post #17
Retr0id wrote: post #6

Earlier quoted context omitted.

2^61 isn't even that large, well within the compute budget of mere mortals.

Depends on what “isn’t even that large means”. A modern 6ghz machine would probably need 12 years of 24/7 operation to count that high. To me that seems like a lot.

That's assuming 1 IPC, and no parallelism. A desktop-class zen5 CPU has 32 threads, with AVX512. Pipelining gets you up to 2048 bits of SIMD throughput per core per clock cycle: https://www.numberworld.org/blogs/2024_8_7_zen5_avx512_teard...

So assuming you use 64-bit counters, you can divide those 12 years by 1024 to get 4 days.

And that's not even considering what you could do on a GPU.

Edit: I might be off by a factor of 2, not sure if the SIMD throughput is per-core or per-thread. Also thermal throttling. Same ballpark though!

Re: Guid Smash

#45

Post by gammalost »

ahmedfromtunis wrote: post #39

The proximity measure seems to be flawed. If you want to see how close to a non-ordinal 123456 a random generator can get, you also need to look for stuff like 923456 or 123956, etc. Also, would 223456 be considered a closer match compared to 323456? (It shouldn't in my opinion because, again, these are non-ordinal strings).

If its a random ID then I'd argue that all of them are equally close to each other. With that said, I do not know how GUIDs are generated

Re: Guid Smash

#46

Post by avar »

sgentle wrote: post #37
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.

Apparently there's 500 hours of video uploaded to YouTube every minute (30 seconds every millisecond). Assuming 4K@60fps, that works out to 14,929,920,000 pixels per millisecond. If YouTube wanted to give every incoming pixel its own UUIDv7, they'd see a collision rate just under 0.6%.

    > Assuming 4K@60fps [...] they'd see a collision rate just under 0.6%
This doesn't detract from your point of collisions like that being viable at that scale, but assuming an average of 4K@60fps is assuming a lot. The average video upload there is probably south of 1080p@30fps.

Re: Guid Smash

#47

Post by twiss »

8organicbits wrote: post #33
vlovich123 wrote: post #31

Earlier quoted context omitted.

For what it’s worth generating a random UUID for the purposes of collision isn’t generally much more complicated than a few arithmetic instructions which is why I used counting as an example. And as the other poster mentioned generating a UUID collision isn’t a security problem since the UUID tends to be generated within your infrastructure where you can’t really go full blast at generating UUIDs for all sorts of rea…

I don't think that's quite right. A 128-bit UUIDv4 having a 50% chance of having any collision after 2^61 generations is very different from finding a specific 128-bit symmetric key. The best cryptanalysis of AES-128 is 2^126; nowhere near 2^64. Which is why standards bodies like NIST still recommend AES-128 as a baseline.

You're right that AES-128 is fine. Normally the birthday paradox only applies to cryptographic hashes.

The only way it would apply to symmetric keys is if you have a server that stores 2^64 encrypted messages, and can somehow find out which messages used the same symmetric key (normally not possible unless they also have the same IV and plaintext), and can somehow coerce the user who uploaded message #1 to decrypt message #2 for you (or vice versa). Obviously that isn't realistic.

Re: Guid Smash

#48

Post by twiss »

arcanemachiner wrote: post #41
habibur wrote: post #36

Earlier quoted context omitted.

The birthday paradox simplified : if you generate n bits of random data, you can at most generate n/2 bits of random numbers before clashes start to occur. That's square root of number's range. So if you need 1000 random numbers, generate from 1 to 1 million.

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?

The actual number is 23: https://en.wikipedia.org/wiki/Birthday_problem

The square root approximation works well for large numbers, but leaves out some factors that are relevant for small numbers.

Re: Guid Smash

#49

Post by Spooky23 »

arcanemachiner wrote: post #41
habibur wrote: post #36

Earlier quoted context omitted.

The birthday paradox simplified : if you generate n bits of random data, you can at most generate n/2 bits of random numbers before clashes start to occur. That's square root of number's range. So if you need 1000 random numbers, generate from 1 to 1 million.

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.

Re: Guid Smash

#50

Post by lyu07282 »

w-ll wrote: post #14
lionkor wrote: post #13

Earlier quoted context omitted.

Oh, why?

not OP but i already have fields for time ts and what model it is. i want my uuids random.

> i want my uuids random

You probably actually want at least a few prefixed bytes be a timestamp (uuidv7) for b-tree efficiency but ymmv

Post reply on HN