Random Number Generation and Information Security

11 11 2012

by Siwen Zhao

Random Number Generation (RNG) is one of the most critical issues in ensuring information security. Many methods for securing our information need random numbers. For example, random numbers are used in creating keys (e.g. one time pad) for data encryption, generating large primes for asymmetric key exchange and selecting CAPTCHA strings for authentication. Because random numbers are so important in information security, we would always want to develop RNG methods that can generate numbers with greater randomness.

Before discussing the details of RNG, it is important to understand what randomness is. Truly random numbers [1]

  • Are unpredictable, and  [1]
  • Cannot be subsequentially reliably reproduced. [1]

Therefore, only RNG methods that generate random numbers with the two characteristics above can achieve true randomness and are immune to random number attacks.

However, true randomness is very hard to attain, which leaves our information vulnerable to attack once the “random” numbers get cracked. With interests in how we generate random numbers and how the “randomness” can be cracked, I would like to discuss, in the rest of this blog, the major methods of RNG and how they work, some thoughts on what are the pros and cons for each category of methods, and some current issues and developments.

The RNG methods can be categorized based on their random sources. “Random sources can be classified as either true-random or pseudo-random.” (Ellison) [2]We will look at these two categories one by one in the following sections.

True Random Number Generator

True Random Number Generator (TRNG) is also called physical generators [1] where physical devices are at present to be the random sources. The physical actions collected from the devices then will be translated into digital bits with some mathematical functions (calculation of Entropy [2]). Then the outcome will be our random numbers. One of the earliest TRNG would be the use of traditional gambling devices. [3] Nowadays, common sources are decay of radioactive material, quantum mechanics processes, thermal and other types of noise, frequency instability of free-running oscillators [1].

With the early adoption of gambling devices being relatively less random, TRNG with all the modern random sources mentioned above generate numbers with high level of randomness because the particle reactions and the oscillations are very hard to predict or to get the exact same result when redoing the processes. However, all these random resources would need certain environment and space for the physical actions to take place, which is very difficult to implement on computers or other modern computational devices. Moreover, even being used for generating random numbers for computers, these factors could be slow and with ill-defined distributions [2].

One recent development to cover the downsides of physical random number generator is the introduction of Digital Random Number Generator (DRNG) from Intel. Intel declares that this new DRNG includes a high-quality entropy source on the chips [4]. Intel somehow managed to put this secret physical thing on their chips to provide source of entropy and the numbers generated would go directly in to the computing operations in the computer. Therefore, the numbers are physical generated that are highly random, and the generation can be much faster than any other physical sources.

Pseudo Random Number Generator

As the name suggested, Pseudo Random Numbers are not real random numbers, they are computer-generated numbers that appear to be random.  The most commonly used scheme for Pseudo Random Number Generators (PRNGs) is “multiplicative linear congruential”. [5] Function used as shown below, n is a very large prime number, and with carefully selection of a, b and n, we can generate a long sequence of numbers distributed randomly between 0 and n-1. If we make n a huge prime number, the number sequence would look pretty random. However, as random as r is, a, b, n and the initial seed  are not random at all, we have to choose them very carefully to make sure no one crack our random. Take the java random function as an example, if we deliberately give the same seed to the Random method, we would get the same sequence of number. And in many random functions, time or date at the present would be taken as the seed. Therefore, if some attacker has access to the context of when and where, or by who the random number is generated, or the number sequence is really long that it reveals some pattern, the attack may have a good chance of cracking the random.

Therefore, the PRNG is not as random therefore secure as TRNG. However, it does have the advantage of fast computing and easy to be adopted in computers. Also, if we need a really long sequence of random numbers, the physical devices may not have enough states for us to translate them in to so many digits [2]. Therefore, PRNG does better in generating longer sequence of random numbers than TRNG does.

As both TRNG and PRNG have advantages and disadvantages, at the end, it really comes down to where they would be used. It is very important to analyze the requirements before adopting any methods. And this applies not only to the security requirements, but also to business requirements, budgeting requirements, social requirements and all other factors involved. At the same time, we may see more developments on the combination of both TRNG and PRNG that keep the strengths of both TRNG and PRNG and overcome some weakness of each, as we have already seen in Intel’s DRNG mentioned previously.

___________

[1] Šimka, Martin, Miloš Drutarovský, and Viktor Fischer. “Random Numbers in Cryptography” 06 Dec 2006. Keynote.

[2] Ellison, Carl. “Cryptographic Random Numbers.” THE WORLD. P1363 standard. Web. 24 Oct 2012. <http://world.std.com/~cme/P1363/ranno.html&gt;.

[3] Warnock, Tony. “LOS ALAMOS SCIENCE.” LOS ALAMOS SCIENCE. Special Issue, Stanislaw 1909-1984 (1987): 137-141. Web. 22 Oct. 2012. <http://www.fas.org/sgp/othergov/doe/lanl/pubs/00418729.pdf&gt;.

[4] “Intel® Digital Random Number Generator (DRNG) Software Implementation Guide.” Intel. Intel Corporation, 08 Aug 2012. Web. 22 Oct 2012. <http://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide/&gt;.

[5] Roehrig, Stephen, “Program Control” Object-Oriented Programming, 6 Sept 2012. Keynote.

Advertisements

Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: