different configuration of the "same" system may always provide the
same lower bits and only count in the upper bits at much lower
resolution. This means that successive reads of the clock may
produce identical values even if enough time has passed that the
value "should" change based on the nominal clock resolution. There
are also cases where frequently reading a clock can produce
artificial sequential values, because of extra code that checks for
the clock being unchanged between two reads and increases it by one!
Designing portable application code to generate unpredictable numbers
based on such system clocks is particularly challenging because the
system designer does not always know the properties of the system
clock.
Use of a hardware serial number (such as an Ethernet MAC address) may
also provide fewer bits of uniqueness than one would guess. Such
quantities are usually heavily structured, and subfields may have
only a limited range of possible values, or values may be easily
guessable based on approximate date of manufacture or other data.
For example, it is likely that a company that manufactures both
computers and Ethernet adapters will, at least internally, use its
own adapters, which significantly limits the range of built-in
addresses.
Problems such as those described above make the production of code to
generate unpredictable quantities difficult if the code is to be
ported across a variety of computer platforms and systems.
3.5. Timing and Value of External Events
It is possible to measure the timing and content of mouse movement,
key strokes, and similar user events. This is a reasonable source of
unguessable data, with some qualifications. On some machines, input
such as key strokes is buffered. Even though the user’s inter-
keystroke timing may have sufficient variation and unpredictability,
there might not be an easy way to access that variation. Another
problem is that no standard method exists for sampling timing
details. This makes it hard to use this technique to build standard
software intended for distribution to a large range of machines.
The amount of mouse movement and the actual key strokes are usually
easier to access than timings, but they may yield less
unpredictability because the user may provide highly repetitive
input.
Other external events, such as network packet arrival times and
lengths, can also be used, but only with great care. In particular,
the possibility of manipulation of such network traffic measurements
by an adversary and the lack of history at system start-up must be
carefully considered. If this input is subject to manipulation, it
must not be trusted as a source of entropy.
In principle, almost any external sensor, such as raw radio reception
or temperature sensing in appropriately equipped computers, can be
used. But in each case, careful consideration must be given to how
much this data is subject to adversarial manipulation and to how much
entropy it can actually provide.
The above techniques are quite powerful against attackers that have
no access to the quantities being measured. For example, these
techniques would be powerful against offline attackers who had no
access to one’s environment and who were trying to crack one’s random
seed after the fact. In all cases, the more accurately one can
measure the timing or value of an external sensor, the more rapidly
one can generate bits.
3.6. Non-hardware Sources of Randomness
The best source of input entropy would be a hardware-based random
source such as ring oscillators, disk drive timing, thermal noise, or
radioactive decay. However, if none of these is available, there are
other possibilities. These include system clocks, system or
input/output buffers, user/system/hardware/network serial numbers or
addresses and timing, and user input. Unfortunately, each of these
sources can produce very limited or predictable values under some
circumstances.
Some of the sources listed above would be quite strong on multi-user
systems, where each user of the system is in essence a source of
randomness. However, on a small single-user or embedded system,
especially at start-up, it might be possible for an adversary to
assemble a similar configuration. This could give the adversary
inputs to the mixing process that were well-enough correlated to
those used originally to make exhaustive search practical.
The use of multiple random inputs with a strong mixing function is
recommended and can overcome weakness in any particular input. The
timing and content of requested "random" user keystrokes can yield
hundreds of random bits, but conservative assumptions need to be
made. For example, one reasonably conservative assumption would be
that an inter-keystroke interval provides at most a few bits of
randomness, but only when the interval is unique in the sequence of
intervals up to that point. A similar assumption would be that a key
code provides a few bits of randomness, but only when the code is
unique in the sequence. Thus, an interval or key code that
duplicated a previous value would be assumed to provide no additional
randomness. The results of mixing these timings with typed
characters could be further combined with clock values and other
inputs.
This strategy may make practical portable code for producing good
random numbers for security, even if some of the inputs are very weak
on some of the target systems. However, it may still fail against a
high-grade attack on small, single-user, or embedded systems,
especially if the adversary has ever been able to observe the
generation process in the past. A hardware-based random source is
still preferable.
4. De-skewing
Is there any specific requirement on the shape of the distribution of
quantities gathered for the entropy to produce the random numbers?
The good news is that the distribution need not be uniform. All that
is needed to bound performance is a conservative estimate of how
non-uniform it is. Simple techniques to de-skew a bit stream are
given below, and stronger cryptographic techniques are described in
Section 5.2.
4.1. Using Stream Parity to De-Skew
As a simple but not particularly practical example, consider taking a
sufficiently long string of bits and mapping the string to "zero" or
"one". The mapping will not yield a perfectly uniform distribution,
but it can be as close as desired. One mapping that serves the
purpose is to take the parity of the string. This has the advantages
that it is robust across all degrees of skew up to the estimated
maximum skew and that it is trivial to implement in hardware.
The following analysis gives the number of bits that must be sampled:
Suppose that the ratio of ones to zeros is ( 0.5 + E ) to
( 0.5 - E ), where E is between 0 and 0.5 and is a measure of the
"eccentricity" of the distribution. Consider the distribution of the
parity function of N bit samples. The respective probabilities that
the parity will be one or zero will be the sum of the odd or even
terms in the binomial expansion of (p + q)^N, where p = 0.5 + E, the
probability of a one, and q = 0.5 - E, the probability of a zero.
These sums can be computed easily as
N N
1/2 * ( ( p + q ) + ( p - q ) )
and
N N
1/2 * ( ( p + q ) - ( p - q ) ).
(Which formula corresponds to the probability that the parity will be
1 depends on whether N is odd or even.)
Since p + q = 1 and p - q = 2E, these expressions reduce to
N
1/2 * [1 + (2E) ]
and
N
1/2 * [1 - (2E) ].
Neither of these will ever be exactly 0.5 unless E is zero, but we
can bring them arbitrarily close to 0.5. If we want the
probabilities to be within some delta d of 0.5, e.g., then
N
( 0.5 + ( 0.5 * (2E) ) ) < 0.5 + d.
Solving for N yields N > log(2d)/log(2E). (Note that 2E is less than
1, so its log is negative. Division by a negative number reverses
the sense of an inequality.)
The following table gives the length N of the string that must be
sampled for various degrees of skew in order to come within 0.001 of
a 50/50 distribution.
+---------+--------+-------+
| Prob(1) | E | N |
+---------+--------+-------+
| 0.5 | 0.00 | 1 |
| 0.6 | 0.10 | 4 |
| 0.7 | 0.20 | 7 |
| 0.8 | 0.30 | 13 |
| 0.9 | 0.40 | 28 |
| 0.95 | 0.45 | 59 |
| 0.99 | 0.49 | 308 |
+---------+--------+-------+
The last entry shows that even if the distribution is skewed 99% in
favor of ones, the parity of a string of 308 samples will be within
0.001 of a 50/50 distribution. But, as we shall see in section 5.2,
there are much stronger techniques that extract more of the available
entropy.
4.2. Using Transition Mappings to De-Skew
Another technique, originally due to von Neumann [VON_NEUMANN], is to
examine a bit stream as a sequence of non-overlapping pairs. One
could then discard any 00 or 11 pairs found, interpret 01 as a 0 and
10 as a 1. Assume that the probability of a 1 is 0.5+E and that the
probability of a 0 is 0.5-E, where E is the eccentricity of the
source as described in the previous section. Then the probability of
each pair is shown in the following table:
+------+-----------------------------------------+
| pair | probability |
+------+-----------------------------------------+
| 00 | (0.5 - E)^2 = 0.25 - E + E^2 |
| 01 | (0.5 - E)*(0.5 + E) = 0.25 - E^2 |
| 10 | (0.5 + E)*(0.5 - E) = 0.25 - E^2 |
| 11 | (0.5 + E)^2 = 0.25 + E + E^2 |
+------+-----------------------------------------+
This technique will completely eliminate any bias but requires an
indeterminate number of input bits for any particular desired number
of output bits. The probability of any particular pair being
discarded is 0.5 + 2E^2, so the expected number of input bits to
produce X output bits is X/(0.25 - E^2).
This technique assumes that the bits are from a stream where each bit
has the same probability of being a 0 or 1 as any other bit in the
stream and that bits are uncorrelated, i.e., that the bits come from
identical independent distributions. If alternate bits are from two
correlated sources, for example, the above analysis breaks down.
The above technique also provides another illustration of how a
simple statistical analysis can mislead if one is not always on the
lookout for patterns that could be exploited by an adversary. If the
algorithm were misread slightly so that overlapping successive bits
pairs were used instead of non-overlapping pairs, the statistical
analysis given would be the same. However, instead of providing an
unbiased, uncorrelated series of random 1s and 0s, it would produce a
totally predictable sequence of exactly alternating 1s and 0s.
4.3. Using FFT to De-Skew
When real-world data consists of strongly correlated bits, it may
still contain useful amounts of entropy. This entropy can be
extracted through various transforms, the most powerful of which are
described in section 5.2 below.
Using the Fourier transform of the data or its optimized variant, the
FFT, is interesting primarily for theoretical reasons. It can be
shown that this technique will discard strong correlations. If
adequate data is processed and if remaining correlations decay,
spectral lines that approach statistical independence and normally
distributed randomness can be produced [BRILLINGER].
4.4. Using Compression to De-Skew
Reversible compression techniques also provide a crude method of de-
skewing a skewed bit stream. This follows directly from the
definition of reversible compression and the formula in Section 2 for
the amount of information in a sequence. Since the compression is
reversible, the same amount of information must be present in the
shorter output as was present in the longer input. By the Shannon
information equation, this is only possible if, on average, the
probabilities of the different shorter sequences are more uniformly
distributed than were the probabilities of the longer sequences.
Therefore, the shorter sequences must be de-skewed relative to the
input.
However, many compression techniques add a somewhat predictable
preface to their output stream and may insert a similar sequence
periodically in their output or otherwise introduce subtle patterns
of their own. They should be considered only rough techniques
compared to those described in Section 5.2. At a minimum, the
beginning of the compressed sequence should be skipped and only later
bits should used for applications requiring roughly-random bits.
5. Mixing
What is the best overall strategy for obtaining unguessable random
numbers in the absence of a strong, reliable hardware entropy source?
It is to obtain input from a number of uncorrelated sources and to
mix them with a strong mixing function. Such a function will
preserve the entropy present in any of the sources, even if other
quantities being combined happen to be fixed or easily guessable (low
entropy). This approach may be advisable even with a good hardware
source, as hardware can also fail. However, this should be weighed
against a possible increase in the chance of overall failure due to
added software complexity.
Once one has used good sources, such as some of those listed in
Section 3, and mixed them as described in this section, one has a
strong seed. This can then be used to produce large quantities of
cryptographically strong material as described in Sections 6 and 7.
A strong mixing function is one that combines inputs and produces an
output in which each output bit is a different complex non-linear
function of all the input bits. On average, changing any input bit
will change about half the output bits. But because the relationship
is complex and non-linear, no particular output bit is guaranteed to
change when any particular input bit is changed.
Consider the problem of converting a stream of bits that is skewed
towards 0 or 1 or which has a somewhat predictable pattern to a
shorter stream which is more random, as discussed in Section 4. This
is simply another case where a strong mixing function is desired, to
mix the input bits and produce a smaller number of output bits. The
technique given in Section 4.1, using the parity of a number of bits,
is simply the result of successively XORing them. This is examined
as a trivial mixing function, immediately below. Use of stronger
mixing functions to extract more of the randomness in a stream of
skewed bits is examined in Section 5.2. See also [NASLUND].
5.1. A Trivial Mixing Function
For expository purposes we describe a trivial example for single bit
inputs using the Exclusive Or (XOR) function. This function is
equivalent to addition without carry, as show in the table below.
This is a degenerate case in which the one output bit always changes
for a change in either input bit. But, despite its simplicity, it
provides a useful illustration.
+-----------+-----------+----------+
| input 1 | input 2 | output |
+-----------+-----------+----------+
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
+-----------+-----------+----------+
If inputs 1 and 2 are uncorrelated and combined in this fashion, then
the output will be an even better (less skewed) random bit than the
inputs are. If we assume an "eccentricity" E as defined in Section
4.1 above, then the output eccentricity relates to the input
eccentricity as follows:
E = 2 * E * E
output input 1 input 2
Since E is never greater than 1/2, the eccentricity is always
improved, except in the case in which at least one input is a totally
skewed constant. This is illustrated in the following table, where
the top and left side values are the two input eccentricities and the
entries are the output eccentricity:
+--------+--------+--------+--------+--------+--------+--------+
| E | 0.00 | 0.10 | 0.20 | 0.30 | 0.40 | 0.50 |
+--------+--------+--------+--------+--------+--------+--------+
| 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
| 0.10 | 0.00 | 0.02 | 0.04 | 0.06 | 0.08 | 0.10 |
| 0.20 | 0.00 | 0.04 | 0.08 | 0.12 | 0.16 | 0.20 |
| 0.30 | 0.00 | 0.06 | 0.12 | 0.18 | 0.24 | 0.30 |
| 0.40 | 0.00 | 0.08 | 0.16 | 0.24 | 0.32 | 0.40 |
| 0.50 | 0.00 | 0.10 | 0.20 | 0.30 | 0.40 | 0.50 |
+--------+--------+--------+--------+--------+--------+--------+
However, note that the above calculations assume that the inputs are
not correlated. If the inputs were, say, the parity of the number of
minutes from midnight on two clocks accurate to a few seconds, then
each might appear random if sampled at random intervals much longer
than a minute. Yet if they were both sampled and combined with XOR,
the result would be zero most of the time.
5.2. Stronger Mixing Functions
The US Government Advanced Encryption Standard [AES] is an example of
a strong mixing function for multiple bit quantities. It takes up to
384 bits of input (128 bits of "data" and 256 bits of "key") and
produces 128 bits of output, each of which is dependent on a complex
non-linear function of all input bits. Other encryption functions
with this characteristic, such as [DES], can also be used by
considering them to mix all of their key and data input bits.
Another good family of mixing functions is the "message digest" or
hashing functions such as the US Government Secure Hash Standards
[SHA*] and the MD4, MD5 [MD4, MD5] series. These functions all take
a practically unlimited amount of input and produce a relatively
short fixed-length output mixing all the input bits. The MD* series
produces 128 bits of output, SHA-1 produces 160 bits, and other SHA
functions produce up to 512 bits.
Although the message digest functions are designed for variable
amounts of input, AES and other encryption functions can also be used
to combine any number of inputs. If 128 bits of output is adequate,
the inputs can be packed into a 128-bit data quantity and successive
AES "keys", padding with zeros if needed; the quantity is then
successively encrypted by the "keys" using AES in Electronic Codebook
Mode. Alternatively, the input could be packed into one 128-bit key
and multiple data blocks and a CBC-MAC could be calculated [MODES].
More complex mixing should be used if more than 128 bits of output
are needed and one wants to employ AES (but note that it is
absolutely impossible to get more bits of "randomness" out than are
put in). For example, suppose that inputs are packed into three
quantities, A, B, and C. One may use AES to encrypt A with B and
then with C as keys to produce the first part of the output, then
encrypt B with C and then A for more output and, if necessary,
encrypt C with A and then B for yet more output. Still more output
can be produced by reversing the order of the keys given above. The
same can be done with the hash functions, hashing various subsets of
the input data or different copies of the input data with different
prefixes and/or suffixes to produce multiple outputs.
For an example of using a strong mixing function, reconsider the case
of a string of 308 bits, each of which is biased 99% toward zero.
The parity technique given in Section 4.1 reduces this to one bit,
with only a 1/1000 deviance from being equally likely a zero or one.
But, applying the equation for information given in Section 2, this
308-bit skewed sequence contains over 5 bits of information. Thus,
hashing it with SHA-1 and taking the bottom 5 bits of the result
would yield 5 unbiased random bits and not the single bit given by
calculating the parity of the string. Alternatively, for some
applications, you could use the entire hash output to retain almost
all of the 5+ bits of entropy in a 160-bit quantity.
5.3. Using S-Boxes for Mixing
Many modern block encryption functions, including DES and AES,
incorporate modules known as S-Boxes (substitution boxes). These
produce a smaller number of outputs from a larger number of inputs
through a complex non-linear mixing function that has the effect of
concentrating limited entropy from the inputs into the output.
S-Boxes sometimes incorporate bent Boolean functions (functions of an
even number of bits producing one output bit with maximum non-
linearity). Looking at the output for all input pairs differing in
any particular bit position, exactly half the outputs are different.
An S-Box in which each output bit is produced by a bent function such
that any linear combination of these functions is also a bent
function is called a "perfect S-Box".
S-boxes and various repeated applications or cascades of such boxes
can be used for mixing [SBOX1, SBOX2].
5.4. Diffie-Hellman as a Mixing Function
Diffie-Hellman exponential key exchange is a technique that yields a
shared secret between two parties. It can be computationally
infeasible for a third party to determine this secret even if they
can observe all the messages between the two communicating parties.
This shared secret is a mixture of initial quantities generated by
each of the parties [D-H].
If these initial quantities are random and uncorrelated, then the
shared secret combines their entropy but, of course, can not produce
more randomness than the size of the shared secret generated.
Although this is true if the Diffie-Hellman computation is performed