Unique values are needed everywhere in modern computing: ActiveX GUIDs, HTTP session cookies, ... However, while some of those values have no identified security impact (e.g. ActiveX GUIDs), others shall meet very strong security properties (e.g. HTTP session cookies).
An attacker should at least not be able to guess some or all values that have been or will be generated. A stronger property is the inability for the attacker to guess past or future values, even if he has access to a subset of generated values at some point.
Let's take a "uniqueness generator" that returns an integer value (whatever size is that integer). How unique this value can be?
Unique values
The value is unique if two successive calls to the same function are guaranteed not to yield the same result.
This property is very easy to achieve, either through a monotonous counter (0, 1, 2, 3 ...) or a timestamp. But those generators do not meet even the lowest security requirements formulated before: they are very easy to predict at any time. Fortunately, cookie value == timestamp has disappeared from the Internet years ago.
Some better generators exist, such as GUID and UUID. Older GUID generators were based on MAC address and timestamp, therefore having far lesser possible outputs than the entire value space. Recent GUID generators are based on cryptographically sound random generators (see below).
Of course, there are limits to "uniqueness": at least the size of the output value. Everything stored on 32 bits will be easy to find out, even if it comes out of a 160 bits hashing algorithm. Moreover, values can be unique to a given computer only, a given process, or even a given thread.
Random values
For security-related tasks, it is often critical to use non-predictable unique generators. Therefore most people began to think "unique == random".
However, true randomness is very difficult to achieve (as PHP knows).
The simplest random generator is the Linear Congruential generator. All values are correlated through the following formula: xn+1 = A * xn + B [N], where A, B and N are fixed values.
On Windows, the rand() function of MSVCRT.DLL uses the following parameters:
A = 214013
B = 2531011
N = 232
Internal state is maintained on 32 bits. However, only the 16 upper bits are returned as a result, masked with 0x7fff. Therefore, rand() produces values between 0 and RAND_MAX, which has a hardcoded value of 215.
This is confirmed on Windows Seven 64-bit as seen below.
Therefore, the odds of guessing rand() output on a single shot is 1 out of 215, which is already bad (as DNS knows).
But finding out rand() internal state (which is trivial with a few known output values) could prove far more catastrophic. In fact, rand() should never be used at all - it is mostly there for compatibility reasons. Good Windows applications make use of CryptGenRandom().
Out of curiosity, I also had a look at the GNU libc. It turned out that rand() has several implementations, the most basic of which (referred as "type 0") being a Linear Congruential generator with the following parameters:
A = 1103515245
B = 12345
N = 232
B = 12345
N = 232
RAND_MAX = 231
Using this generator to produce int or unsigned int values will immediately leak the internal generator state to the client.
Newer implementations use a Linear Feedback Shift Register.
Secure values
As we saw earlier, random does not always mean secure. But even if the developer used a cryptographically strong random generator, it can still fall prey to implementation mistakes.
One recent example I had is the (Sun provided) java.rmi.server.UID class. Each word is important:
"A UID represents an identifier that is unique over time with respect to the host it is generated on, or one of 216 "well-known" identifiers. (...) A UID instance contains three primitive values:
unique, an int that uniquely identifies the VM that this UID was generated in, with respect to its host and at the time represented by the time value (an example implementation of the unique value would be a process identifier), or zero for a well-known UIDtime, a long equal to a time (as returned by System.currentTimeMillis()) at which the VM that this UID was generated in was alive, or zero for a well-known UIDcount, a short to distinguish UIDs generated in the same VM with the same time value"
So, secure or not? Hard to tell from the documentation ... Let's run the following code sample:
package uidtest;
import java.rmi.server.UID;
public class Main {
public static void main(String[] args) {
for (int i=0; i < 5; i++) {
UID u = new UID();
System.out.println(u);
}
}
}
$ javac uidtest.java
$ java uidtest
-8241e54:12334a437e6:-8000
-8241e54:12334a437e6:-7fff
-8241e54:12334a437e6:-7ffe
-8241e54:12334a437e6:-7ffd
-8241e54:12334a437e6:-7ffc
So, it appears that this UID generator is a simple monotonous counter.
Since the Sun JDK has been open-sourced, it is possible to have a deeper look at the implementation:
public UID() {
synchronized (lock) {
if (!hostUniqueSet) {
hostUnique = (new SecureRandom()).nextInt();
hostUniqueSet = true;
}
unique = hostUnique;
if (lastCount == Short.MAX_VALUE) {
boolean interrupted = Thread.interrupted();
boolean done = false;
while (!done) {
long now = System.currentTimeMillis();
if (now <= lastTime) {
// wait for time to change
try {
Thread.currentThread().sleep(1);
} catch (InterruptedException e) {
interrupted = true;
}
} else {
lastTime = now;
lastCount = Short.MIN_VALUE;
done = true;
}
}
if (interrupted) {
Thread.currentThread().interrupt();
}
}
time = lastTime;
count = lastCount++;
}
}
First field is initialized with SecureRandom() ... once per process.
Second field is time in milliseconds. Second field changes when all possible values for the third field have been exhausted.
Third field is a monotonous 16-bit counter.
Conclusion: you should not rely on Java UID class for secure UID generation!
