6 ms·

Probability of GUID collisions with different versions

93 points by yanowitz 11y ago

cek 11y ago
GUID == UUID. Annoys me to this day that MS uses the term GUID. Windows includes API functions using both names (e.g. CoCreateGuid and UuidCreate).
- Zikes 11y ago
  According to Wikipedia they're similar but distinct standards. https://en.wikipedia.org/wiki/Globally_unique_identifier#Binary_encoding https://en.wikipedia.org/wiki/Globally_unique_identifier#Bin...
- BuildTheRobots 11y ago
  A very brief google leads me to believing they're both 128bit numbers -could you please point me towards something that explains the differences? :)
  - cek 11y ago
    This S/O question does a fair job (see 3rd answer): http://stackoverflow.com/questions/246930/is-there-any-difference-between-a-guid-and-a-uuid http://stackoverflow.com/questions/246930/is-there-any-diffe...
    - BuildTheRobots 11y ago
      Better than fair job. Greatest of thanks :)
- TazeTSchnitzel 11y ago
  GUIDs are a variant of UUIDs, and not a Microsoft-exclusive thing.
  - cek 11y ago
    It's far more complicated (and simple) than that. This S/O question will help you understand. http://stackoverflow.com/questions/246930/is-there-any-difference-between-a-guid-and-a-uuid http://stackoverflow.com/questions/246930/is-there-any-diffe... A UUID generated or used by any of Microsoft's APIs or tools named with "Guid" are 100% standard UUIDs. It is not possible to create a a UUID with these APIs or tools that does not conform to the standard.
    - TazeTSchnitzel 11y ago
      GUIDs are a particular implementation of UUID, yes. The big difference is that GUID tends to be upper-case and little-endian (except for the big-endian bit), whereas UUIDs tend to be lower-case and big-endian.
deleted 11y ago
[deleted]
TazeTSchnitzel 11y ago
UUIDs and GUIDs are far too complicated, personally I don't like using them. There are multiple "versions" (really, generation algorithms) of UUID and GUID, each with their own problems: * Some types of UUID uniquely identify the machine they were generated on (one version contains the MAC address + current time, another contains the POSIX UID/GID + domain name) - this got Microsoft into hot water in the 1990s when Word added GUIDs to documents, which meant you could trace documents Stasi-style * Some types of UUID are based on insecure hashing algorithms (MD5 and SHA1) * Some types of UUID are namespaced, because everything needs namespaces, obviously * There's a specially reserved type for Microsoft to use for special COM objects There's only one mode you should actually use, which is the random bits. UUIDs and GUIDs also have a weird spacing of dashes. You'd expect three dashes, splitting it into a sequence of 4-byte chunks, but no: it's split into 4-2-2-2-6, for some reason. And which chunk it is matters, because different chunks have different endianness. Some of them are considered numbers, some of them bytes, even though they all look the same. Some of them have special significance (it contains two different version numbers!), with no especially obvious rhyme or reason to their placement. Oh, and the endianness is implementation-defined: GUIDs are partly "native" endian (usually little-endian, then), partly big-endian, whereas UUIDs are typically big-endian. How do you tell them apart? Well, GUIDs are usually written in capitals, and UUIDs are usually written in lowercase. I just use 16 random bytes encoded in hexadecimal, separated by three dashes at 4-byte increments. No hashing algorithms, versions, endianness issues, namespacing, severe privacy problems, just random bytes. It's not only simpler, it has more bits of entropy, and is easier to generate.
- JoeAltmaier 11y ago
  I also treat a UUID as a string of bytes. Go ahead and render it any way you like, but there are no endianness issues. The bytes are random and meaningless. Also be careful of what you think is 'random'. Calling the OS random-number-generator may not be random enough. I'd recommend in every case to use the system library to generate a UUID.
  - TazeTSchnitzel 11y ago
    > I also treat a UUID as a string of bytes. Why not avoid UUID altogether? It is an overly complicated format. It is simpler to just generate 16 random bytes and represent them as you wish. Beware that 16 random bytes, at least currently, is not a valid UUID. You have to include version and variant numbers. > Go ahead and render it any way you like, but there are no endianness issues. The bytes are random and meaningless. Endianness absolutely matters. If you don't encode it and decode it correctly from the binary formats, you will end up with a different identifier. > Also be careful of what you think is 'random'. Calling the OS random-number-generator may not be random enough. If it's just a regular PRNG, sure. What you want is a CSPRNG, like /dev/urandom.
bhouston 11y ago
I can deal with a machine crashing, I can not deal with an invalid database caused by GUIDs intersecting. Thus I actually want to avoid GUID intersections more than I care about a single machine's valid ram.
gus_massa 11y ago
> GUID generation algorithm 4 fills the GUID with 122 random bits. The odds of two GUIDs colliding are therefore one in 2^122, which is a phenomenally small number. Another thing to consider, is that due to the birthday paradox once you build 2.7 * 10^18 GUID, the probability that you have at lest a collision is bigger than 50%. And 2.7 * 10^18 is only 2^61.2.
- JoeAltmaier 11y ago
  only
