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

31–40 of 72 posts

Re: Guid Smash

#31

Post by vlovich123 »

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

Earlier quoted context omitted.

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?

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

For cryptographic applications it is really small because the previous poster is correct that 2^64 is very small for that purpose - a small supercomputing cluster or two could decrypt such a cipher in a reasonable amount of time, which is why symmetric keys are all 256 bits and up to guarantee there’s no way to attack them.

Re: Guid Smash

#32

Post by kr2 »

nopassrecover wrote: post #27

Reminds me of a problem I ran into once where someone had wanted unique but short codes as identifiers for relatively small counts, and picked a substring of a UUID: http://mattmitchell.com.au/birthday-problems-friendly-identi...

> However, the overall takeaway was: Don’t use the MongoDB Increment value as a Unique Identifier.

However, the overall takeaway should be, as always: don't use MongoDB. Period. Every time I learn something new about it I'm baffled about why people continue to use it.

Re: Guid Smash

#33

Post by 8organicbits »

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

Earlier quoted context omitted.

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?

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.

Re: Guid Smash

#34

Post by JdeBP »

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…

Years ago, Microsoft took the same algorithm that was being used to generate these things for Remote Procedure Calls in the Open Software Foundation's Distributed Computing Environment and used that algorithm to generate IDs for its Component Object Model. This was all happening in the late 1980s, and at a point where none of it was hard and fast.

If you were doing RPC in OSF DCE your IDs were UUIDs, and if you were doing COM in Wintel your IDs were GUIDs; and that was basically the difference, a different name for the same thing when used in a different domain.

Plus the difference in endianism because one was a network-byte-order network thing and the other was an Intel Architecture byte order thing, and only some parts of these IDs were technically multiple-byte integers with byte orders to have.

But by the late 1990s this had already become lost to history, with a sea of people who had made all sorts of inferences and promoted them as gospel truth, from the fact that Microsoft had two programs named GUIDGEN.EXE and UUIDGEN.EXE, from the fact that many generators sprang up and the whole idea spread to Java and databases and this new-fangled WorldWeb thing and all sorts of stuff, from the fact that there sprang up multiple different versions of these IDs and what version an ID was depended from tooling and libraries, and from the fact that at the time Microsoft was less likely to go through formal standards processes and more likely to just write and ship things and sponsor a book and a CD-ROM of doco so if your world was RFCs and the IETF you had one worldview and if your world was Microsoft Press and the MSDN you had another worldview.

Re: Guid Smash

#35

Post by tgv »

charcircuit wrote: post #29
tonyhart7 wrote: post #26

Earlier quoted context omitted.

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.

Only if the other side uses your key as theirs, and uses it to store data from many sources. I, personally, don't feel it's hardly worth considering. A primary key under your own control doesn't cost much, and is a better choice.

Re: Guid Smash

#36

Post by habibur »

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.

Re: Guid Smash

#37

Post by sgentle »

e1g wrote: post #8
8organicbits wrote: post #3

Note that this only considers UUIDv4, the random UUID. Other forms can generate UUIDs that are much closer together. For UUIDv7, UUIDs generated within the same millisecond will have identical 48 bit prefixes (or up to 60 when the monotonic counter from section 6.2 is used). https://www.rfc-editor.org/rfc/rfc9562.html#monotonicity_cou...

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

Re: Guid Smash

#38

Post by Joel_Mckay »

Most just pack down:

epoch time + MAC Address + transaction counter (catch NTP skew) + Thread PID + new Pointer address = GUID

Then increment global transaction counter, complete some ops, and check to ensure current epoch time is in the future before the transaction frees the memory locations.

This is often robust in highly concurrent distributed systems even under network degradation, or corrupted sync states. Has other interesting use-cases too. =3

Re: Guid Smash

#39

Post by ahmedfromtunis »

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

Post reply on HN