<p>I guess the main source of confusion is that there are many versions (and many implementations) of UUIDs.</p>

<p><strong>Random but not unique:</strong> As you can see from the Wikipedia article, version 4 UUIDs are just 122-bit random numbers. Nothing else. They are exactly as good for cryptographic purposes as the random number generator that you used to implement it. And they are not "unique" in any other sense except that it's highly unlikely to get collisions (at least if you use a good random-number generator).</p>

<p><strong>Unique but not random:</strong> In the other extreme we have version 1 UUIDs, which concatenate MAC addresses with timestamps. Assuming that the MAC addresses are globally unique (as they are supposed to be, as there is a central authority that allocates them), and assuming that you don't generate UUIDs too rapidly, then the end result is something that is guaranteed to be globally unique. However, it is not "random" in any sense; if you know who generated the UUID and when, you can predict the value of the UUID fairly accurately. Obviously, it is an extremely bad idea to use such UUIDs as a replacement of random numbers in any cryptographic application.</p>

CC BY-SA 2.5
2010-11-19T14:10:45.737Z
2010-11-19T14:10:45.737Z
Jukka Suomela
<p>An object is <em>mathematically</em> unique, if there does not exist <strong>another</strong> object which satisfies the properties of the first object. For instance, the solution of $7x+2=5$ is unique (over reals), while the solution of $x^2=4$ is not unique (over reals).</p>

<p>An object is <em>practically</em> unique, if there is not an <strong>efficient</strong> procedure which finds another object that satisfies the properties of the first object. For instance, let $H(\cdot)$ be a <a href="http://en.wikipedia.org/wiki/Cryptographic_hash_function" rel="nofollow">cryptographically secure hash function</a>. By definition, the solution to $y=H(x)$ is (practically) unique; That is, while there are mathematically infinitely many $x$'s which satisfy $y=H(x)$, there is no efficient procedure which, given $y$ and $x$, can find $x&#39; \ne x$ such that $y=H(x&#39;)$.</p>

<p>This is the case with UUID's. Given a (random) seed, the UUID generator produces a (practically) unique UUID; That is, it is practically infeasible to find two seeds $s \ne s&#39;$ such that $UUID(s) = UUID(s&#39;)$, while <em>mathematically</em> such seeds exist.</p>

<p>When I teach this concept in the class, I usually provide an example: Assume that, to find such a <em>collision</em>, one must try $2^{128}$ seeds. This number is so high that it is beyond the (estimated) amount of particles in the known universe!</p>

