Request for Comments: 4086 Motorola Laboratories
BCP: 106 J. Schiller
Obsoletes: 1750 MIT
Category: Best Current Practice S. Crocker
June 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 Notice
Copyright (C) The Internet Society (2005).
Abstract
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 .......................................3
2. General Requirements ............................................4
3. Entropy Sources .................................................7
3.1. Volume Required ............................................7
3.2. Existing Hardware Can Be Used For Randomness ...............8
3.2.1. Using Existing Sound/Video Input ....................8
3.2.2. Using Existing Disk Drives ..........................8
3.3. Ring Oscillator Sources ....................................9
3.4. Problems with Clocks and Serial Numbers ...................10
3.5. Timing and Value of External Events .......................11
3.6. Non-hardware Sources of Randomness ........................12
4. De-skewing .....................................................12
4.1. Using Stream Parity to De-Skew ............................13
4.2. Using Transition Mappings to De-Skew ......................14
4.3. Using FFT to De-Skew ......................................15
4.4. Using Compression to De-Skew ..............................15
5. Mixing .........................................................16
5.1. A Trivial Mixing Function .................................17
5.2. Stronger Mixing Functions .................................18
5.3. Using S-Boxes for Mixing ..................................19
5.4. Diffie-Hellman as a Mixing Function .......................19
5.5. Using a Mixing Function to Stretch Random Bits ............20
5.6. Other Factors in Choosing a Mixing Function ...............20
6. Pseudo-random Number Generators ................................21
6.1. Some Bad Ideas ............................................21
6.1.1. The Fallacy of Complex Manipulation ................21
6.1.2. The Fallacy of Selection from a Large Database .....22
6.1.3. Traditional Pseudo-random Sequences ................23
6.2. Cryptographically Strong Sequences ........................24
6.2.1. OFB and CTR Sequences ..............................25
6.2.2. The Blum Blum Shub Sequence Generator ..............26
6.3. Entropy Pool Techniques ...................................27
7. Randomness Generation Examples and Standards ...................28
7.1. Complete Randomness Generators ............................28
7.1.1. US DoD Recommendations for Password Generation .....28
7.1.2. The /dev/random Device .............................29
7.1.3. Windows CryptGenRandom .............................30
7.2. Generators Assuming a Source of Entropy ...................31
7.2.1. X9.82 Pseudo-Random Number Generation ..............31
7.2.2. X9.17 Key Generation ...............................33
7.2.3. DSS Pseudo-random Number Generation ................34
8. Examples of Randomness Required ................................34
8.1. Password Generation .......................................35
8.2. A Very High Security Cryptographic Key ....................36
9. Conclusion .....................................................38
10. Security Considerations ........................................38
11. Acknowledgments ................................................39
Appendix A: Changes from RFC 1750 ..................................40
Informative References .............................................41
1. 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.,
random) numbers.
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
possibilities.
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,
FERGUSON, KAUFMAN].
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,
FERGUSON, KAUFMAN].
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,
as follows:
-----
\
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
128-bit keys.
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 ) )
i
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
unpredictable numbers.
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
and useful.
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
[TURBID].
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
standards.
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--+-------+
| |/ |/ |/ | |
| | |
+----------------------------------+ V
+-----+
|\ |\ |\ | | 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