Seeding random number generators

In our discussion of random number generators so far, we've seen the generator's period as a major limiting factor in "how much randomness" it can generate. But an equally important— and sometimes more important— issue is how we seed or initialise a random number generator.

Let's take, for example, Java's standard generator java.util.Random, which has a period of 2⁴⁸. We can imagine this as a huge wheel with 2⁴⁸ randomly-numbered notches. Whenever we create an instance of java.util.Random, the wheel starts in a "random" place, and moves round by one notch every time we generate a number from that instance. Wherever we start from, we'll end up back at the same place after generating 2⁴⁸ numbers. If the place where we start is "truly random", then a sequence length of 2⁴⁸ may be sufficient for our application. But how do we pick a random place on the wheel to start from?

The random place that we start from is in effect the seed or initial state of the generator. For this, we ideally want to pick a number (or some sequence of bits) that is "truly unpredictable". Or put another way, we want to find some source of entropy (or "true unpredictability") available to the program.

System clocks and System.nanoTime()

The traditional solution used by java.lang.Random is to use one of the system clocks that the computer makes available. In recent versions of the JVM, the measure taken is that reported by System.nanoTime(), which typically gives the number of nanoseconds since the computer was switched on. (In older versions of the JVM, or possibly as a fallback position on some platforms, System.currentTimeMillis() is used, which reports the current "wall clock" time in milliseconds since 1 Jan 1970.)

So how good is System.nanoTime()? Well, on the face of it, it's a 64-bit value, so ample for generating starting points for all 2⁴⁸ possible sequences. But now consider that there are "only" 10⁹ nanoseconds every second. So in the first five minutes that the computer is switched on, "only" 3x10¹¹— or about 2³⁸— possible values could be returned by System.nanoTime(). In other words, in the first 5 minutes of the computer being on, only about one thousandth of the possible series of java.lang.Random will ever be generated. (Of course, if Windows takes three of those five minutes to boot up, and/or if the system cannot actually report timings with nanosecond granularity, that reduces the number of possibilities even further...) For many casual applications, 2³⁸ possibilities or something in that order is still plenty. But we certainly wouldn't want to use System.nanoTime() to seed, say, a random encryption key, or a "serious" game or gambling application where a user's ability to guess the random sequence could result in financial loss.

Of course, for such applications, we also shouldn't be using java.lang.Random. But the problem of seed selection still applies. Even if we have a high-quality random number generator with a period of, say, 2¹⁶⁰, that period doesn't really buy us "extra randomness" if we are only able to generate, say, 2³⁸ distinct seeds and/or an adversary can make further predictions about the seed.

Looking for other sources of entropy

To get more randomness in the choice of the generator's "initial position", we need to look for more sources of entropy on the local machine. On the next page, we discuss approaches to finding entropy for seeding a random number generator.

---