Introduction

A Random Number Generator (RNG) plays a critically important role in cryptography. Most programming languages and compilers provide functionality for generating "random" numbers as part of their standard libraries, but using these for cryptographic purposes is always a bad idea. The most common requirement of an RNG is in systems dealing with encryption. The security of the most commonly used government-certified cryptographic protocols relies heavily on the availability of unguessable random values.

The requirements for the "quality" of random numbers for such cryptographic applications vary: generation of master keys and session keys require full-entropy data with the highest strength reserve, whereas other requirements like generation of nonces and salts require unpredictability and unique values.

The core of the Random Number Generator and the source of the seeds required for the generation of pseudorandom bits is a 384-byte randomness pool that is periodically replenished with random data collected from various physical sources using an algorithm designed to meet the following requirements:

1. An adversary with full knowledge of the underlying software, hardware, and all sources of randomness must not be able to predict the pool content.
2. At any given instance, if the internal state of the generator becomes available to the adversary, the safety of the past outputs must remain intact.

To ensure that these requirements are met, the pool is refilled with new random data from a variety of highly unpredictable sources so that should any of them fail, the security of the generator is not compromised. The following are the sources used to fill the randomness pool:

• Fast entropy sources collected at 500 ms intervals:
  • Thread and process information and memory status.
  • High-precision CPU timestamps and system counters.
  • Various Win32 handles and window information.
  • MS Windows BCryptGenRandom.
  • x86 on-chip hardware RNG (RDSEED and RDRAND).


• Slow entropy sources:
  • Hardware RNG based on CPU timing jitter.
  • Disk I/O statistics.
  • System performance and interrupt information.
  • Networking statistics for TCP/IP and Lanman.
  • CoreTemp CPU temeratures.
  • GPU-Z hardware information.
  • Mouse movement and user keystrokes.

Instead of overwriting the existing data in the pool, the new data obtained from the above sources is added to the pool using modulo 2⁸ addition, which ensures an increase in the pool's entropy over time.

Mixing The Pool

The pool mixing operation is at done frequent intervals, for example after every 32 bytes written to the pool and each time before any output is generated from it. This step performs diffusion within the pool while preserving its total entropy which ensures that every bit in the pool affects every other bit and also removes statistical biases.

This RNG uses a cryptographically secure one-way hash function to transform the content of the pool using the following procedure:

Let p be the size of the randomness pool.
Let SHA512 be the underlying hash function with the digest size d.
Let P_i be the i-th block of size d, where the number of blocks in the pool is given by n = p/d.
Let R_i be the i-th block of the new pool after the mixing operation has been applied to it.

for i = 0 to n-1 do
done

For example,

Hence, we obtain the new pool R = R₀ || R₁ || ... || R_n-1

Generating Random Values

While extracting data from the pool, its content is never directly copied to the destination. Therefore, even if an attacker obtains the output generated by the RNG, it is infeasible for him to determine any prior outputs. The following procedure is followed to extract data from the pool:

1. If there hasn't been a slow poll at least once, call the slow poll function to collect new random data from the system and add it to the pool.
2. After every byte is written to the output buffer, the pool read cursor advances by one byte. If the cursor reaches the end of the pool, it wraps back to the beginning.
3. Mix the pool and XOR its content to the output buffer. Invert every bit in the pool and mix it again to create the new pool and XOR its content to the output buffer.
4. Mix the pool one final time (this does not affect the final output) and export the final value to the caller.

The pool mixing operation is done thrice in the above process: the first time to create a dependency of the generated output on the entire pool content and to prevent state leaks in case the attacker has access to values in the memory, a second time after inverting the bits to create the new pool, and a final third time so that the generated output is not compromised even if the adversary has an opportunity to read the pool content at a later stage.

Fast DRBG For Pseudorandom Data

Although maximum bit strength is necessary for purposes like key generation, the aforementioned method of extracting entropy from a running system is very slow in practice. For weaker uses like nonces, initialization vectors, and salts, a compromise can be made in the strength reserve of the required data to achieve a higher bit rate. Xrand has a Deterministic Random Bit Generator (DRBG) to serve such purposes, which is based on the CTR_DRBG mechanism specified by SP 800-90A. This implementation uses AES-256 in counter mode as the underlying block cipher without a derivation function or prediction resistance.

The DRBG is periodically seeded with full entropy data from the main RNG and the pseudorandom bits are generated by repeatedly updating the internal state of the DRBG using the AES operation with the random data as the key and a sequentially updated 128-bit counter.

References And Design Origins

The Random Number Generator is based on the following publications and existing designs:

• Cryptographic Random Numbers by Carl Ellison.
• Software Generation of Practically Strong Random Numbers by Peter Gutmann.
• Random Number Generators - Principles and Practices by David Johnston.
• The TrueCrypt Random Number Generator.
• The GnuPG Random-Number Subsystem Architecture.

---

Written by Vibhav Tiwari for Xrand