An advance in random number generation? Who cares? What’s so important about improving the way we generate random numbers, and how does this tie in with security?
What are random numbers?
Random numbers are numbers that are completely unpredictable, and they are of paramount importance in cryptography. Most cryptographic algorithms depend in some way on random numbers, usually for generating passwords and cryptographic keys.
Unfortunately, it is extraordinarily difficult to generate sequences of numbers that are even close to being truly random. In fact there’s no known way to generate truly random numbers. The best we can do is to generate sequences that have high entropy – a measure of unpredictability. The higher the entropy, the closer a sequence is to being truly random.
High entropy sequences are obtained from physical sources such as radioactive decay or electrical “noise” generated from electrical circuits. Specialized hardware does use these, but consumer grade computers have to make do by using more prosaic sources such as keyboard and mouse interactions by users.
It isn’t practical to use these high entropy sources for random number generation, as they are inefficient. Instead, computers use pseudo-random number generators (PRGs) which take a high entropy source as input – known as the seed – and generate a random-looking sequence. This sequence is entirely deterministic, but if the seed has sufficient entropy, it is difficult for an attacker to replicate the sequence. Of course, the seed must be kept private!
If an attacker can guess the seed, the random number sequence is compromised and all sorts of nasty things can be done, ultimately leading the attacker to recover the plaintext of encrypted messages.
This is why the reported advance in random number generation by researchers at the University of Texas at Austin is so important. The new technique produces high entropy random numbers with considerably less effort than previous techniques.
How does it work? Basically, the new method takes two low entropy sequences of numbers (known as “weakly random” sequences) and turns them into one much higher entropy sequence. It is known as two-source extraction.
This means that high entropy seeds can be more efficiently generated, and consequently more unpredictable (and thus more secure) pseudo-random number sequences are possible. The end result will be stronger cryptography, and ultimately better security.