Network Working Group D. Eastlake, 3rd
Request for Comments: 4086 Motorola Laboratories
BCP: 106 J. Schiller
Obsoletes: 1750 MIT
Category: Best Current Practice S. CrockerJune 2005 Randomness Requirements for Security
Status of This Memo
This document specifies an Internet Best Current Practices for the
Internet Community, and requests discussion and suggestions for
improvements. Distribution of this memo is unlimited.
Copyright (C) The Internet Society (2005).
Security systems are built on strong cryptographic algorithms that
foil pattern analysis attempts. However, the security of these
systems is dependent on generating secret quantities for passwords,
cryptographic keys, and similar quantities. The use of pseudo-random
processes to generate secret quantities can result in pseudo-
security. A sophisticated attacker may find it easier to reproduce
the environment that produced the secret quantities and to search the
resulting small set of possibilities than to locate the quantities in
the whole of the potential number space.
Choosing random quantities to foil a resourceful and motivated
adversary is surprisingly difficult. This document points out many
pitfalls in using poor entropy sources or traditional pseudo-random
number generation techniques for generating such quantities. It
recommends the use of truly random hardware techniques and shows that
the existing hardware on many systems can be used for this purpose.
It provides suggestions to ameliorate the problem when a hardware
solution is not available, and it gives examples of how large such
quantities need to be for some applications.
Table of Contents
1. Introduction and Overview .......................................32. General Requirements ............................................43. Entropy Sources .................................................73.1. Volume Required ............................................73.2. Existing Hardware Can Be Used For Randomness ...............83.2.1. Using Existing Sound/Video Input ....................83.2.2. Using Existing Disk Drives ..........................83.3. Ring Oscillator Sources ....................................93.4. Problems with Clocks and Serial Numbers ...................103.5. Timing and Value of External Events .......................113.6. Non-hardware Sources of Randomness ........................124. De-skewing .....................................................124.1. Using Stream Parity to De-Skew ............................134.2. Using Transition Mappings to De-Skew ......................144.3. Using FFT to De-Skew ......................................154.4. Using Compression to De-Skew ..............................155. Mixing .........................................................165.1. A Trivial Mixing Function .................................175.2. Stronger Mixing Functions .................................185.3. Using S-Boxes for Mixing ..................................195.4. Diffie-Hellman as a Mixing Function .......................195.5. Using a Mixing Function to Stretch Random Bits ............205.6. Other Factors in Choosing a Mixing Function ...............206. Pseudo-random Number Generators ................................216.1. Some Bad Ideas ............................................216.1.1. The Fallacy of Complex Manipulation ................216.1.2. The Fallacy of Selection from a Large Database .....226.1.3. Traditional Pseudo-random Sequences ................236.2. Cryptographically Strong Sequences ........................246.2.1. OFB and CTR Sequences ..............................256.2.2. The Blum Blum Shub Sequence Generator ..............266.3. Entropy Pool Techniques ...................................277. Randomness Generation Examples and Standards ...................287.1. Complete Randomness Generators ............................287.1.1. US DoD Recommendations for Password Generation .....287.1.2. The /dev/random Device .............................297.1.3. Windows CryptGenRandom .............................307.2. Generators Assuming a Source of Entropy ...................317.2.1. X9.82 Pseudo-Random Number Generation ..............317.2.2. X9.17 Key Generation ...............................337.2.3. DSS Pseudo-random Number Generation ................348. Examples of Randomness Required ................................348.1. Password Generation .......................................358.2. A Very High Security Cryptographic Key ....................369. Conclusion .....................................................3810. Security Considerations ........................................38
11. Acknowledgments ................................................39
Appendix A: Changes from RFC 1750 ..................................40
Informative References .............................................411. Introduction and Overview
Software cryptography is coming into wider use, although there is a
long way to go until it becomes pervasive. Systems such as SSH,
IPSEC, TLS, S/MIME, PGP, DNSSEC, and Kerberos are maturing and
becoming a part of the network landscape [SSH] [IPSEC] [TLS] [S/MIME]
[MAIL_PGP*] [DNSSEC*]. For comparison, when the previous version of
this document [RFC1750] was issued in 1994, the only Internet
cryptographic security specification in the IETF was the Privacy
Enhanced Mail protocol [MAIL_PEM*].
These systems provide substantial protection against snooping and
spoofing. However, there is a potential flaw. At the heart of all
cryptographic systems is the generation of secret, unguessable (i.e.,
The lack of generally available facilities for generating such random
numbers (that is, the lack of general availability of truly
unpredictable sources) forms an open wound in the design of
cryptographic software. For the software developer who wants to
build a key or password generation procedure that runs on a wide
range of hardware, this is a very real problem.
Note that the requirement is for data that an adversary has a very
low probability of guessing or determining. This can easily fail if
pseudo-random data is used that meets only traditional statistical
tests for randomness, or that is based on limited-range sources such
as clocks. Sometimes such pseudo-random quantities can be guessed by
an adversary searching through an embarrassingly small space of
This Best Current Practice document describes techniques for
producing random quantities that will be resistant to attack. It
recommends that future systems include hardware random number
generation or provide access to existing hardware that can be used
for this purpose. It suggests methods for use if such hardware is
not available, and it gives some estimates of the number of random
bits required for sample applications.
2. General Requirements
Today, a commonly encountered randomness requirement is to pick a
user password, usually a simple character string. Obviously, a
password that can be guessed does not provide security. For re-
usable passwords, it is desirable that users be able to remember the
password. This may make it advisable to use pronounceable character
strings or phrases composed of ordinary words. But this affects only
the format of the password information, not the requirement that the
password be very hard to guess.
Many other requirements come from the cryptographic arena.
Cryptographic techniques can be used to provide a variety of
services, including confidentiality and authentication. Such
services are based on quantities, traditionally called "keys", that
are unknown to and unguessable by an adversary.
There are even TCP/IP protocol uses for randomness in picking initial
sequence numbers [RFC1948].
Generally speaking, the above examples also illustrate two different
types of random quantities that may be wanted. In the case of
human-usable passwords, the only important characteristic is that
they be unguessable. It is not important that they may be composed
of ASCII characters, so the top bit of every byte is zero, for
example. On the other hand, for fixed length keys and the like, one
normally wants quantities that appear to be truly random, that is,
quantities whose bits will pass statistical randomness tests.
In some cases, such as the use of symmetric encryption with the one-
time pads or an algorithm like the US Advanced Encryption Standard
[AES], the parties who wish to communicate confidentially and/or with
authentication must all know the same secret key. In other cases,
where asymmetric or "public key" cryptographic techniques are used,
keys come in pairs. One key of the pair is private and must be kept
secret by one party; the other is public and can be published to the
world. It is computationally infeasible to determine the private key
from the public key, and knowledge of the public key is of no help to
an adversary [ASYMMETRIC]. See general references [SCHNEIER,
The frequency and volume of the requirement for random quantities
differs greatly for different cryptographic systems. With pure RSA,
random quantities are required only when a new key pair is generated;
thereafter, any number of messages can be signed without a further
need for randomness. The public key Digital Signature Algorithm
devised by the US National Institute of Standards and Technology
(NIST) requires good random numbers for each signature [DSS]. And
encrypting with a one-time pad (in principle the strongest possible
encryption technique) requires randomness of equal volume to all the
messages to be processed. See general references [SCHNEIER,
In most of these cases, an adversary can try to determine the
"secret" key by trial and error. This is possible as long as the key
is enough smaller than the message that the correct key can be
uniquely identified. The probability of an adversary succeeding at
this must be made acceptably low, depending on the particular
application. The size of the space the adversary must search is
related to the amount of key "information" present, in an
information-theoretic sense [SHANNON]. This depends on the number of
different secret values possible and the probability of each value,
Bits of information = \ - p * log ( p )
/ i 2 i
where i counts from 1 to the number of possible secret values and p
sub i is the probability of the value numbered i. (Because p sub i
is less than one, the log will be negative, so each term in the sum
will be non-negative.)
If there are 2^n different values of equal probability, then n bits
of information are present and an adversary would have to try, on the
average, half of the values, or 2^(n-1), before guessing the secret
quantity. If the probability of different values is unequal, then
there is less information present, and fewer guesses will, on
average, be required by an adversary. In particular, any values that
an adversary can know to be impossible or of low probability can be
initially ignored by the adversary, who will search through the more
probable values first.
For example, consider a cryptographic system that uses 128-bit keys.
If these keys are derived using a fixed pseudo-random number
generator that is seeded with an 8-bit seed, then an adversary needs
to search through only 256 keys (by running the pseudo-random number
generator with every possible seed), not 2^128 keys as may at first
appear to be the case. Only 8 bits of "information" are in these
While the above analysis is correct on average, it can be misleading
in some cases for cryptographic analysis where what is really
important is the work factor for an adversary. For example, assume
that there is a pseudo-random number generator generating 128-bit
keys, as in the previous paragraph, but that it generates zero half
of the time and a random selection from the remaining 2^128 - 1
values the rest of the time. The Shannon equation above says that
there are 64 bits of information in one of these key values, but an
adversary, simply by trying the value zero, can break the security of
half of the uses, albeit a random half. Thus, for cryptographic
purposes, it is also useful to look at other measures, such as min-
entropy, defined as
Min-entropy = - log ( maximum ( p ) )
where i is as above. Using this equation, we get 1 bit of min-
entropy for our new hypothetical distribution, as opposed to 64 bits
of classical Shannon entropy.
A continuous spectrum of entropies, sometimes called Renyi entropy,
has been defined, specified by the parameter r. Here r = 1 is
Shannon entropy and r = infinity is min-entropy. When r = zero, it
is just log (n), where n is the number of non-zero probabilities.
Renyi entropy is a non-increasing function of r, so min-entropy is
always the most conservative measure of entropy and usually the best
to use for cryptographic evaluation [LUBY].
Statistically tested randomness in the traditional sense is NOT the
same as the unpredictability required for security use.
For example, the use of a widely available constant sequence, such as
the random table from the CRC Standard Mathematical Tables, is very
weak against an adversary. An adversary who learns of or guesses it
can easily break all security, future and past, based on the sequence
[CRC]. As another example, using AES with a constant key to encrypt
successive integers such as 1, 2, 3, ... will produce output that
also has excellent statistical randomness properties but is
predictable. On the other hand, taking successive rolls of a six-
sided die and encoding the resulting values in ASCII would produce
statistically poor output with a substantial unpredictable component.
So note that passing or failing statistical tests doesn't reveal
whether something is unpredictable or predictable.
3. Entropy Sources
Entropy sources tend to be very implementation dependent. Once one
has gathered sufficient entropy, it can be used as the seed to
produce the required amount of cryptographically strong pseudo-
randomness, as described in Sections 6 and 7, after being de-skewed
or mixed as necessary, as described in Sections 4 and 5.
Is there any hope for true, strong, portable randomness in the
future? There might be. All that's needed is a physical source of
Thermal noise (sometimes called Johnson noise in integrated circuits)
or a radioactive decay source and a fast, free-running oscillator
would do the trick directly [GIFFORD]. This is a trivial amount of
hardware, and it could easily be included as a standard part of a
computer system's architecture. Most audio (or video) input devices
are usable [TURBID]. Furthermore, any system with a spinning disk or
ring oscillator and a stable (crystal) time source or the like has an
adequate source of randomness ([DAVIS] and Section 3.3). All that's
needed is the common perception among computer vendors that this
small additional hardware and the software to access it is necessary
ANSI X9 is currently developing a standard that includes a part
devoted to entropy sources. See Part 2 of [X9.82].
3.1. Volume Required
How much unpredictability is needed? Is it possible to quantify the
requirement in terms of, say, number of random bits per second?
The answer is that not very much is needed. For AES, the key can be
128 bits, and, as we show in an example in Section 8, even the
highest security system is unlikely to require strong keying material
of much over 200 bits. If a series of keys is needed, they can be
generated from a strong random seed (starting value) using a
cryptographically strong sequence, as explained in Section 6.2. A
few hundred random bits generated at start-up or once a day is enough
if such techniques are used. Even if the random bits are generated
as slowly as one per second and it is not possible to overlap the
generation process, it should be tolerable in most high-security
applications to wait 200 seconds occasionally.
These numbers are trivial to achieve. It could be achieved by a
person repeatedly tossing a coin, and almost any hardware based
process is likely to be much faster.
3.2. Existing Hardware Can Be Used For Randomness
As described below, many computers come with hardware that can, with
care, be used to generate truly random quantities.
3.2.1. Using Existing Sound/Video Input
Many computers are built with inputs that digitize some real-world
analog source, such as sound from a microphone or video input from a
camera. The "input" from a sound digitizer with no source plugged in
or from a camera with the lens cap on is essentially thermal noise.
If the system has enough gain to detect anything, such input can
provide reasonably high quality random bits. This method is
extremely dependent on the hardware implementation.
For example, on some UNIX-based systems, one can read from the
/dev/audio device with nothing plugged into the microphone jack or
with the microphone receiving only low level background noise. Such
data is essentially random noise, although it should not be trusted
without some checking, in case of hardware failure, and it will have
to be de-skewed.
Combining this approach with compression to de-skew (see Section 4),
one can generate a huge amount of medium-quality random data with the
UNIX-style command line:
cat /dev/audio | compress - >random-bits-file
A detailed examination of this type of randomness source appears in
3.2.2. Using Existing Disk Drives
Disk drives have small random fluctuations in their rotational speed
due to chaotic air turbulence [DAVIS, Jakobsson]. The addition of
low-level disk seek-time instrumentation produces a series of
measurements that contain this randomness. Such data is usually
highly correlated, so significant processing is needed, as described
in Section 5.2 below. Nevertheless, experimentation a decade ago
showed that, with such processing, even slow disk drives on the
slower computers of that day could easily produce 100 bits a minute
or more of excellent random data.
Every increase in processor speed, which increases the resolution
with which disk motion can be timed or increases the rate of disk
seeks, increases the rate of random bit generation possible with this
technique. At the time of this paper and with modern hardware, a
more typical rate of random bit production would be in excess of
10,000 bits a second. This technique is used in random number
generators included in many operating system libraries.
Note: the inclusion of cache memories in disk controllers has little
effect on this technique if very short seek times, which represent
cache hits, are simply ignored.
3.3. Ring Oscillator Sources
If an integrated circuit is being designed or field-programmed, an
odd number of gates can be connected in series to produce a free-
running ring oscillator. By sampling a point in the ring at a fixed
frequency (for example, one determined by a stable crystal
oscillator), some amount of entropy can be extracted due to
variations in the free-running oscillator timing. It is possible to
increase the rate of entropy by XOR'ing sampled values from a few
ring oscillators with relatively prime lengths. It is sometimes
recommended that an odd number of rings be used so that, even if the
rings somehow become synchronously locked to each other, there will
still be sampled bit transitions. Another possible source to sample
is the output of a noisy diode.
Sampled bits from such sources will have to be heavily de-skewed, as
disk rotation timings must be (see Section 4). An engineering study
would be needed to determine the amount of entropy being produced
depending on the particular design. In any case, these can be good
sources whose cost is a trivial amount of hardware by modern
As an example, IEEE 802.11i suggests the circuit below, with due
attention in the design to isolation of the rings from each other and
from clocked circuits to avoid undesired synchronization, etc., and
with extensive post processing [IEEE_802.11i].
|\ |\ |\
+-->| >0-->| >0-- 19 total --| >0--+-------+
| |/ |/ |/ | |
| | |
|\ |\ |\ | | output
+-->| >0-->| >0-- 23 total --| >0--+--->| XOR |------>
| |/ |/ |/ | | |
| | +-----+
+----------------------------------+ ^ ^
|\ |\ |\ | |
+-->| >0-->| >0-- 29 total --| >0--+------+ |
| |/ |/ |/ | |
| | |
Other randomness, if available ---------+
3.4. Problems with Clocks and Serial Numbers
Computer clocks and similar operating system or hardware values,
provide significantly fewer real bits of unpredictability than might
appear from their specifications.
Tests have been done on clocks on numerous systems, and it was found
that their behavior can vary widely and in unexpected ways. One
version of an operating system running on one set of hardware may
actually provide, say, microsecond resolution in a clock, while a
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
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
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
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
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
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
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
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
1/2 * ( ( p + q ) + ( p - q ) )
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
1/2 * [1 + (2E) ]
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
( 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
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
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.
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
privately, an adversary who can observe either of the public keys and
knows the modulus being used need only search through the space of
the other secret key in order to be able to calculate the shared
secret [D-H]. So, conservatively, it would be best to consider
public Diffie-Hellman to produce a quantity whose guessability
corresponds to the worse of the two inputs. Because of this and the
fact that Diffie-Hellman is computationally intensive, its use as a
mixing function is not recommended.
5.5. Using a Mixing Function to Stretch Random Bits
Although it is not necessary for a mixing function to produce the
same or fewer output bits than its inputs, mixing bits cannot
"stretch" the amount of random unpredictability present in the
inputs. Thus, four inputs of 32 bits each, in which there are 12
bits worth of unpredictability (such as 4,096 equally probable
values) in each input, cannot produce more than 48 bits worth of
unpredictable output. The output can be expanded to hundreds or
thousands of bits by, for example, mixing with successive integers,
but the clever adversary's search space is still 2^48 possibilities.
Furthermore, mixing to fewer bits than are input will tend to
strengthen the randomness of the output.
The last table in Section 5.1 shows that mixing a random bit with a
constant bit with Exclusive Or will produce a random bit. While this
is true, it does not provide a way to "stretch" one random bit into
more than one. If, for example, a random bit is mixed with a 0 and
then with a 1, this produces a two bit sequence but it will always be
either 01 or 10. Since there are only two possible values, there is
still only the one bit of original randomness.
5.6. Other Factors in Choosing a Mixing Function
For local use, AES has the advantages that it has been widely tested
for flaws, is reasonably efficient in software, and is widely
documented and implemented with hardware and software implementations
available all over the world including open source code. The SHA*
family have had a little less study and tend to require more CPU
cycles than AES but there is no reason to believe they are flawed.
Both SHA* and MD5 were derived from the earlier MD4 algorithm. They
all have source code available [SHA*, MD4, MD5]. Some signs of
weakness have been found in MD4 and MD5. In particular, MD4 has only
three rounds and there are several independent breaks of the first
two or last two rounds. And some collisions have been found in MD5
AES was selected by a robust, public, and international process. It
and SHA* have been vouched for by the US National Security Agency
(NSA) on the basis of criteria that mostly remain secret, as was DES.
While this has been the cause of much speculation and doubt,
investigation of DES over the years has indicated that NSA
involvement in modifications to its design, which originated with
IBM, was primarily to strengthen it. There has been no announcement
of a concealed or special weakness being found in DES. It is likely
that the NSA modifications to MD4 to produce the SHA algorithms
similarly strengthened these algorithms, possibly against threats not
yet known in the public cryptographic community.
Where input lengths are unpredictable, hash algorithms are more
convenient to use than block encryption algorithms since they are
generally designed to accept variable length inputs. Block
encryption algorithms generally require an additional padding
algorithm to accommodate inputs that are not an even multiple of the
As of the time of this document, the authors know of no patent claims
to the basic AES, DES, SHA*, MD4, and MD5 algorithms other than
patents for which an irrevocable royalty free license has been
granted to the world. There may, of course, be essential patents of
which the authors are unaware or patents on implementations or uses
or other relevant patents issued or to be issued.