5 ms·

This is how my intuition went: it's probably less than 128 bits because UUIDs are 128 bits, and they're universally unique. But what's in a name? There's

This is how my intuition went: it's probably less than 128 bits because UUIDs are 128 bits, and they're universally unique. But what's in a name? There's no natural law constraining the UUID standard, such that they must be actually universally unique. And 128 bits isn't such an incredible bit space. MD5 hashes are 128 bits, and prone to manipulating in favor of collisions. Don't get me wrong, 3.402823669209385*10^38 is a huge number, and we haven't used enough passwords to occupy every value in that key space, but I still don't imagine 128 bits provides truly universally unique coverage, but really just pretty okay uniqueness coverage.

readams 9y ago
Md5 collisions are not the result of 2^128 being too small. 2^128 is hilariously big.
X-Istence 9y ago
I think you should take a gander at this: http://nowiknow.com/shuffled/ http://nowiknow.com/shuffled/
- sjcsjc 9y ago
  Or maybe this https://czep.net/weblog/52cards.html https://czep.net/weblog/52cards.html
- dfox 9y ago
  One thing that this shows is that many accepted cryptographicaly secure RNGs are in fact insufficient for shuffling decks of cards. I'm not sure how one would go about exploiting the resulting bias, but it is probably somehow exploitable.
psyc 9y ago
At one time, UUIDs were made by combining a fine timestamp with MAC-style hardware ids, giving a value that was conceptually unique in time and space. IIRC, it was eventually realized that choosing a value at random (e.g. using true RNG) was just as good. 2^128 is about 300 undecillion. Roughly 800 billion values per nanosecond for the age of the universe.
- pacaro 9y ago
  Version 4 UUIDs are preferred not because random is as good, indeed for some usecases it is worse, but typically because leaking information about time of creation and MAC address of the creator is undesirable
  - dannyw 9y ago
    Why not just hash it then?
    - dfox 9y ago
      Because the probability of random collision for hash function is same as probability of generating two colliding random bit strings of same length as the hash.
FRex 9y ago
MD5 is prone to manipulation due to its logic, not the size of the output. It also has many very efficient collision attacks but no feasible preimage attack (AFAIK) and they shave just few bits off 2^128 (which is still a lot): https://crypto.stackexchange.com/a/41865 https://crypto.stackexchange.com/a/41865

readams 9y ago

Md5 collisions are not the result of 2^128 being too small. 2^128 is hilariously big.

X-Istence 9y ago

I think you should take a gander at this: http://nowiknow.com/shuffled/ http://nowiknow.com/shuffled/

sjcsjc 9y ago
Or maybe this https://czep.net/weblog/52cards.html https://czep.net/weblog/52cards.html
dfox 9y ago
One thing that this shows is that many accepted cryptographicaly secure RNGs are in fact insufficient for shuffling decks of cards. I'm not sure how one would go about exploiting the resulting bias, but it is probably somehow exploitable.

psyc 9y ago

At one time, UUIDs were made by combining a fine timestamp with MAC-style hardware ids, giving a value that was conceptually unique in time and space. IIRC, it was eventually realized that choosing a value at random (e.g. using true RNG) was just as good. 2^128 is about 300 undecillion. Roughly 800 billion values per nanosecond for the age of the universe.

pacaro 9y ago
Version 4 UUIDs are preferred not because random is as good, indeed for some usecases it is worse, but typically because leaking information about time of creation and MAC address of the creator is undesirable
- dannyw 9y ago
  Why not just hash it then?
  - dfox 9y ago
    Because the probability of random collision for hash function is same as probability of generating two colliding random bit strings of same length as the hash.

FRex 9y ago

MD5 is prone to manipulation due to its logic, not the size of the output. It also has many very efficient collision attacks but no feasible preimage attack (AFAIK) and they shave just few bits off 2^128 (which is still a lot): https://crypto.stackexchange.com/a/41865 https://crypto.stackexchange.com/a/41865