How unique is UUID?

Question

How safe is it to use UUID to uniquely identify something (I'm using it for files uploaded to the server)? As I understand it, it is based off random numbers. However, it seems to me that given enough time, it would eventually repeat it self, just by pure chance. Is there a better system or a pattern of some type to alleviate this issue?

Jobbery

"unique" means never collide. If it has any potential to collide, it's not unique. Therefore by definition, UUID is not unique, and safe only if you're prepared for potential collisions regardless of chance of collisions. Otherwise, your program is simply incorrect. You can say UUID as "almost unique" but it doesn't mean it's "unique". – Televise

UUIDs are unique "for practical purposes" - the fact that there is a infinitesimally small chance of a duplicate value being generated doesn't make programs relying on this incorrect except in the very rare situation where the volume of IDs being generated starts to make that possibility statistically significant. – Crocodilian

Table with more numbers can be found on the Birthday attack wikipedia page. en.wikipedia.org/wiki/Birthday_attack#Mathematics (UUIDs are 128 bits). If 128 bits still isn't good enough you can always just generate more and join them together; completely pointless, but you can. – Penury

@Televise UUID (version 1) can't collide provided you create them correctly. They have some bytes used to uniquely identify your computer - 48 bits to be exact. These bytes are manually configured, or created from the MAC address. On top of that, they have a timer with a 0.0001 second increment. If you plan to create more than 10000000 UUIDs per second, there is 13 bits extra available for a serial number. Of course, in many cases the 61 bits (48+13) reserved for node ID and serial number can collide if you use random numbers instead of taking care. – Mycenaean

linked: #40271 – Mchail

Answer 1

Very safe:

the annual risk of a given person being hit by a meteorite is estimated to be one chance in 17 billion, which means the probability is about 0.00000000006 (6 × 10⁻¹¹), equivalent to the odds of creating a few tens of trillions of UUIDs in a year and having one duplicate. In other words, only after generating 1 billion UUIDs every second for the next 100 years, the probability of creating just one duplicate would be about 50%.

Caveat:

However, these probabilities only hold when the UUIDs are generated using sufficient entropy. Otherwise, the probability of duplicates could be significantly higher, since the statistical dispersion might be lower. Where unique identifiers are required for distributed applications, so that UUIDs do not clash even when data from many devices is merged, the randomness of the seeds and generators used on every device must be reliable for the life of the application. Where this is not feasible, RFC4122 recommends using a namespace variant instead.

Source: The Random UUID probability of duplicates section of the Wikipedia article on Universally unique identifiers (link leads to a revision from December 2016 before editing reworked the section).

Also see the current section on the same subject on the same Universally unique identifier article, Collisions.

Tanaka

I like this part from Wikipedia: However, these probabilities only hold when the UUIDs are generated using sufficient entropy. Otherwise, the probability of duplicates could be significantly higher, since the statistical dispersion might be lower. So what is the real chance of duplicate noting this sentence. We can not create real random numbers on computer, can we? – Bingle

Actually, a lot of work has gone into finding ways to introduce as much entropy ("real randomness", I guess you'd call it) as possible into random number APIs. See en.wikipedia.org/wiki/Entropy_%28computing%29 – Ibby

That's actually a higher probability of collision than I'd imagined. Birthday paradox at, I guess. – Trichiasis

@linus_hologram - It's not really a JS problem. The source of entropy is typically configured at the operating system level. – Upheave

You can reduce the chance of having any collisions by starting with a very random UUID, and then using consecutive UUIDs (and if others use the same strategy). Birthday paradox works less against you. However the expected number of collissions is unchanged. And if you one collision, you have many. – Axle

@MartijnPieters, could someone edit to add this useful information: are we speaking about 128-bit or 256-bit UUID? It changes everything in the maths here. – Lindblad

@Basj: Read the linked article: Out of a total of 128 bits, Version 4 UUIDs have 6 reserved bits (4 for the version and 2 other reserved bits), so randomly generated UUIDs have 122 random bits. – Reinaldo

I have worked on this it generate duplicate, i m not it's have chance duplicate by keychain shared value, or reason because of uuid generate duplicate [UICKeyChainStore setString:uuidString forKey:@"uuid"]; [defaults setObject:uuidString forKey:@"uuid"]; [defaults synchronize]; – Rainy

Answer 2

If by "given enough time" you mean 100 years and you're creating them at a rate of a billion a second, then yes, you have a 50% chance of having a collision after 100 years.

Broderic

But only after using up 256 exabytes of storage for those IDs. – Intradermal

Is the uniqueness purely because of randomness? Or there are other factors? (e.g. time stamp, ip, etc) – Choreograph

If something depends on random numbers not being the same, then those random numbers aren't random. If they are truly random then there is no way of knowing what the chance is of getting a duplicate. – Oracle

@TheTahaan That's not what random means. It doesn't mean "totally unpredictable" -- usually they follow some kind of distribution. If you flip 10 coins, the chance of getting 2 heads, followed by 3 tails, followed by 5 heads, is pretty low (2^-10, about 0.001). It's truly random, but we absolutely can know the chance of getting a particular outcome. We just can't say in advance whether it will happen. – Motorcar

You're using a lousy implementation. No guarantees exist for bad implementations. :-P – Intradermal

Just to explain what this implementation did wrong, they're using a version 1 UUID, which relies on a combination of timestamp and mac address for its uniqueness. However if you generate UUIDs fast enough, the timestamp won't have incremented yet. In this scenario, your UUID generation algorithm is supposed to track the last timestamp used and increment it by 1. They clearly failed to take that step. However all version 1 UUIDs correctly generated by the same machine in a short period will exhibit obvious similarities, but ought to still be unique. – Intradermal

@BobAman I know it's almost 10 years ago but shouldn't that be 500+ exabytes? given that a UUID = 16 bytes – Alexipharmic

@MemetOlsen Haven't rechecked my numbers, but people often overestimate. I believe I did use birthday paradox formula to come up w/ that number. – Intradermal

@scalabl3 Mathematically, the chance of generating 2 in a row is no different than the chance of them being spaced by a trillion. The probability of collision is not affected by the sequence in which the UUIDs are crated but their contents. You can hit 2 in a row and then not have another collision for the next trillion, or you can get collision only after the first trillion - the probability is still the same. Ergo, the probability of a clash in the first 2 attempts is exactly the same as the probability of a clash between any 2 fixed attempts, e.g. 1st and 100th, 10th and 689th, ... – Misapprehend

Answer 3

There is more than one type of UUID, so "how safe" depends on which type (which the UUID specifications call "version") you are using.

• Version 1 is the time based plus MAC address UUID. The 128-bits contains 48-bits for the network card's MAC address (which is uniquely assigned by the manufacturer) and a 60-bit clock with a resolution of 100 nanoseconds. That clock wraps in 3603 A.D. so these UUIDs are safe at least until then (unless you need more than 10 million new UUIDs per second or someone clones your network card). I say "at least" because the clock starts at 15 October 1582, so you have about 400 years after the clock wraps before there is even a small possibility of duplications.

• Version 4 is the random number UUID. There's six fixed bits and the rest of the UUID is 122-bits of randomness. See Wikipedia or other analysis that describe how very unlikely a duplicate is.

• Version 3 is uses MD5 and Version 5 uses SHA-1 to create those 122-bits, instead of a random or pseudo-random number generator. So in terms of safety it is like Version 4 being a statistical issue (as long as you make sure what the digest algorithm is processing is always unique).

• Version 2 is similar to Version 1, but with a smaller clock so it is going to wrap around much sooner. But since Version 2 UUIDs are for DCE, you shouldn't be using these.

So for all practical problems they are safe. If you are uncomfortable with leaving it up to probabilities (e.g. your are the type of person worried about the earth getting destroyed by a large asteroid in your lifetime), just make sure you use a Version 1 UUID and it is guaranteed to be unique (in your lifetime, unless you plan to live past 3603 A.D.).

So why doesn't everyone simply use Version 1 UUIDs? That is because Version 1 UUIDs reveal the MAC address of the machine it was generated on and they can be predictable -- two things which might have security implications for the application using those UUIDs.

Microphysics

Defaulting to a version 1 UUID has serious issues when they're generated by the same server for many people. The version 4 UUID is my default since you can quickly write something to generate one in any language or platform (including javascript). – Briarroot

One need not generate 10 million version 1 UUIDs in a second to encounter a duplicate; one must merely generate a batch of 16,384 UUIDs within the span of a single "tick" in order to overflow the sequence number. I have seen this happen with an implementation that relied, naively, on a clock source that (1) had μs-level granularity, and (2) was not guaranteed to be monotonic (system clocks are not). Be careful whose UUID generation code you use, and be especially wary with time-based UUID generators. They are difficult to get right, so subject them to load tests before using them. – Neruda

Answer 4

The answer to this may depend largely on the UUID version.

Many UUID generators use a version 4 random number. However, many of these use a Pseudo Random Number Generator (PRNG) to generate them.

If a poorly seeded PRNG with a small period is used to generate the UUID I would say it's not very safe at all. Some random number generators also have poor variance. i.e. favoring certain numbers more often than others. This isn't going to work well.

Therefore, it's only as safe as the algorithms used to generate it.

On the flip side, if you know the answer to these questions then I think a version 4 UUID should be very safe to use. In fact I'm using it to identify blocks on a network block file system and so far have not had a clash.

In my case, the PRNG I'm using is a Mersenne Twister and I'm being careful with the way it's seeded which is from multiple sources including /dev/urandom. Mersenne twister has a period of 2^19937 − 1. It's going to be a very very long time before I see a repeat UUID.

So pick a good library or generate it yourself and make sure you use a decent PRNG algorithm.

Cypsela

Answer 5

For UUID4 I make it that there are approximately as many IDs as there are grains of sand in a cube-shaped box with sides 360,000km long. That's a box with sides ~2 1/2 times longer than Jupiter's diameter.

Working so someone can tell me if I've messed up units:

• volume of grain of sand 0.00947mm^3 (Guardian)
• UUID4 has 122 random bits -> 5.3e36 possible values (wikipedia)
• volume of that many grains of sand = 5.0191e34 mm^3 or 5.0191e+25m^3
• side length of cubic box with that volume = 3.69E8m or 369,000km
• diameter of Jupiter: 139,820km (google)

Belk

Actually I guess this assumes 100% packing so maybe I should add a factor for that! – Belk

This is actually very helpful and has made me realize it's probably okay and there are other things to worry about. lmao – Reliable

that assumes the box is full of sand. you need to specify all your assumptions – Presser

Obviously its a full box, otherwise I could have said "a box the size of the known universe which is 0.0000000002% full" (for example, not calculated!) which is less descriptive. I think the packing factor is a much bigger issue with the above calc but at least it's conservative (i.e. a more realistic value than 100% will make the box bigger). – Belk

Answer 6

I concur with the other answers. UUIDs are safe enough for nearly all practical purposes¹, and certainly for yours.

But suppose (hypothetically) that they aren't.

Is there a better system or a pattern of some type to alleviate this issue?

Here are a couple of approaches:

1. Use a bigger UUID. For instance, instead of a 128 random bits, use 256 or 512 or ... Each bit you add to a type-4 style UUID will reduce the probability of a collision by a half, assuming that you have a reliable source of entropy².

2. Build a centralized or distributed service that generates UUIDs and records each and every one it has ever issued. Each time it generates a new one, it checks that the UUID has never been issued before. Such a service would be technically straight-forward to implement (I think) if we assumed that the people running the service were absolutely trustworthy, incorruptible, etcetera. Unfortunately, they aren't ... especially when there is the possibility of governments' security organizations interfering. So, this approach is probably impractical, and may be³ impossible in the real world.

---

^{1 - If uniqueness of UUIDs determined whether nuclear missiles got launched at your country's capital city, a lot of your fellow citizens would not be convinced by "the probability is extremely low". Hence my "nearly all" qualification.
2 - And here's a philosophical question for you. Is anything ever truly random? How would we know if it wasn't? Is the universe as we know it a simulation? Is there a God who might conceivably "tweak" the laws of physics to alter an outcome?
3 - If anyone knows of any research papers on this problem, please comment.}

Upheave

I just want to point out that the method number 2 basically defeats the main purpose of using UUID and you might as well just use a classic numbered ID at that point. – Sauncho

I disagree. The flaw in sequential numbered IDs is that they are too easy to guess. You should be able to implement method 2 in a way that makes the UUIDs difficult to guess. – Upheave

But even for what you're saying you can basically use any other random string/number and just check for duplicates, you don't have any reason to use UUID instead of say 6-characters long random string. – Sauncho

Well, yes and no. It depends on the context in which the ids are required to be unique. If they are only required to be unique in a closed system, then it is feasible to use short random strings and store them all in a database (or something) to check for duplicates. But that doesn't give you guaranteed universal uniqueness. And if the number of unique ids generated over the lifetime of the system is large enough you will run into scaling problems, assuming that the unique ids are required to be unique over time ... not just at a point in time. – Upheave

Why doesn't using a centralized database guarantee universal uniqueness? That doesn't make any sense to me. – Coolish

What if some of the actors are not using the centralized database? What if the database gets reset in (say) 20 years time? What if you run out of ids? My point is that a guarantee of "universally uniqueness" is next to impossible to achieve unless you place significant caveats on what "universal" means. Note that is all in the context of a question that asks "how unique is a UUID?". – Upheave

Answer 7

Quoting from Wikipedia:

Thus, anyone can create a UUID and use it to identify something with reasonable confidence that the identifier will never be unintentionally used by anyone for anything else

It goes on to explain in pretty good detail on how safe it actually is. So to answer your question: Yes, it's safe enough.

Isosceles

Answer 8

UUID schemes generally use not only a pseudo-random element, but also the current system time, and some sort of often-unique hardware ID if available, such as a network MAC address.

The whole point of using UUID is that you trust it to do a better job of providing a unique ID than you yourself would be able to do. This is the same rationale behind using a 3rd party cryptography library rather than rolling your own. Doing it yourself may be more fun, but it's typically less responsible to do so.

Wittenburg

So why use a UUID when logins are right there? – Anastos

Answer 9

Been doing it for years. Never run into a problem.

I usually set up my DB's to have one table that contains all the keys and the modified dates and such. Haven't run into a problem of duplicate keys ever.

The only drawback that it has is when you are writing some queries to find some information quickly you are doing a lot of copying and pasting of the keys. You don't have the short easy to remember ids anymore.

Electioneer

Answer 10

Here's a testing snippet for you to test it's uniquenes. inspired by @scalabl3's comment

Funny thing is, you could generate 2 in a row that were identical, of course at mind-boggling levels of coincidence, luck and divine intervention, yet despite the unfathomable odds, it's still possible! :D Yes, it won't happen. just saying for the amusement of thinking about that moment when you created a duplicate! Screenshot video! – scalabl3 Oct 20 '15 at 19:11

If you feel lucky, check the checkbox, it only checks the currently generated id's. If you wish a history check, leave it unchecked. Please note, you might run out of ram at some point if you leave it unchecked. I tried to make it cpu friendly so you can abort quickly when needed, just hit the run snippet button again or leave the page.

Math.log2 = Math.log2 || function(n){ return Math.log(n) / Math.log(2); }
  Math.trueRandom = (function() {
  var crypt = window.crypto || window.msCrypto;

  if (crypt && crypt.getRandomValues) {
      // if we have a crypto library, use it
      var random = function(min, max) {
          var rval = 0;
          var range = max - min;
          if (range < 2) {
              return min;
          }

          var bits_needed = Math.ceil(Math.log2(range));
          if (bits_needed > 53) {
            throw new Exception("We cannot generate numbers larger than 53 bits.");
          }
          var bytes_needed = Math.ceil(bits_needed / 8);
          var mask = Math.pow(2, bits_needed) - 1;
          // 7776 -> (2^13 = 8192) -1 == 8191 or 0x00001111 11111111

          // Create byte array and fill with N random numbers
          var byteArray = new Uint8Array(bytes_needed);
          crypt.getRandomValues(byteArray);

          var p = (bytes_needed - 1) * 8;
          for(var i = 0; i < bytes_needed; i++ ) {
              rval += byteArray[i] * Math.pow(2, p);
              p -= 8;
          }

          // Use & to apply the mask and reduce the number of recursive lookups
          rval = rval & mask;

          if (rval >= range) {
              // Integer out of acceptable range
              return random(min, max);
          }
          // Return an integer that falls within the range
          return min + rval;
      }
      return function() {
          var r = random(0, 1000000000) / 1000000000;
          return r;
      };
  } else {
      // From http://baagoe.com/en/RandomMusings/javascript/
      // Johannes Baagøe <[email protected]>, 2010
      function Mash() {
          var n = 0xefc8249d;

          var mash = function(data) {
              data = data.toString();
              for (var i = 0; i < data.length; i++) {
                  n += data.charCodeAt(i);
                  var h = 0.02519603282416938 * n;
                  n = h >>> 0;
                  h -= n;
                  h *= n;
                  n = h >>> 0;
                  h -= n;
                  n += h * 0x100000000; // 2^32
              }
              return (n >>> 0) * 2.3283064365386963e-10; // 2^-32
          };

          mash.version = 'Mash 0.9';
          return mash;
      }

      // From http://baagoe.com/en/RandomMusings/javascript/
      function Alea() {
          return (function(args) {
              // Johannes Baagøe <[email protected]>, 2010
              var s0 = 0;
              var s1 = 0;
              var s2 = 0;
              var c = 1;

              if (args.length == 0) {
                  args = [+new Date()];
              }
              var mash = Mash();
              s0 = mash(' ');
              s1 = mash(' ');
              s2 = mash(' ');

              for (var i = 0; i < args.length; i++) {
                  s0 -= mash(args[i]);
                  if (s0 < 0) {
                      s0 += 1;
                  }
                  s1 -= mash(args[i]);
                  if (s1 < 0) {
                      s1 += 1;
                  }
                  s2 -= mash(args[i]);
                  if (s2 < 0) {
                      s2 += 1;
                  }
              }
              mash = null;

              var random = function() {
                  var t = 2091639 * s0 + c * 2.3283064365386963e-10; // 2^-32
                  s0 = s1;
                  s1 = s2;
                  return s2 = t - (c = t | 0);
              };
              random.uint32 = function() {
                  return random() * 0x100000000; // 2^32
              };
              random.fract53 = function() {
                  return random() +
                      (random() * 0x200000 | 0) * 1.1102230246251565e-16; // 2^-53
              };
              random.version = 'Alea 0.9';
              random.args = args;
              return random;

          }(Array.prototype.slice.call(arguments)));
      };
      return Alea();
  }
}());

Math.guid = function() {
    return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c)    {
      var r = Math.trueRandom() * 16 | 0,
          v = c == 'x' ? r : (r & 0x3 | 0x8);
      return v.toString(16);
  });
};
function logit(item1, item2) {
    console.log("Do "+item1+" and "+item2+" equal? "+(item1 == item2 ? "OMG! take a screenshot and you'll be epic on the world of cryptography, buy a lottery ticket now!":"No they do not. shame. no fame")+ ", runs: "+window.numberofRuns);
}
numberofRuns = 0;
function test() {
   window.numberofRuns++;
   var x = Math.guid();
   var y = Math.guid();
   var test = x == y || historyTest(x,y);

   logit(x,y);
   return test;

}
historyArr = [];
historyCount = 0;
function historyTest(item1, item2) {
    if(window.luckyDog) {
       return false;
    }
    for(var i = historyCount; i > -1; i--) {
        logit(item1,window.historyArr[i]);
        if(item1 == history[i]) {
            
            return true;
        }
        logit(item2,window.historyArr[i]);
        if(item2 == history[i]) {
            
            return true;
        }

    }
    window.historyArr.push(item1);
    window.historyArr.push(item2);
    window.historyCount+=2;
    return false;
}
luckyDog = false;
document.body.onload = function() {
document.getElementById('runit').onclick  = function() {
window.luckyDog = document.getElementById('lucky').checked;
var val = document.getElementById('input').value
if(val.trim() == '0') {
    var intervaltimer = window.setInterval(function() {
         var test = window.test();
         if(test) {
            window.clearInterval(intervaltimer);
         }
    },0);
}
else {
   var num = parseInt(val);
   if(num > 0) {
        var intervaltimer = window.setInterval(function() {
         var test = window.test();
         num--;
         if(num < 0 || test) {
    
         window.clearInterval(intervaltimer);
         }
    },0);
   }
}
};
};

Please input how often the calulation should run. set to 0 for forever. Check the checkbox if you feel lucky.<BR/>
<input type="text" value="0" id="input"><input type="checkbox" id="lucky"><button id="runit">Run</button><BR/>

Abelmosk

Try with a RFC 4122 Version 1 (date-time and MAC address) UUID. – Annular

Answer 11

I don't know if this matters to you, but keep in mind that GUIDs are globally unique, but substrings of GUIDs aren't.

Selfexecuting

Keep in mind that the reference linked here talks about Version 1 UUIDs (which take information about the generating computer etc. into the id). Most other Answers talk about Version 4 (which are totally random). The above linked Wikipedia article en.wikipedia.org/wiki/Universally_unique_identifier explains the different kinds of UUIDs. – Introvert

Answer 12

I should mention I bought two external Seagate drives on Amazon, and they had the same device UUID, but differing PARTUUID. Presumably the cloning software they used to format the drives just copied the UUID as well.

Obviously UUID collisions are much more likely to happen due to a flawed cloning or copying process than from random coincidence. Bear that in mind when calculating UUID risks.

Zirconium