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