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).
AbstractSecurity 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.
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 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.
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.
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]. 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.
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]. 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. 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 ---------+
For example, it is likely that a company that manufactures both computers and Ethernet adapters will, at least internally, use its own adapters, which significantly limits the range of built-in addresses. Problems such as those described above make the production of code to generate unpredictable quantities difficult if the code is to be ported across a variety of computer platforms and systems.
non-uniform it is. Simple techniques to de-skew a bit stream are given below, and stronger cryptographic techniques are described in Section 5.2.
N ( 0.5 + ( 0.5 * (2E) ) ) < 0.5 + d. Solving for N yields N > log(2d)/log(2E). (Note that 2E is less than 1, so its log is negative. Division by a negative number reverses the sense of an inequality.) The following table gives the length N of the string that must be sampled for various degrees of skew in order to come within 0.001 of a 50/50 distribution. +---------+--------+-------+ | Prob(1) | E | N | +---------+--------+-------+ | 0.5 | 0.00 | 1 | | 0.6 | 0.10 | 4 | | 0.7 | 0.20 | 7 | | 0.8 | 0.30 | 13 | | 0.9 | 0.40 | 28 | | 0.95 | 0.45 | 59 | | 0.99 | 0.49 | 308 | +---------+--------+-------+ The last entry shows that even if the distribution is skewed 99% in favor of ones, the parity of a string of 308 samples will be within 0.001 of a 50/50 distribution. But, as we shall see in section 5.2, there are much stronger techniques that extract more of the available entropy. 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. 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]. Section 2 for the amount of information in a sequence. Since the compression is reversible, the same amount of information must be present in the shorter output as was present in the longer input. By the Shannon information equation, this is only possible if, on average, the probabilities of the different shorter sequences are more uniformly distributed than were the probabilities of the longer sequences. Therefore, the shorter sequences must be de-skewed relative to the input.
However, many compression techniques add a somewhat predictable preface to their output stream and may insert a similar sequence periodically in their output or otherwise introduce subtle patterns of their own. They should be considered only rough techniques compared to those described in Section 5.2. At a minimum, the beginning of the compressed sequence should be skipped and only later bits should used for applications requiring roughly-random bits. 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].
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. 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. SBOX1, SBOX2]. 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.
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. 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 output. 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 block size. 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.