1482 lines
58 KiB
Markdown
1482 lines
58 KiB
Markdown
---
|
|
created_at: '2016-11-01T20:35:08.000Z'
|
|
title: Randomness Requirements for Security (2005)
|
|
url: http://tools.ietf.org/html/rfc4086
|
|
author: Tomte
|
|
points: 42
|
|
story_text:
|
|
comment_text:
|
|
num_comments: 19
|
|
story_id:
|
|
story_title:
|
|
story_url:
|
|
parent_id:
|
|
created_at_i: 1478032508
|
|
_tags:
|
|
- story
|
|
- author_Tomte
|
|
- story_12849798
|
|
objectID: '12849798'
|
|
year: 2005
|
|
|
|
---
|
|
BEST CURRENT PRACTICE
|
|
|
|
|
|
|
|
Errata
|
|
Exist
|
|
|
|
|
|
|
|
Network Working Group D. Eastlake, 3rd
|
|
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.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 1]
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20051. 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
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 2]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 200511. Acknowledgments ................................................39
|
|
Appendix A: Changes from RFC 1750 ..................................40
|
|
Informative References .............................................41
|
|
|
|
1 . Introduction and OverviewSSH] [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.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 3]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20052 . General RequirementsRFC1948].
|
|
|
|
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
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 4]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005SHANNON]. 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.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 5]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005LUBY].
|
|
|
|
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.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 6]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20053 . Entropy Sources6 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 RequiredSection 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.
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 7]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20053.2 . Existing Hardware Can Be Used For Randomness3.2.1 . Using Existing Sound/Video InputSection 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 DrivesDAVIS, 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
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 8]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20053.3 . Ring Oscillator SourcesSection 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].
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 9]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20053.4 . Problems with Clocks and Serial NumbersEastlake, et al. Standards Track [Page 10]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20053.5 . Timing and Value of External EventsEastlake, et al. Standards Track [Page 11]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20053.6 . Non-hardware Sources of Randomness4 . De-skewingEastlake, et al. Standards Track [Page 12]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005section 5.2,
|
|
there are much stronger techniques that extract more of the available
|
|
entropy.
|
|
|
|
4.2 . Using Transition Mappings to De-SkewVON_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 |
|
|
+------+-----------------------------------------+
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 14]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20054.3 . Using FFT to De-Skewsection 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-SkewSection 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.
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 15]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005Section 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 . MixingSection 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].
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 16]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20055.1 . A Trivial Mixing FunctionSection
|
|
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
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 17]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20055.2 . Stronger Mixing FunctionsAES] 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
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 18]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20055.3 . Using S-Boxes for MixingSBOX1, SBOX2].
|
|
|
|
5.4 . Diffie-Hellman as a Mixing FunctionD-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.
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 19]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20055.5 . Using a Mixing Function to Stretch Random BitsSection 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 FunctionEastlake, et al. Standards Track [Page 20]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20056 . Pseudo-random Number GeneratorsSection 3 and possibly de-skewed and mixed as described in Sections 4
|
|
and 5, one can algorithmically extend that seed to produce a large
|
|
number of cryptographically-strong random quantities. Such
|
|
algorithms are platform independent and can operate in the same
|
|
fashion on any computer. For the algorithms to be secure, their
|
|
input and internal workings must be protected from adversarial
|
|
observation.
|
|
|
|
The design of such pseudo-random number generation algorithms, like
|
|
the design of symmetric encryption algorithms, is not a task for
|
|
amateurs. Section 6.1 below lists a number of bad ideas that failed
|
|
algorithms have used. To learn what works, skip Section 6.1 and just
|
|
read the remainder of this section and Section 7, which describes and
|
|
references some standard pseudo random number generation algorithms.
|
|
See Section 7 and Part 3 of [X9.82].
|
|
|
|
6.1 . Some Bad Ideas6.1.1 . The Fallacy of Complex ManipulationEastlake, et al. Standards Track [Page 21]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005KNUTH], where the author describes a
|
|
complex algorithm. It was intended that the machine language program
|
|
corresponding to the algorithm would be so complicated that a person
|
|
trying to read the code without comments wouldn't know what the
|
|
program was doing. Unfortunately, actual use of this algorithm
|
|
showed that it almost immediately converged to a single repeated
|
|
value in one case and a small cycle of values in another case.
|
|
|
|
Not only does complex manipulation not help you if you have a limited
|
|
range of seeds, but blindly-chosen complex manipulation can destroy
|
|
the entropy in a good seed!
|
|
|
|
6.1.2 . The Fallacy of Selection from a Large DatabaseUSENET_1, USENET_2]. Assume that a
|
|
random quantity was selected by fetching 32 bytes of data from a
|
|
random starting point in this data. This does not yield 32*8 = 256
|
|
bits worth of unguessability. Even if much of the data is human
|
|
language that contains no more than 2 or 3 bits of information per
|
|
byte, it doesn't yield 32*2 = 64 bits of unguessability. For an
|
|
adversary with access to the same Usenet database, the unguessability
|
|
rests only on the starting point of the selection. That is perhaps a
|
|
little over a couple of dozen bits of unguessability.
|
|
|
|
The same argument applies to selecting sequences from the data on a
|
|
publicly available CD/DVD recording or any other large public
|
|
database. If the adversary has access to the same database, this
|
|
"selection from a large volume of data" step buys little. However,
|
|
if a selection can be made from data to which the adversary has no
|
|
access, such as system buffers on an active multi-user system, it may
|
|
be of help.
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 22]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20056.1.3 . Traditional Pseudo-random SequencesKNUTH] has a classic exposition on pseudo-random numbers.
|
|
Applications he mentions are simulations of natural phenomena,
|
|
sampling, numerical analysis, testing computer programs, decision
|
|
making, and games. None of these have the same characteristics as
|
|
the sorts of security uses we are talking about. Only in the last
|
|
two could there be an adversary trying to find the random quantity.
|
|
However, in these cases, the adversary normally has only a single
|
|
chance to use a guessed value. In guessing passwords or attempting
|
|
to break an encryption scheme, the adversary normally has many,
|
|
perhaps unlimited, chances at guessing the correct value. Sometimes
|
|
the adversary can store the message to be broken and repeatedly
|
|
attack it. Adversaries are also be assumed to be aided by a
|
|
computer.
|
|
|
|
For testing the "randomness" of numbers, Knuth suggests a variety of
|
|
measures, including statistical and spectral. These tests check
|
|
things like autocorrelation between different parts of a "random"
|
|
sequence or distribution of its values. But these tests could be met
|
|
by a constant stored random sequence, such as the "random" sequence
|
|
printed in the CRC Standard Mathematical Tables [CRC]. Despite
|
|
meeting all the tests suggested by Knuth, that sequence is unsuitable
|
|
for cryptographic us, as adversaries must be assumed to have copies
|
|
of all commonly published "random" sequences and to be able to spot
|
|
the source and predict future values.
|
|
|
|
A typical pseudo-random number generation technique is the linear
|
|
congruence pseudo-random number generator. This technique uses
|
|
modular arithmetic, where the value numbered N+1 is calculated from
|
|
the value numbered N by
|
|
|
|
V = ( V * a + b )(Mod c)
|
|
N+1 N
|
|
|
|
The above technique has a strong relationship to linear shift
|
|
register pseudo-random number generators, which are well understood
|
|
cryptographically [SHIFT*]. In such generators, bits are introduced
|
|
at one end of a shift register as the Exclusive Or (binary sum
|
|
without carry) of bits from selected fixed taps into the register.
|
|
For example, consider the following:
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 23]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005SCHNEIER, STERN]. For example, with
|
|
the generators above, one can determine V(n+1) given knowledge of
|
|
V(n). In fact, it has been shown that with these techniques, even if
|
|
only one bit of the pseudo-random values are released, the seed can
|
|
be determined from short sequences.
|
|
|
|
Not only have linear congruent generators been broken, but techniques
|
|
are now known for breaking all polynomial congruent generators
|
|
[KRAWCZYK].
|
|
|
|
6.2 . Cryptographically Strong SequencesFERGUSON, SCHNEIER],
|
|
and not to reveal the complete state of the generator in the sequence
|
|
elements. If each value in the sequence can be calculated in a fixed
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 24]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20056.2.1 . OFB and CTR SequencesMODES].
|
|
|
|
An example is shown below in which shifting and masking are used to
|
|
combine part of the output feedback with part of the old input. This
|
|
type of partial feedback should be avoided for reasons described
|
|
below.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 25]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005Section 6.1.3, but with the all-
|
|
important difference that the feedback is determined by a complex
|
|
non-linear function of all bits rather than by a simple linear or
|
|
polynomial combination of output from a few bit position taps.
|
|
|
|
Donald W. Davies showed that this sort of shifted partial output
|
|
feedback significantly weakens an algorithm, compared to feeding all
|
|
the output bits back as input. In particular, for DES, repeatedly
|
|
encrypting a full 64-bit quantity will give an expected repeat in
|
|
about 2^63 iterations. Feeding back anything less than 64 (and more
|
|
than 0) bits will give an expected repeat in between 2^31 and 2^32
|
|
iterations!
|
|
|
|
To predict values of a sequence from others when the sequence was
|
|
generated by these techniques is equivalent to breaking the
|
|
cryptosystem or to inverting the "non-invertible" hashing with only
|
|
partial information available. The less information revealed in each
|
|
iteration, the harder it will be for an adversary to predict the
|
|
sequence. Thus it is best to use only one bit from each value. It
|
|
has been shown that in some cases this makes it impossible to break a
|
|
system even when the cryptographic system is invertible and could be
|
|
broken if all of each generated value were revealed.
|
|
|
|
6.2.2 . The Blum Blum Shub Sequence GeneratorBBS]. It is also very simple and is based on quadratic
|
|
residues. Its only disadvantage is that it is computationally
|
|
intensive compared to the traditional techniques given in Section
|
|
6.1.3. This is not a major drawback if it is used for moderately-
|
|
infrequent purposes, such as generating session keys.
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 26]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20056.3 . Entropy Pool Techniques7.1.2 and 7.1.3 utilize the technique of maintaining a
|
|
"pool" of bits and providing operations for strongly mixing input
|
|
with some randomness into the pool and extracting pseudo-random bits
|
|
from the pool. This is illustrated in the figure below.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 27]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005RSA_BULL1] for similar
|
|
suggestions.
|
|
|
|
7 . Randomness Generation Examples and Standardssection 7.1, include an entropy source.
|
|
Others, described in section 7.2, provide the pseudo-random number
|
|
strong-sequence generator but assume the input of a random seed or
|
|
input from a source of entropy.
|
|
|
|
7.1 . Complete Randomness GeneratorsDES]. The third is
|
|
a more modern and stronger standard based on SHA-1 [SHA*]. Lastly,
|
|
the widely deployed modern UNIX and Windows random number generators
|
|
are described.
|
|
|
|
7.1.1 . US DoD Recommendations for Password GenerationDoD]. It suggests using the US Data
|
|
Encryption Standard [DES] in Output Feedback Mode [MODES] as follows:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 28]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20057.1.2 . The /dev/random DeviceEastlake, et al. Standards Track [Page 29]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20057.1.3 . Windows CryptGenRandomEastlake, et al. Standards Track [Page 30]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005WSC].
|
|
|
|
7.2 . Generators Assuming a Source of EntropySection
|
|
6.2) from that seed.
|
|
|
|
7.2.1 . X9.82 Pseudo-Random Number GenerationRFC2104]. The
|
|
draft version of this generator is described below, omitting a number
|
|
of optional features [X9.82].
|
|
|
|
In the subsections below, the HMAC hash construct is simply referred
|
|
to as HMAC but, of course, a particular standard SHA function must be
|
|
selected in an particular use. Generally speaking, if the strength
|
|
of the pseudo-random values to be generated is to be N bits, the SHA
|
|
function chosen must generate N or more bits of output, and a source
|
|
of at least N bits of input entropy will be required. The same hash
|
|
function must be used throughout an instantiation of this generator.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 31]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20057.2.2 . X9.17 Key GenerationX9.17]:
|
|
|
|
s is the initial 64 bit seed.
|
|
0
|
|
|
|
g is the sequence of generated 64-bit key quantities
|
|
n
|
|
|
|
k is a random key reserved for generating this key sequence.
|
|
|
|
t is the time at which a key is generated, to as fine a resolution
|
|
as is available (up to 64 bits).
|
|
|
|
DES ( K, Q ) is the DES encryption of quantity Q with key K.
|
|
|
|
Then:
|
|
|
|
g = DES ( k, DES ( k, t ) XOR s )
|
|
n n
|
|
|
|
s = DES ( k, DES ( k, t ) XOR g )
|
|
n+1 n
|
|
|
|
|
|
If g sub n is to be used as a DES key, then every eighth bit should
|
|
be adjusted for parity for that use, but the entire 64 bit unmodified
|
|
g should be used in calculating the next s.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 33]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20057.2.3 . DSS Pseudo-random Number GenerationDSS] provides a
|
|
method of producing a sequence of pseudo-random 160 bit quantities
|
|
for use as private keys or the like. This has been modified by
|
|
Change Notice 1 [DSS_CN1] to produce the following algorithm for
|
|
generating general-purpose pseudo-random numbers:
|
|
|
|
t = 0x 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0
|
|
|
|
XKEY = initial seed
|
|
0
|
|
|
|
For j = 0 to ...
|
|
|
|
XVAL = ( XKEY + optional user input ) (Mod 2^512)
|
|
j
|
|
|
|
X = G( t, XVAL )
|
|
j
|
|
|
|
XKEY = ( 1 + XKEY + X ) (Mod 2^512)
|
|
j+1 j j
|
|
|
|
|
|
The quantities X thus produced are the pseudo-random sequence of
|
|
160-bit values. Two functions can be used for "G" above. Each
|
|
produces a 160-bit value and takes two arguments, a 160-bit value and
|
|
a 512 bit value.
|
|
|
|
The first is based on SHA-1 and works by setting the 5 linking
|
|
variables, denoted H with subscripts in the SHA-1 specification, to
|
|
the first argument divided into fifths. Then steps (a) through (e)
|
|
of section 7 of the NIST SHA-1 specification are run over the second
|
|
argument as if it were a 512-bit data block. The values of the
|
|
linking variable after those steps are then concatenated to produce
|
|
the output of G [SHA*].
|
|
|
|
As an alternative method, NIST also defined an alternate G function
|
|
based on multiple applications of the DES encryption function [DSS].
|
|
|
|
8 . Examples of Randomness RequiredEastlake, et al. Standards Track [Page 34]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005ORMAN] and [RSA_BULL13] provide information on the
|
|
public key lengths that should be used for exchanging symmetric keys.
|
|
|
|
8.1 . Password Generationsection 7.1). Using a list of 1,000
|
|
words, the password could be expressed as a three-word phrase
|
|
(1,000,000,000 possibilities). By using case-insensitive letters and
|
|
digits, six characters would suffice ((26+10)^6 = 2,176,782,336
|
|
possibilities).
|
|
|
|
For a higher-security password, the number of bits required goes up.
|
|
To decrease the probability by 1,000 requires increasing the universe
|
|
of passwords by the same factor, which adds about 10 bits. Thus, to
|
|
have only a one in a million chance of a password being guessed under
|
|
the above scenario would require 39 bits of randomness and a password
|
|
that was a four-word phrase from a 1,000 word list, or eight
|
|
letters/digits. To go to a one-in-10^9 chance, 49 bits of randomness
|
|
are needed, implying a five-word phrase or a ten-letter/digit
|
|
password.
|
|
|
|
In a real system, of course, there are other factors. For example,
|
|
the larger and harder to remember passwords are, the more likely
|
|
users will bed to write them down, resulting in an additional risk of
|
|
compromise.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 35]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20058.2 . A Very High Security Cryptographic Key8.2.1 . Effort per Key TrialKeyStudy] that was sponsored by the Business Software Alliance. It
|
|
concluded that a reasonable key length in 1995 for very high security
|
|
is in the range of 75 to 90 bits and, since the cost of cryptography
|
|
does not vary much with the key size, it recommends 90 bits. To
|
|
update these recommendations, just add 2/3 of a bit per year for
|
|
Moore's law [MOORE]. This translates to a determination, in the year
|
|
2004, a reasonable key length is in the 81- to 96-bit range. In
|
|
fact, today, it is increasingly common to use keys longer than 96
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 36]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20058.2.2 . Meet-in-the-Middle AttacksKeyStudy]
|
|
analysis.
|
|
|
|
This amount of randomness is well beyond the limit of that in the
|
|
inputs recommended by the US DoD for password generation and could
|
|
require user-typing timing, hardware random number generation, or
|
|
other sources of randomness.
|
|
|
|
The meet-in-the-middle attack assumes that the cryptographic
|
|
algorithm can be decomposed in this way. Hopefully no modern
|
|
algorithm has this weakness, but there may be cases where we are not
|
|
sure of that or even of what algorithm a key will be used with. Even
|
|
if a basic algorithm is not subject to a meet-in-the-middle attack,
|
|
an attempt to produce a stronger algorithm by applying the basic
|
|
algorithm twice (or two different algorithms sequentially) with
|
|
different keys will gain less added security than would be expected.
|
|
Such a composite algorithm would be subject to a meet-in-the-middle
|
|
attack.
|
|
|
|
Enormous resources may be required to mount a meet-in-the-middle
|
|
attack, but they are probably within the range of the national
|
|
security services of a major nation. Essentially all nations spy on
|
|
other nations' traffic.
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 37]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 20058.2.3 . Other ConsiderationsKeyStudy] also considers the possibilities of special-purpose code-
|
|
breaking hardware and having an adequate safety margin.
|
|
|
|
Note that key length calculations such as those above are
|
|
controversial and depend on various assumptions about the
|
|
cryptographic algorithms in use. In some cases, a professional with
|
|
a deep knowledge of algorithm-breaking techniques and of the strength
|
|
of the algorithm in use could be satisfied with less than half of the
|
|
192 bit key size derived above.
|
|
|
|
For further examples of conservative design principles, see
|
|
[FERGUSON].
|
|
|
|
9 . Conclusion10 . Security ConsiderationsEastlake, et al. Standards Track [Page 38]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 200511 . AcknowledgementsRFC 1750,
|
|
the predecessor of this document:
|
|
|
|
David M. Balenson, Don T. Davis, Carl Ellison, Marc Horowitz,
|
|
Christian Huitema, Charlie Kaufman, Steve Kent, Hal Murray, Neil
|
|
Haller, Richard Pitkin, Tim Redmond, and Doug Tygar.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 39]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005RFC 1750
|
|
|
|
1. Additional acknowledgements have been added.
|
|
|
|
2. Insertion of section 5.3 on mixing with S-boxes.
|
|
|
|
3. Addition of section 3.3 on Ring Oscillator randomness sources.
|
|
|
|
4. Addition of AES and the members of the SHA series producing more
|
|
than 160 bits. Use of AES has been emphasized and the use of DES
|
|
de-emphasized.
|
|
|
|
5. Addition of section 6.3 on entropy pool techniques.
|
|
|
|
6. Addition of section 7.2.3 on the pseudo-random number generation
|
|
techniques given in FIPS 186-2 (with Change Notice 1), 7.2.1 on
|
|
those given in X9.82, section 7.1.2 on the random number
|
|
generation techniques of the /dev/random device in Linux and other
|
|
UNIX systems, and section 7.1.3 on random number generation
|
|
techniques in the Windows operating system.
|
|
|
|
7. Addition of references to the "Minimal Key Lengths for Symmetric
|
|
Ciphers to Provide Adequate Commercial Security" study published
|
|
in January 1996 [KeyStudy] and to [RFC1948].
|
|
|
|
8. Added caveats to using Diffie-Hellman as a mixing function and,
|
|
because of those caveats and its computationally intensive nature,
|
|
recommend against its use.
|
|
|
|
9. Addition of references to the X9.82 effort and the [TURBID] and
|
|
[NASLUND] papers.
|
|
|
|
10. Addition of discussion of min-entropy and Renyi entropy and
|
|
references to the [LUBY] book.
|
|
|
|
11. Major restructuring, minor wording changes, and a variety of
|
|
reference updates.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 40]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005AES] "Specification of the Advanced Encryption Standard
|
|
(AES)", United States of America, US National
|
|
Institute of Standards and Technology, FIPS 197,
|
|
November 2001.
|
|
|
|
[ASYMMETRIC] Simmons, G., Ed., "Secure Communications and
|
|
Asymmetric Cryptosystems", AAAS Selected Symposium
|
|
69, ISBN 0-86531-338-5, Westview Press, 1982.
|
|
|
|
[BBS] Blum, L., Blum, M., and M. Shub, "A Simple
|
|
Unpredictable Pseudo-Random Number Generator", SIAM
|
|
Journal on Computing, v. 15, n. 2, 1986.
|
|
|
|
[BRILLINGER] Brillinger, D., "Time Series: Data Analysis and
|
|
Theory", Holden-Day, 1981.
|
|
|
|
[CRC] "C.R.C. Standard Mathematical Tables", Chemical
|
|
Rubber Publishing Company.
|
|
|
|
[DAVIS] Davis, D., Ihaka, R., and P. Fenstermacher,
|
|
"Cryptographic Randomness from Air Turbulence in Disk
|
|
Drives", Advances in Cryptology - Crypto '94,
|
|
Springer-Verlag Lecture Notes in Computer Science
|
|
#839, 1984.
|
|
|
|
[DES] "Data Encryption Standard", US National Institute of
|
|
Standards and Technology, FIPS 46-3, October 1999.
|
|
Also, "Data Encryption Algorithm", American National
|
|
Standards Institute, ANSI X3.92-1981. See also FIPS
|
|
112, "Password Usage", which includes FORTRAN code
|
|
for performing DES.
|
|
|
|
[D-H] Rescorla, E., "Diffie-Hellman Key Agreement Method",
|
|
RFC 2631, June 1999.
|
|
|
|
[DNSSEC1] Arends, R., Austein, R., Larson, M., Massey, D., and
|
|
S. Rose, "DNS Security Introduction and
|
|
Requirements", RFC 4033, March 2005.
|
|
|
|
[DNSSEC2] Arends, R., Austein, R., Larson, M., Massey, D., and
|
|
S. Rose, "Resource Records for the DNS Security
|
|
Extensions", RFC 4034, March 2005.
|
|
|
|
[DNSSEC3] Arends, R., Austein, R., Larson, M., Massey, D., and
|
|
S. Rose, "Protocol Modifications for the DNS Security
|
|
Extensions", RFC 4035, March 2005.
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 41]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005DoD] "Password Management Guideline", United States of
|
|
America, Department of Defense, Computer Security
|
|
Center, CSC-STD-002-85, April 1885.
|
|
|
|
(See also "Password Usage", FIPS 112, which
|
|
incorporates CSC-STD-002-85 as one of its appendices.
|
|
FIPS 112 is currently available at:
|
|
http://www.idl.nist.gov/fipspubs/fip112.htm.)
|
|
|
|
[DSS] "Digital Signature Standard (DSS)", US National
|
|
Institute of Standards and Technology, FIPS 186-2,
|
|
January 2000.
|
|
|
|
[DSS_CN1] "Digital Signature Standard Change Notice 1", US
|
|
National Institute of Standards and Technology, FIPS
|
|
186-2 Change Notice 1, 5, October 2001.
|
|
|
|
[FERGUSON] Ferguson, N. and B. Schneier, "Practical
|
|
Cryptography", Wiley Publishing Inc., ISBN
|
|
047122894X, April 2003.
|
|
|
|
[GIFFORD] Gifford, D., "Natural Random Number", MIT/LCS/TM-371,
|
|
September 1988.
|
|
|
|
[IEEE_802.11i] "Amendment to Standard for Telecommunications and
|
|
Information Exchange Between Systems - LAN/MAN
|
|
Specific Requirements - Part 11: Wireless Medium
|
|
Access Control (MAC) and physical layer (PHY)
|
|
specifications: Medium Access Control (MAC) Security
|
|
Enhancements", IEEE, January 2004.
|
|
|
|
[IPSEC] Kent, S. and R. Atkinson, "Security Architecture for
|
|
the Internet Protocol", RFC 2401, November 1998.
|
|
|
|
[Jakobsson] Jakobsson, M., Shriver, E., Hillyer, B., and A.
|
|
Juels, "A practical secure random bit generator",
|
|
Proceedings of the Fifth ACM Conference on Computer
|
|
and Communications Security, 1998.
|
|
|
|
[KAUFMAN] Kaufman, C., Perlman, R., and M. Speciner, "Network
|
|
Security: Private Communication in a Public World",
|
|
Prentis Hall PTR, ISBN 0-13-046019-2, 2nd Edition
|
|
2002.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 42]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC:
|
|
Keyed-Hashing for Message Authentication", RFC 2104,
|
|
February 1997.
|
|
|
|
[RSA_BULL1] "Suggestions for Random Number Generation in
|
|
Software", RSA Laboratories Bulletin #1, January
|
|
1996.
|
|
|
|
[RSA_BULL13] Silverman, R., "A Cost-Based Security Analysis of
|
|
Symmetric and Asymmetric Key Lengths", RSA
|
|
Laboratories Bulletin #13, April 2000 (revised
|
|
November 2001).
|
|
|
|
[SBOX1] Mister, S. and C. Adams, "Practical S-box Design",
|
|
Selected Areas in Cryptography, 1996.
|
|
|
|
[SBOX2] Nyberg, K., "Perfect Non-linear S-boxes", Advances in
|
|
Cryptography, Eurocrypt '91 Proceedings, Springer-
|
|
Verland, 1991.
|
|
|
|
[SCHNEIER] Schneier, B., "Applied Cryptography: Protocols,
|
|
Algorithms, and Source Code in C", 2nd Edition, John
|
|
Wiley & Sons, 1996.
|
|
|
|
[SHANNON] Shannon, C., "The Mathematical Theory of
|
|
Communication", University of Illinois Press, 1963.
|
|
Originally from: Bell System Technical Journal, July
|
|
and October, 1948.
|
|
|
|
[SHIFT1] Golub, S., "Shift Register Sequences", Aegean Park
|
|
Press, Revised Edition, 1982.
|
|
|
|
[SHIFT2] Barker, W., "Cryptanalysis of Shift-Register
|
|
Generated Stream Cypher Systems", Aegean Park Press,
|
|
1984.
|
|
|
|
[SHA] "Secure Hash Standard", US National Institute of
|
|
Science and Technology, FIPS 180-2, 1 August 2002.
|
|
|
|
[SHA_RFC] Eastlake 3rd, D. and P. Jones, "US Secure Hash
|
|
Algorithm 1 (SHA1)", RFC 3174, September 2001.
|
|
|
|
[SSH] Products of the SECSH Working Group, Works in
|
|
Progress, 2005.
|
|
|
|
[STERN] Stern, J., "Secret Linear Congruential Generators are
|
|
not Cryptographically Secure", Proc. IEEE STOC, 1987.
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 45]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005TLS] Dierks, T. and C. Allen, "The TLS Protocol Version
|
|
1.0", RFC 2246, January 1999.
|
|
|
|
[TURBID] Denker, J., "High Entropy Symbol Generator",
|
|
<http://www.av8n.com/turbid/paper/turbid.htm>, 2003.
|
|
|
|
[USENET_1] Kantor, B. and P. Lapsley, "Network News Transfer
|
|
Protocol", RFC 977, February 1986.
|
|
|
|
[USENET_2] Barber, S., "Common NNTP Extensions", RFC 2980,
|
|
October 2000.
|
|
|
|
[VON_NEUMANN] Von Nuemann, J., "Various techniques used in
|
|
connection with random digits", Von Neumann's
|
|
Collected Works, Vol. 5, Pergamon Press, 1963.
|
|
|
|
[WSC] Howard, M. and D. LeBlanc, "Writing Secure Code,
|
|
Second Edition", Microsoft Press, ISBN 0735617228,
|
|
December 2002.
|
|
|
|
[X9.17] "American National Standard for Financial Institution
|
|
Key Management (Wholesale)", American Bankers
|
|
Association, 1985.
|
|
|
|
[X9.82] "Random Number Generation", American National
|
|
Standards Institute, ANSI X9F1, Work in Progress.
|
|
Part 1 - Overview and General Principles.
|
|
Part 2 - Non-Deterministic Random Bit Generators
|
|
Part 3 - Deterministic Random Bit Generators
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 46]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005Eastlake, et al. Standards Track [Page 47]
|
|
```
|
|
|
|
``` newpage
|
|
|
|
RFC 4086 Randomness Requirements for Security June 2005BCP 78, and except as set forth therein, the authors
|
|
retain all their rights.
|
|
|
|
This document and the information contained herein are provided on an
|
|
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
|
|
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
|
|
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
|
|
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
|
|
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
|
|
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
|
|
|
|
Intellectual Property
|
|
|
|
The IETF takes no position regarding the validity or scope of any
|
|
Intellectual Property Rights or other rights that might be claimed to
|
|
pertain to the implementation or use of the technology described in
|
|
this document or the extent to which any license under such rights
|
|
might or might not be available; nor does it represent that it has
|
|
made any independent effort to identify any such rights. Information
|
|
on the procedures with respect to rights in RFC documents can be
|
|
found in BCP 78 and BCP 79.
|
|
|
|
Copies of IPR disclosures made to the IETF Secretariat and any
|
|
assurances of licenses to be made available, or the result of an
|
|
attempt made to obtain a general license or permission for the use of
|
|
such proprietary rights by implementers or users of this
|
|
specification can be obtained from the IETF on-line IPR repository at
|
|
http://www.ietf.org/ipr.
|
|
|
|
The IETF invites any interested party to bring to its attention any
|
|
copyrights, patents or patent applications, or other proprietary
|
|
rights that may cover technology that may be required to implement
|
|
this standard. Please address the information to the IETF at ietf-
|
|
ipr@ietf.org.
|
|
|
|
Acknowledgement
|
|
|
|
Funding for the RFC Editor function is currently provided by the
|
|
Internet Society.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eastlake, et al. Standards Track [Page 48]
|
|
```
|
|
|
|
|
|
Html markup produced by rfcmarkup 1.126, available from
|
|
<https://tools.ietf.org/tools/rfcmarkup/>
|