True Random Number Generators (TRNGs)

Motivation and Background

Random numbers are extensively used in a wide variety of cryptographic operations. Almost all cryptographic protocols require the generation and use of secret values that must be unknown to attackers. For instance, asymmetric (public key) algorithms such as RSA, DSA, and Diffie-Hellman use public/private keypairs that are required to be generated by random number generators. Moreover one time pad -the only unconditionally secure encryption system - uses as much key material as ciphertext and requires that the keystream be generated from a truly random process. Since security protocols rely on the unpredictability of the keys used, random number generators for cryptographic applications must meet stringent requirements. The most important criterion is that any adversary with full knowledge of the RNG design must not be able to make any useful predictions about the bits that are going to be used next even if he knows all the previously generated bits. A good RNG must be able to provide the following:

Equal probability: A random number generator should have the quality of giving an equally probably random number. Just as flipping a coin should produce heads or tails at the same probability or a dice should produce one of its sides at an equal chance as its others, a random number generator should produce a random number within its range that is equally probable. Each RNG, therefore, must be tested so that their outputs shall be statistically acceptable.

Unpredictability: A good quality of a RNG in the field of cryptography is that it generates numbers that seem to not be related to previous or future values. If given a previous value generated by an RNG in a crypto-application, the current or later values should not be able to be guessed. If they were, it would compromise any future uses of the crypto-application. If the application were used for encryption, all previous and future encrypted information could be determined.

Randomness sources can be classified as either true-random or pseudo-random. Most random number sources actually utilize a pseudorandom number generator (PRNG), which uses deterministic processes to generate a sequence of output bits from a truly random seed. Since the output is purely a function of the seed, the entropy of the PRNG output can never exceed the entropy of the seed. Security of PRNGs rely on the computational bound on the adversary such that it can be computationally infeasible for him to distinguish a good PRNG from a perfect RNG. Examples of PRNGs designed for cryptographic applications include MD5Random and SHA1Random.

As opposed to pseudo-random sources, which are good only against computationally limited adversaries, true-random sources can be considered unconditionally unguessable, even by an adversary with infinite computing resources. Besides, a PRNG by itself will be insecure without a seed produced by a TRNG. As a source of entropy TRNGs generally measure some source of noise that is nearly indeterminable, so that the measurements are likely to be any value within a certain range. For example, the amount of radiation that a Geiger counter detects in a normal setting will be random. Then the bits of the raw data from the entropy source should be corrected for any abnormalities or bias that might exist. The correction should at least include an XOR corrector or a Von Neumann corrector.

Our Research

Design and analysis of provably secure true random number generators (TRNGs) for cryptographic hardware applications.

Publications

B. Sunar, W. J. Martin, D. Stinson, A Provably Secure True Random Number Generator with Built-in Tolerance to Active Attacks -- PREPRINT (PDF)
B. J. Abcunas, S. P. Coughlin, G. T. Pedro, D. C. Reisberg, Evaluation of Random Number Generators on FPGAs, MQP Report, (PDF)
W. R. Coppock, C. R. Philbrook, A Mathematical and Physical Analysis of Circuit Jitter with Application to Cryptographic Random Bit Generation, MQP Report, (PDF)

Links to Other Research Groups

These links open in a new browser window. Neither WPI nor the CRIS lab are responsible for the content of these external web sites.

Notes on random number generators by Robert Davies
Online resources for collecting and processing crypto-strength randomness by David Wagner (UC Berkeley)

References

M. Bucci, and R. Luzzi. Design of Testable Random Bit Generators. In Cryptographic Hardware and Embedded Systems - CHES 2005, pages 147-156. Springer-Verlag, 2005.
B. Barak, R. Shaltiel, and E. Tromer. True Random Number Generators Secure in a Changing Environment. In Cryptographic Hardware and Embedded Systems - CHES 2003, pages 166-180. Springer-Verlag, 2003.
Carl Ellison. Cryptographic Random Numbers. Windows Developer Magazine, August 2002.
Benjamin Jun and Paul Kocher. The Intel random number generator. Technical report, Intel Corporation, April 1999.

Maintained by webmaster@wpi.edu
Last modified: Feb 07, 2006, 12:15 EST