- cmurphycode 11y ago
  Yeah, I really don't understand how they are ignoring this. It's actually very concerning to me that they don't understand this.
  - skrebbel 11y ago
    Are you sure they don't? Do you know how much 2^61 is?
    - cmurphycode 11y ago
      Well, if they did understand, they would say the chance is ~1 in 2^61, not 1 in 2^122, and they would've based the math comparison to RAM failure on 2^61, which changes the comparison entirely. In any case, I should have been more clear. I'm not necessarily worried about this case. But if you design systems and miss a factor of a square root, you tend to break things that we're all relying on to work.
    - sirsar 11y ago
      Far within the bounds of modern computing. The Bitcoin network cranks out 2^61 hashes every 2 or so seconds.
- chronial 11y ago
  If you generated 2.7 * 10^18 GUIDs (and obviously stored them all, otherwise the birthday paradox is not relevant), you also used up 43 exabytes (=1 million terrabytes) of storage. I wonder which problem you will encounter first...
dspillett 11y ago
> If you use the European scale. Be careful there. Parts of Europe including here (the UK) officially use short scale like the US. When looking at historical figures it is important to be extra careful as scale use has flipped back and forth over time in places. "Historical" doesn't go as far back as you think either: short scale becoming the standard number naming convention in the UK happened in 1974 so there are still people alive who use long scale and remember it being the most common form. To really confuse things some places use a half-way house of "short scale with milliard"... It is safer to stick with "scientific" prefixes (kilo, mega, giga, tera, ...) as they are consistently interpreted the same way except where someone is being deliberately difficult (for "deliberately difficult" read "just plain wrong"). It sometimes sounds odd referring to things like "giga pounds" instead of "billions of pounds" (or "thousand millions of pounds" or "milliards of pounds") but it reduces the risk of misinterpretation and anyone who doesn't understand probably wouldn't truly understand any of the above terms without explanation. For more see https://en.wikipedia.org/wiki/Long_and_short_scales https://en.wikipedia.org/wiki/Long_and_short_scales
dblohm7 11y ago
I'm amazed that in all of these discussions nobody ever references the RFC, so here you go: http://www.ietf.org/rfc/rfc4122.txt http://www.ietf.org/rfc/rfc4122.txt

93 points by yanowitz 11y ago

cek 11y ago

GUID == UUID. Annoys me to this day that MS uses the term GUID. Windows includes API functions using both names (e.g. CoCreateGuid and UuidCreate).

Zikes 11y ago
According to Wikipedia they're similar but distinct standards. https://en.wikipedia.org/wiki/Globally_unique_identifier#Binary_encoding https://en.wikipedia.org/wiki/Globally_unique_identifier#Bin...
BuildTheRobots 11y ago
A very brief google leads me to believing they're both 128bit numbers -could you please point me towards something that explains the differences? :)
- cek 11y ago
  This S/O question does a fair job (see 3rd answer): http://stackoverflow.com/questions/246930/is-there-any-difference-between-a-guid-and-a-uuid http://stackoverflow.com/questions/246930/is-there-any-diffe...
  - BuildTheRobots 11y ago
    Better than fair job. Greatest of thanks :)
TazeTSchnitzel 11y ago
GUIDs are a variant of UUIDs, and not a Microsoft-exclusive thing.
- cek 11y ago
  It's far more complicated (and simple) than that. This S/O question will help you understand. http://stackoverflow.com/questions/246930/is-there-any-difference-between-a-guid-and-a-uuid http://stackoverflow.com/questions/246930/is-there-any-diffe... A UUID generated or used by any of Microsoft's APIs or tools named with "Guid" are 100% standard UUIDs. It is not possible to create a a UUID with these APIs or tools that does not conform to the standard.
  - TazeTSchnitzel 11y ago
    GUIDs are a particular implementation of UUID, yes. The big difference is that GUID tends to be upper-case and little-endian (except for the big-endian bit), whereas UUIDs tend to be lower-case and big-endian.

deleted 11y ago

[deleted]

TazeTSchnitzel 11y ago

UUIDs and GUIDs are far too complicated, personally I don't like using them. There are multiple "versions" (really, generation algorithms) of UUID and GUID, each with their own problems: * Some types of UUID uniquely identify the machine they were generated on (one version contains the MAC address + current time, another contains the POSIX UID/GID + domain name) - this got Microsoft into hot water in the 1990s when Word added GUIDs to documents, which meant you could trace documents Stasi-style * Some types of UUID are based on insecure hashing algorithms (MD5 and SHA1) * Some types of UUID are namespaced, because everything needs namespaces, obviously * There's a specially reserved type for Microsoft to use for special COM objects There's only one mode you should actually use, which is the random bits. UUIDs and GUIDs also have a weird spacing of dashes. You'd expect three dashes, splitting it into a sequence of 4-byte chunks, but no: it's split into 4-2-2-2-6, for some reason. And which chunk it is matters, because different chunks have different endianness. Some of them are considered numbers, some of them bytes, even though they all look the same. Some of them have special significance (it contains two different version numbers!), with no especially obvious rhyme or reason to their placement. Oh, and the endianness is implementation-defined: GUIDs are partly "native" endian (usually little-endian, then), partly big-endian, whereas UUIDs are typically big-endian. How do you tell them apart? Well, GUIDs are usually written in capitals, and UUIDs are usually written in lowercase. I just use 16 random bytes encoded in hexadecimal, separated by three dashes at 4-byte increments. No hashing algorithms, versions, endianness issues, namespacing, severe privacy problems, just random bytes. It's not only simpler, it has more bits of entropy, and is easier to generate.

JoeAltmaier 11y ago
I also treat a UUID as a string of bytes. Go ahead and render it any way you like, but there are no endianness issues. The bytes are random and meaningless. Also be careful of what you think is 'random'. Calling the OS random-number-generator may not be random enough. I'd recommend in every case to use the system library to generate a UUID.
- TazeTSchnitzel 11y ago
  > I also treat a UUID as a string of bytes. Why not avoid UUID altogether? It is an overly complicated format. It is simpler to just generate 16 random bytes and represent them as you wish. Beware that 16 random bytes, at least currently, is not a valid UUID. You have to include version and variant numbers. > Go ahead and render it any way you like, but there are no endianness issues. The bytes are random and meaningless. Endianness absolutely matters. If you don't encode it and decode it correctly from the binary formats, you will end up with a different identifier. > Also be careful of what you think is 'random'. Calling the OS random-number-generator may not be random enough. If it's just a regular PRNG, sure. What you want is a CSPRNG, like /dev/urandom.

bhouston 11y ago

I can deal with a machine crashing, I can not deal with an invalid database caused by GUIDs intersecting. Thus I actually want to avoid GUID intersections more than I care about a single machine's valid ram.

gus_massa 11y ago

> GUID generation algorithm 4 fills the GUID with 122 random bits. The odds of two GUIDs colliding are therefore one in 2^122, which is a phenomenally small number. Another thing to consider, is that due to the birthday paradox once you build 2.7 * 10^18 GUID, the probability that you have at lest a collision is bigger than 50%. And 2.7 * 10^18 is only 2^61.2.

JoeAltmaier 11y ago
only
cmurphycode 11y ago
Yeah, I really don't understand how they are ignoring this. It's actually very concerning to me that they don't understand this.
- skrebbel 11y ago
  Are you sure they don't? Do you know how much 2^61 is?
  - cmurphycode 11y ago
    Well, if they did understand, they would say the chance is ~1 in 2^61, not 1 in 2^122, and they would've based the math comparison to RAM failure on 2^61, which changes the comparison entirely. In any case, I should have been more clear. I'm not necessarily worried about this case. But if you design systems and miss a factor of a square root, you tend to break things that we're all relying on to work.
  - sirsar 11y ago
    Far within the bounds of modern computing. The Bitcoin network cranks out 2^61 hashes every 2 or so seconds.
chronial 11y ago
If you generated 2.7 * 10^18 GUIDs (and obviously stored them all, otherwise the birthday paradox is not relevant), you also used up 43 exabytes (=1 million terrabytes) of storage. I wonder which problem you will encounter first...

dspillett 11y ago

> If you use the European scale. Be careful there. Parts of Europe including here (the UK) officially use short scale like the US. When looking at historical figures it is important to be extra careful as scale use has flipped back and forth over time in places. "Historical" doesn't go as far back as you think either: short scale becoming the standard number naming convention in the UK happened in 1974 so there are still people alive who use long scale and remember it being the most common form. To really confuse things some places use a half-way house of "short scale with milliard"... It is safer to stick with "scientific" prefixes (kilo, mega, giga, tera, ...) as they are consistently interpreted the same way except where someone is being deliberately difficult (for "deliberately difficult" read "just plain wrong"). It sometimes sounds odd referring to things like "giga pounds" instead of "billions of pounds" (or "thousand millions of pounds" or "milliards of pounds") but it reduces the risk of misinterpretation and anyone who doesn't understand probably wouldn't truly understand any of the above terms without explanation. For more see https://en.wikipedia.org/wiki/Long_and_short_scales https://en.wikipedia.org/wiki/Long_and_short_scales

dblohm7 11y ago

I'm amazed that in all of these discussions nobody ever references the RFC, so here you go: http://www.ietf.org/rfc/rfc4122.txt http://www.ietf.org/rfc/rfc4122.txt