Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Once in a while when a question like "how I get good random numbers" is asked the suggested approach is to just generate an UUID. 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?

share|improve this question
2  
Doesn't how a UUID get generated depend on the implementation? A UUID might be unique but easy to guess... –  Lev Reyzin Nov 19 '10 at 13:19
    
@Lev Reyzin: Maybe, and so I asked this question. –  sharptooth Nov 19 '10 at 13:27
    
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 Nov 20 '10 at 17:57
add comment

3 Answers 3

up vote 10 down vote accepted

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)
  • 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)
share|improve this answer
    
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 Nov 19 '10 at 13:52
    
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 Nov 19 '10 at 16:36
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
Does this imply that UUIDs can be used as cryptographic keys? –  sharptooth Nov 19 '10 at 13:34
    
@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 Nov 19 '10 at 14:29
    
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 Nov 19 '10 at 16:31
    
The notion of practical uniqueness might be of interest here, though. Nice catch. –  Raphael Nov 19 '10 at 16:42
1  
@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: csrc.nist.gov/groups/ST/toolkit/secure_hashing.html.) –  Sadeq Dousti Nov 19 '10 at 16:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.