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

21–30 of 72 posts

Re: Guid Smash

#21

Post by Zambyte »

kaoD wrote: post #19
w-ll wrote: post #14

Earlier quoted context omitted.

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

I think the current Microsoft GUID is just UUIDv7. https://learn.microsoft.com/en-us/dotnet/api/system.guid?vie... I don't think there's a "Microsoft standard" and they just use different versions of UUID in different products over time. No idea why they call it GUID instead of UUID though, but it's easier to speak out loud so I'm not against it. v7 has a timestamp indeed, but isn't the time making it more collision…

> isn't the time making it more collision resistant?

That seems to depend a whole lot on the pattern your application generates UUIDs in. If you're generating a consistent distribution over time, sure. If you generate a whole lot in bursts, collision seems to be way more likely.

Re: Guid Smash

#22

Post by kaoD »

Zambyte wrote: post #21
kaoD wrote: post #19

Earlier quoted context omitted.

I think the current Microsoft GUID is just UUIDv7. https://learn.microsoft.com/en-us/dotnet/api/system.guid?vie... I don't think there's a "Microsoft standard" and they just use different versions of UUID in different products over time. No idea why they call it GUID instead of UUID though, but it's easier to speak out loud so I'm not against it. v7 has a timestamp indeed, but isn't the time making it more collision…

> isn't the time making it more collision resistant? That seems to depend a whole lot on the pattern your application generates UUIDs in. If you're generating a consistent distribution over time, sure. If you generate a whole lot in bursts, collision seems to be way more likely.

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

Re: Guid Smash

#24

Post by thfuran »

8organicbits wrote: post #20
dgrin91 wrote: post #18

Earlier quoted context omitted.

Yeah, but a nation state server farm can probably cut that down to minutes because their budget can buy a lot of processors. You only need a few hundred to really shrink it down to manageable numbers. And it turns out that nation starts aren't the only ones that have this budget

What's the threat here? It's trivial to force a collision. Here's the same UUID twice: 6e197264-d14b-44df-af98-39aac5681791 6e197264-d14b-44df-af98-39aac5681791 Typically, you don't care about UUIDs that aren't in your system and you generate those yourself to avoid maliciously generated collisions. Your system can't handle 2^61 IDs. It doesn't have the processing power, storage, or bandwidth for that to happen. Not…

The last several comments were responding to

>2^61 is still a very large number of course, but much more feasible to reach than 2^122 when doing a collision attack. This is the reason that cryptographic hashes are typically 256 bits or more (to make the cost of collision attacks >= 2^128).

Re: Guid Smash

#25

Post by 8organicbits »

kaoD wrote: post #22
Zambyte wrote: post #21

Earlier quoted context omitted.

> isn't the time making it more collision resistant? That seems to depend a whole lot on the pattern your application generates UUIDs in. If you're generating a consistent distribution over time, sure. If you generate a whole lot in bursts, collision seems to be way more likely.

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)

Re: Guid Smash

#26

Post by tonyhart7 »

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.

Your app is must be popular to be having an entire universe "amount" of users lol

joke aside all of this is theorical, in practical application its literally impossible to hit it that it doesn't matters if its possible or not since you are not google scale anyway

Re: Guid Smash

#28

Post by 8organicbits »

thfuran wrote: post #24
8organicbits wrote: post #20

Earlier quoted context omitted.

What's the threat here? It's trivial to force a collision. Here's the same UUID twice: 6e197264-d14b-44df-af98-39aac5681791 6e197264-d14b-44df-af98-39aac5681791 Typically, you don't care about UUIDs that aren't in your system and you generate those yourself to avoid maliciously generated collisions. Your system can't handle 2^61 IDs. It doesn't have the processing power, storage, or bandwidth for that to happen. Not…

The last several comments were responding to >2^61 is still a very large number of course, but much more feasible to reach than 2^122 when doing a collision attack. This is the reason that cryptographic hashes are typically 256 bits or more (to make the cost of collision attacks >= 2^128).

I'm not sure. 6ghz is around 2^61 CPU cycles in 12 years. I.E. basic CPU instructions; counting, not computing a cryptographic hash. Otherwise, where is the cluster that's bruteforcing ~122 bit cryptographic hash collisions in minutes?

Re: Guid Smash

#29

Post by charcircuit »

tonyhart7 wrote: post #26
charcircuit wrote: post #9

Earlier quoted context omitted.

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

Your app is must be popular to be having an entire universe "amount" of users lol joke aside all of this is theorical, in practical application its literally impossible to hit it that it doesn't matters if its possible or not since you are not google scale anyway

It's not just your app. It's any other app or data provider that you may now or in the future interact with.

Re: Guid Smash

#30

Post by mmoskal »

Retr0id wrote: post #6
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 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.

Post reply on HN