CC BY-SA 2.5
2010-11-19T13:34:59.827Z
Does this imply that UUIDs can be used as cryptographic keys?
sharptooth
CC BY-SA 2.5
2010-11-19T14:29:38.657Z
@sharptooth: Strictly speaking, collision-freeness does not imply randomness. In addition, the seed to the UUID generator might not be a random string. (It might be a URL, an FQDN, an object identifier, a distinguished name, etc.) Please seek the Wikipedia entry you cited in the question for more info.
Sadeq Dousti
CC BY-SA 2.5
2010-11-19T16:31:35.240Z
One should note that the size of the solution space is not sufficient to be safe. In most cases there are algorithms that do better than naive traversal, and there certainly are cases where we can find objects of desired properties in exponential spaces in polynomial time.
Raphael
CC BY-SA 2.5
2010-11-19T16:42:43.733Z
The notion of practical uniqueness might be of interest here, though. Nice catch.
Raphael
CC BY-SA 2.5
2010-11-19T16:54:16.810Z
@Raphael: You're right. For instance, to find collisions in SHA-1, the naive birthday attack needs $2^{80}$ trials, but there are more advanced attacks which needs as low as $2^{63}$ trials. That's why SHA-1 is considered insecure for many purposes. (As of 2010; see: http://csrc.nist.gov/groups/ST/toolkit/secure_hashing.html.)
Sadeq Dousti
CC BY-SA 2.5
2010-11-19T13:29:23.290Z
2010-11-19T13:29:23.290Z
Sadeq Dousti
<p>When you say <em>random numbers</em> you want to have a series of numbers such that given any sequence of $i-1$ numbers, the probability of the $i$th number having a certain value is independent from all its predecessors (I (over)simplify here), i.e.</p>

<p>$\begin{equation*}Pr[n_i = k \mid n_0, \dots, n_{i-1}] = Pr[n_i = k]\end{equation*}$</p>

<p><em>Unique numbers</em> can be generated without having to guarantee that (e.g. just counting upwards yields unique numbers). These kinds of unique numbers <em>can be guessed</em>, which make them bad <em>random numbers</em>.</p>

<p>In fact, most things that are called random-number generators in practice are <em>pseudo-random-number</em> generators. That means that they have a perfectly deterministic and predictable algorithm of constructing the next number but they start with a secret <em>seed</em> that changes from application to application. Without knowing that seed the generated series have many properties of true random sequences. That can be checked by certain statistical methods.</p>

<p>In most practical, every-day scenarios you want to have unguessable sequences, e.g. for password creation. Pseudo-random-number generators are fine for that provided you choose a proper seed; many people use the system timestamp when the request comes in, assuming this is pretty hard to predict up to the millisecond. If you really need the statistical properties of random sequences, for example for Monte Carlo simulations, you should be more wary.</p>

<p><strong>Edit:</strong> To clarify: Random sequences (R) and unique sequences (U) are not opposing concepts; you can have all combinations of both:</p>

<ul>
<li>R, !U: roll die (or observe other allegedly random event, see <a href="http://random.org" rel="noreferrer">random.org</a>)</li>
<li>R, U: roll a die with <em>lots</em> of sides and reject duplicates ( or roll many dice)</li>
<li>!R, U: use any bijective enumeration scheme, e.g. $f(n) = n$</li>
<li>!R, !U: $1,1,1,\dots$ (also: PRNG)</li>
</ul>

CC BY-SA 2.5
2010-11-19T13:52:54.920Z
Do you mean that in case of random samples are independent of each other and in case of unique they are dependent in sense that new samples must be different from old ones?
sharptooth
CC BY-SA 2.5
2010-11-19T16:36:01.850Z
Yes and no. What you mention is certainly one kind of stochastic dependency. But there can be more. In your scenario (random numbers but unique) I can only exclude a finite amount of numbers while I have no hint as to what might be the next number. Pseudo-random-number generators are "worse" insofar as as there exists a non-random function that yields the next number if you know the seed. Understand that random sequences and unique sequences are not opposing concepts; you can have all combinations of both.
Raphael
CC BY-SA 2.5
2010-11-19T13:20:34.610Z
2011-02-12T13:29:18.467Z
2011-02-12T13:29:18.467Z
Raphael
<p>Once in a while when <a href="https://stackoverflow.com/questions/3307275/">a question like "how I get good random numbers</a>" is asked the suggested approach is to just generate an <a href="http://en.wikipedia.org/wiki/Universally_unique_identifier" rel="nofollow noreferrer">UUID</a>. UUID <em>looks like</em> a random number and it is designed in such way that UUIDs likely never repeat - it is <em>unique</em>.</p>

<p>What is mathematical difference between "unique" and "random"? Why exactly should UUID not be used as a random number - for example as a cryptographic key?</p>

CC BY-SA 2.5
2010-11-19T13:19:04.617Z
Doesn't how a UUID get generated depend on the implementation? A UUID might be unique but easy to guess...
Lev Reyzin
CC BY-SA 2.5
2010-11-19T13:27:28.223Z
@Lev Reyzin: Maybe, and so I asked this question.
sharptooth
CC BY-SA 2.5
2010-11-20T17:57:50.873Z
Sorry if I wasn't clear. I meant that if a UUID can be implemented in such a way that it's easy to guess (and it can be),  then it's no good as a crypto key.  @Jukka's answer makes this point explicit.
Lev Reyzin
<cr.crypto-security><randomness>
What is mathematical difference between "random" and "unique"?
sharptooth
# What is mathematical difference between "random" and "unique"?

(Asked by: username_0 on 2010-11-19)

Once in a while when [a question like "how I get good random numbers](https://stackoverflow.com/questions/3307275/)" is asked the suggested approach is to just generate an [UUID](http://en.wikipedia.org/wiki/Universally_unique_identifier). UUID *looks like* a random number and it is designed in such way that UUIDs likely never repeat - it is *unique*.

What is mathematical difference between "unique" and "random"? Why exactly should UUID not be used as a random number - for example as a cryptographic key?

**Tags:** cr.crypto-security, randomness

> **Comments:**
> **username_1**: Doesn't how a UUID get generated depend on the implementation? A UUID might be unique but easy to guess...  
> **username_0**: @username_1: Maybe, and so I asked this question.  
> **username_1**: Sorry if I wasn't clear. I meant that if a UUID can be implemented in such a way that it's easy to guess (and it can be),  then it's no good as a crypto key.  @Jukka's answer makes this point explicit.  

---

## 3 answers

### Answer by username_4 on 2010-11-19. Score: 12 | Accepted answer

When you say *random numbers* you want to have a series of numbers such that given any sequence of $i-1$ numbers, the probability of the $i$th number having a certain value is independent from all its predecessors (I (over)simplify here), i.e.

$\begin{equation\*}Pr[n\_i = k \mid n\_0, \dots, n\_{i-1}] = Pr[n\_i = k]\end{equation\*}$

*Unique numbers* can be generated without having to guarantee that (e.g. just counting upwards yields unique numbers). These kinds of unique numbers *can be guessed*, which make them bad *random numbers*.

In fact, most things that are called random-number generators in practice are *pseudo-random-number* generators. That means that they have a perfectly deterministic and predictable algorithm of constructing the next number but they start with a secret *seed* that changes from application to application. Without knowing that seed the generated series have many properties of true random sequences. That can be checked by certain statistical methods.

In most practical, every-day scenarios you want to have unguessable sequences, e.g. for password creation. Pseudo-random-number generators are fine for that provided you choose a proper seed; many people use the system timestamp when the request comes in, assuming this is pretty hard to predict up to the millisecond. If you really need the statistical properties of random sequences, for example for Monte Carlo simulations, you should be more wary.

**Edit:** To clarify: Random sequences (R) and unique sequences (U) are not opposing concepts; you can have all combinations of both:

* R, !U: roll die (or observe other allegedly random event, see [random.org](http://random.org))
* R, U: roll a die with *lots* of sides and reject duplicates ( or roll many dice)
* !R, U: use any bijective enumeration scheme, e.g. $f(n) = n$
* !R, !U: $1,1,1,\dots$ (also: PRNG)

> **Comments:**
> **username_0**: Do you mean that in case of random samples are independent of each other and in case of unique they are dependent in sense that new samples must be different from old ones?  
> **username_4**: Yes and no. What you mention is certainly one kind of stochastic dependency. But there can be more. In your scenario (random numbers but unique) I can only exclude a finite amount of numbers while I have no hint as to what might be the next number. Pseudo-random-number generators are "worse" insofar as as there exists a non-random function that yields the next number if you know the seed. Understand that random sequences and unique sequences are not opposing concepts; you can have all combinations of both.  

---

### Answer by username_2 on 2010-11-19. Score: 11

I guess the main source of confusion is that there are many versions (and many implementations) of UUIDs.

**Random but not unique:** As you can see from the Wikipedia article, version 4 UUIDs are just 122-bit random numbers. Nothing else. They are exactly as good for cryptographic purposes as the random number generator that you used to implement it. And they are not "unique" in any other sense except that it's highly unlikely to get collisions (at least if you use a good random-number generator).

**Unique but not random:** In the other extreme we have version 1 UUIDs, which concatenate MAC addresses with timestamps. Assuming that the MAC addresses are globally unique (as they are supposed to be, as there is a central authority that allocates them), and assuming that you don't generate UUIDs too rapidly, then the end result is something that is guaranteed to be globally unique. However, it is not "random" in any sense; if you know who generated the UUID and when, you can predict the value of the UUID fairly accurately. Obviously, it is an extremely bad idea to use such UUIDs as a replacement of random numbers in any cryptographic application.


---

### Answer by username_3 on 2010-11-19. Score: 5

An object is *mathematically* unique, if there does not exist **another** object which satisfies the properties of the first object. For instance, the solution of $7x+2=5$ is unique (over reals), while the solution of $x^2=4$ is not unique (over reals).

An object is *practically* unique, if there is not an **efficient** procedure which finds another object that satisfies the properties of the first object. For instance, let $H(\cdot)$ be a [cryptographically secure hash function](http://en.wikipedia.org/wiki/Cryptographic_hash_function). By definition, the solution to $y=H(x)$ is (practically) unique; That is, while there are mathematically infinitely many $x$'s which satisfy $y=H(x)$, there is no efficient procedure which, given $y$ and $x$, can find $x' \ne x$ such that $y=H(x')$.

This is the case with UUID's. Given a (random) seed, the UUID generator produces a (practically) unique UUID; That is, it is practically infeasible to find two seeds $s \ne s'$ such that $UUID(s) = UUID(s')$, while *mathematically* such seeds exist.

When I teach this concept in the class, I usually provide an example: Assume that, to find such a *collision*, one must try $2^{128}$ seeds. This number is so high that it is beyond the (estimated) amount of particles in the known universe!

> **Comments:**
> **username_0**: Does this imply that UUIDs can be used as cryptographic keys?  
> **username_3**: @username_0: Strictly speaking, collision-freeness does not imply randomness. In addition, the seed to the UUID generator might not be a random string. (It might be a URL, an FQDN, an object identifier, a distinguished name, etc.) Please seek the Wikipedia entry you cited in the question for more info.  
> **username_4**: One should note that the size of the solution space is not sufficient to be safe. In most cases there are algorithms that do better than naive traversal, and there certainly are cases where we can find objects of desired properties in exponential spaces in polynomial time.  
> **username_4**: The notion of practical uniqueness might be of interest here, though. Nice catch.  
> **username_3**: @username_4: You're right. For instance, to find collisions in SHA-1, the naive birthday attack needs $2^{80}$ trials, but there are more advanced attacks which needs as low as $2^{63}$ trials. That's why SHA-1 is considered insecure for many purposes. (As of 2010; see: http://csrc.nist.gov/groups/ST/toolkit/secure_hashing.html.)  

---

