1True Random Number GeneratorsKeerat Brar, Shashi Prashanth Karanam {kbrar, skaranam} @ gmu.eduAbstract— This paper discusses the randomness sources, sampling mechanisms and post processing required for a true random number generator (TRNG). We investigate three different implementations of a hardware based TRNG using pure digital circuits. The primary sources of randomness talked about are random delays and transition times of all the logic gates in a circuit, Metastability and Jitter. We discuss the challenge of extracting random bits from the entropy source and introduce the post processing to eliminate the bias in the random bits.Index terms - TRNG, Metastability, Jitter, Entropy, post processing, Ring oscillators.I . INTRODUCTIONRandom number generators (RNGs) have numerous applications in diverse set of areas ranging from statistics to cryptography to art. Many cryptographic primitives such as generation of session keys, initialization vectors, nonces, security protocols, cryptographic accelerators, Smart cards, padding of plaintext messages amongst others like Microprocessors, sensors, wireless networks and many more depend on the generation of true random numbers. A TRNG for cryptographic applications must meet stringent requirements since all the security protocols depend on the unpredictability of the keys or initialization vectors used. Thus, an adversary having complete knowledge about the design of TRNG must not be able to predict the future bits. A TRNG is one in which the probability to generate a bit is constant or the bits generated are statistically independent and unbiased. RNGs can be classified [1] as pseudo random number generators (PRNGs) or TRNGs. PRNG is a function which once initialized by a seed (Random value) generates a sequence of numbers which approximates the properties of true random numbers. Given the same seed value the PRNG will always produce the same sequence. TRNGs exploit randomness which occurs in physical phenomenon in which sources are faster, higher in quality and more protected by themselves. TRNGs base their outputs entirely on an underlying random physical process. Unlike their deterministic cousins there is no internal state kept in the generator and the outputs are based only on the physical process and not on any previously produced bits.In the remainder of this paper, we present a generic architecture for a TRNG briefly discussing the blocks to make a computationally secure TRNG. It defines Metastability and Jitter which are used as the sources of entropy. The first realization uses Metastability and Jitter for random bit generation based on two free running oscillators. These oscillators switch between metastable phase and bistable phase eventually acquiring a random bit. The second design utilizes jitter as the randomness source. It has a large number of ring oscillators with identical ring lengths as the noise source. The non random samples are eliminated by appropriate post processing based on resilient functions. We then introduce a new method for true random number generation replacing the ring oscillators with Fibonacci and Galois oscillators.II . GENERIC ARCHITECTUREA good TRNG design relies on the quality of three basic components Viz. a Randomness source, a Sampler and a Post processing unit.Fig. 1. Generic Architecture of a TRNG Randomness Source: Entropy can be defined as a measure of uncertainty associated with a random variable. The available noise sources (Entropy source) for a TRNG are from physical processes such as electronic noise, chaotic circuits and nuclear delay amongst others. The most widely used technique to generate a random bit stream using digital elements is either by sampling the jittered oscillations or by harvesting the metastabilites in flip flops. Harvesting Mechanism: The entropy source is cached using a harvesting mechanism which does not disturb the physical process but yet collects the maximum entropy. A digitizer (usually a sampler extracting a digitized noise signal) functions as the harvesting mechanism.2 Post Processing: A postprocessor masks the imperfections in an entropy source. It provides tolerance in the presence of environmental changes or tampering. Post processing increases the entropy of random bits by applying a compression function on the digitized noise signal resulting in a lower speed output stream with increased randomness. A few examples of the postprocessing block are Von Neumann corrector, XOR corrector, Hash function (ex: Sha-1), Resilient functions etc. This component might not be needed in all designs but should be employed to strengthen the design if the sources exhibit a bias. Statistical tests: Traditionally, a RNG has to pass through a battery of statistical tests from any of the standard vendors such as NIST, DIEHARD, BSI that certifies randomness properties of TRNGs.III . DIGITAL IMPLEMENTATIONSTwo possible causes of randomness metastablility and jitter are briefly discussed below.a) Metastability: By violating the setup and hold conditions of a Flip flop, the pair of gates internal to the flip flop which are usually cross connected will behave unpredictably or oscillate about some intermediate voltage which is neither a logical High or a logical Low. These oscillations die after sometime and the flip flop finally settles down into a logical high or low, giving rise to a source of randomness.b) Jitter: Jitter is defined as the short-term variations of a digital signal's significant instants from their ideal positions in time [2]. Jitter consists of two components, deterministic and non deterministic jitter (used for TRNG). Random jitter is based on a Gaussian distribution i.e. its standard deviation will grow with time. There are several ways to characterize jitter like period jitter, cycle to cycle jitter, n-cycle jitter and time interval error. The
View Full Document
Unlocking...