Background Papers on Cryptographic Sources of Randomness

Mining Your P’s and Q’s: Detection of Widespread Weak Keys in Network Devices:

Summary: The authors conducted an Internet-wide scan of RSA public keys and DSA signatures. With this information, they searched for pairs of hosts whose RSA keys share prime factors, or whose DSA signatures share ephemeral keys. Both scenarios potentially compromise each host’s private key. The study showed that devices are vulnerable when they generate keys on boot, before the OS has been able to collect sufficient entropy to seed their pseudo-random number generators.

Thoughts: The results of this study seem to indicate that currently used entropy sources provide good sources of randomness when given sufficient collection time. However, the authors note that several popular implementations of RSA and DSA do not use the Linux interface random, which blocks until sufficient entropy has been collected, but instead use random, which immediately returns with the requested number of random bytes. The authors also note that the greatest vulnerabilities come from imbedded or headless devices that do not have user input nor, sometimes, disk drives. Both of which are commonly used to generate entropy.

This discussion seems to indicate that our work should focus on sources of randomness that would be available to such embedded devices. Also, it would be helpful if an entropy source could be discovered that would quickly generate randomness. This would discourage developers from dismissing the use of a blocking implementation.

Analysis of the Linux Random Number Generator:

Summary: The authors have analyzed the source code for the Linux Random Number Generator (LRNG). They provide details as to its functionality and mention several potential security flaws. The LRNG maintains three separate entropy pools. The primary pool gets takes entropy from mouse/keyboard inputs, disk I/O operations, and certain interrupts. The secondary and urandom pools then take entropy from the primary pool. The secondary pool feeds the random system call which blocks until sufficient entropy has been gathered. The urandom pool feeds the urandom system call which immediately returns with the requested number of random bytes, regardless of the amount of entropy gathered.

Thoughts: Most of the vulnerabilities described by the authors seem to be a result of the specific implementation of the LRNG, and could be remedied by the solutions that the authors suggest. The largest vulnerability however, is for embedded devices with no hard disk such as certain routers. As the authors note, the only real source of entropy is network interrupts which are also potentially observable by an attacker. The best advancement to the field would be to find a better source of entropy for embedded devices such as this.

When Good Randomness Goes Bad: Virtual Machine Reset Vulnerabilities and Hedging Deployed Cryptography:

Summary: The authors discuss how a VM snapshot may cache cryptographic randomness. Running from this snapshot can then lead to using repeated, and thus predictable randomness. The most significant/likely vulnerability is that DSA may generate a repeated r value due to the RNG being seeded with the same, old value.

The authors also discuss a method for hedging against potential randomness failures. The general idea is to hash the generated random bits before using them in any cryptographic operation. This does not alleviate the problem of bad randomness, but ensures slightly stronger security in the face of a bad RNG.

Thoughts: The authors have pointed out a significant vulnerability that comes about from repeated randomness. They point out that the problem can be solved by ensuring that fresh randomness is incorporated into any cryptographic operations immediately before it is computed. They do mention however, that this may be a problem if such randomness sources are also cached. Therefore, they suggest using hardware generated randomness for this purpose rather than an entropy pool such as the Linux random number generator, which may be cached. This discussion highlights the largest problem in the field: there is a tradeoff between performance and security. It may take a significant amount of time to generate sufficient entropy for many cryptographic operations to be considered secure. However, many developers are more interested in the performance of their applications, and are not willing to wait for this security.

The authors also discuss hedging which adds some security in the face of a bad RNG. However, they note that this merely allows a function to fail gracefully. Therefore, despite this method, effective random number generation is still extremely important.

A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications:

Summary: This paper describes a test suite that can be used to determine if a given random number generator outputs bit sequences that are sufficiently random. The main purpose of the tests described is to ensure that the random number generator produces bits that are uniformly random, and completely independent. The following table outlines each test and its purpose.

  

Test	Purpose
The Frequency (Monobit) Test	Determine whether the number of ones and zeros in a sequence are approximately the same as would be expected for a truly random sequence
Frequency Test within a Block	Determine whether the frequency of ones in an M-bit block is approximately M/2, as would be expected under an assumption of randomness.
The Runs Test	Determine whether the number of runs of ones and zeros of various lengths is as expected for a random sequence.
Tests for the Longest-Run-of-Ones in a Block	Determine whether the length of the longest run of ones within the tested sequence is consistent with the length of the longest run of ones that would be expected in a random sequence.
The Binary Matrix Rank Test	Check for linear dependence among fixed length substrings of the original sequence.
The Discrete Fourier Transform (Spectral) Test	Detect periodic features (i.e., repetitive patterns that are near each other) in the tested sequence that would indicate a deviation from the assumption of randomness.
The Non-overlapping Template Matching Test	Detect generators that produce too many occurrences of a given non-periodic (aperiodic) pattern.
The Overlapping Template Matching Test	Same as Non-Overlapping Template Matching Test but when the pattern is found, the window slides only one bit before resuming the search.
Maurer's "Universal Statistical" Test	Detect whether or not the sequence can be significantly compressed without loss of information.
The Linear Complexity Test	Determine whether or not the sequence is complex enough to be considered random.
The Serial Test	Determine whether the number of occurrences of the 2m m-bit overlapping patterns is approximately the same as would be expected for a random sequence.
The Approximate Entropy Test	Compare the frequency of overlapping blocks of two consecutive/adjacent lengths (m and m+1) against the expected result for a random sequence.
The Cumulative Sums (Cusums) Test	Determine whether the cumulative sum of the partial sequences occurring in the tested sequence is too large or too small relative to the expected behavior of that cumulative sum for random sequences.
The Random Excursions Test	Determine if the number of visits to a particular state within a cycle deviates from what one would expect for a random sequence.
The Random Excursions Variant Test	Detect deviations from the expected number of visits to various states in the random walk.

Thoughts: This test suite will be very useful for our purposes. It will be crucial in testing the sources of randomness that we come up with. A RNG is of no use if its results are not random or independent as an attacker may be able to gain information if the RNG is used for cryptographic purposes.

How to Generate Cryptographically Strong Sequences of Pseudo Random Bits:

Summary: The authors present a pseudo random number generator that, given a random seed, is capable of producing a statistically random bit sequence. The generator relies on the intractability of the Discrete Logarithm Problem to show that given any sequence of generated bits, an attacker cannot predict the next bit with probability greater than 0.5 in polynomial time.

Thoughts: Pseudo Random number generators are extremely important for cryptographic applications since such functions often cannot wait for a true random number generator to provide enough randomness for each bit requested. Therefore, a true RNG can act as a seed to a PRNG to provide a statistically random sequence. This assumes however, that the PRNG sequence appears random and independent without knowledge of the seed. For our purposes, PRNG’s are important in that we must find entropy sources that can generate a seed for such a generator.