diff options
Diffstat (limited to 'doc/rfc/rfc1750.txt')
| -rw-r--r-- | doc/rfc/rfc1750.txt | 1683 |
1 files changed, 1683 insertions, 0 deletions
diff --git a/doc/rfc/rfc1750.txt b/doc/rfc/rfc1750.txt new file mode 100644 index 0000000..56d478c --- /dev/null +++ b/doc/rfc/rfc1750.txt @@ -0,0 +1,1683 @@ + + + + + + +Network Working Group D. Eastlake, 3rd +Request for Comments: 1750 DEC +Category: Informational S. Crocker + Cybercash + J. Schiller + MIT + December 1994 + + + Randomness Recommendations for Security + +Status of this Memo + + This memo provides information for the Internet community. This memo + does not specify an Internet standard of any kind. Distribution of + this memo is unlimited. + +Abstract + + Security systems today are built on increasingly 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. The sophisticated attacker of these security + systems may find it easier to reproduce the environment that produced + the secret quantities, searching the resulting small set of + possibilities, than to locate the quantities in the whole of the + number space. + + Choosing random quantities to foil a resourceful and motivated + adversary is surprisingly difficult. This paper points out many + pitfalls in using traditional pseudo-random number generation + techniques for choosing 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 particular applications. + + + + + + + + + + + + +Eastlake, Crocker & Schiller [Page 1] + +RFC 1750 Randomness Recommendations for Security December 1994 + + +Acknowledgements + + Comments on this document that have been incorporated were received + from (in alphabetic order) the following: + + David M. Balenson (TIS) + Don Coppersmith (IBM) + Don T. Davis (consultant) + Carl Ellison (Stratus) + Marc Horowitz (MIT) + Christian Huitema (INRIA) + Charlie Kaufman (IRIS) + Steve Kent (BBN) + Hal Murray (DEC) + Neil Haller (Bellcore) + Richard Pitkin (DEC) + Tim Redmond (TIS) + Doug Tygar (CMU) + +Table of Contents + + 1. Introduction........................................... 3 + 2. Requirements........................................... 4 + 3. Traditional Pseudo-Random Sequences.................... 5 + 4. Unpredictability....................................... 7 + 4.1 Problems with Clocks and Serial Numbers............... 7 + 4.2 Timing and Content of External Events................ 8 + 4.3 The Fallacy of Complex Manipulation.................. 8 + 4.4 The Fallacy of Selection from a Large Database....... 9 + 5. Hardware for Randomness............................... 10 + 5.1 Volume Required...................................... 10 + 5.2 Sensitivity to Skew.................................. 10 + 5.2.1 Using Stream Parity to De-Skew..................... 11 + 5.2.2 Using Transition Mappings to De-Skew............... 12 + 5.2.3 Using FFT to De-Skew............................... 13 + 5.2.4 Using Compression to De-Skew....................... 13 + 5.3 Existing Hardware Can Be Used For Randomness......... 14 + 5.3.1 Using Existing Sound/Video Input................... 14 + 5.3.2 Using Existing Disk Drives......................... 14 + 6. Recommended Non-Hardware Strategy..................... 14 + 6.1 Mixing Functions..................................... 15 + 6.1.1 A Trivial Mixing Function.......................... 15 + 6.1.2 Stronger Mixing Functions.......................... 16 + 6.1.3 Diff-Hellman as a Mixing Function.................. 17 + 6.1.4 Using a Mixing Function to Stretch Random Bits..... 17 + 6.1.5 Other Factors in Choosing a Mixing Function........ 18 + 6.2 Non-Hardware Sources of Randomness................... 19 + 6.3 Cryptographically Strong Sequences................... 19 + + + +Eastlake, Crocker & Schiller [Page 2] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + 6.3.1 Traditional Strong Sequences....................... 20 + 6.3.2 The Blum Blum Shub Sequence Generator.............. 21 + 7. Key Generation Standards.............................. 22 + 7.1 US DoD Recommendations for Password Generation....... 23 + 7.2 X9.17 Key Generation................................. 23 + 8. Examples of Randomness Required....................... 24 + 8.1 Password Generation................................. 24 + 8.2 A Very High Security Cryptographic Key............... 25 + 8.2.1 Effort per Key Trial............................... 25 + 8.2.2 Meet in the Middle Attacks......................... 26 + 8.2.3 Other Considerations............................... 26 + 9. Conclusion............................................ 27 + 10. Security Considerations.............................. 27 + References............................................... 28 + Authors' Addresses....................................... 30 + +1. Introduction + + Software cryptography is coming into wider use. Systems like + Kerberos, PEM, PGP, etc. are maturing and becoming a part of the + network landscape [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. + + For the present, the lack of generally available facilities for + generating such unpredictable numbers is 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, the only safe strategy so far has been to force + the local installation to supply a suitable routine to generate + random numbers. To say the least, this is an awkward, error-prone + and unpalatable solution. + + It is important to keep in mind that the requirement is for data that + an adversary has a very low probability of guessing or determining. + This will fail if pseudo-random data is used which only meets + traditional statistical tests for randomness or which is based on + limited range sources, such as clocks. Frequently such random + quantities are determinable by an adversary searching through an + embarrassingly small space of possibilities. + + This informational document suggests techniques for producing random + quantities that will be resistant to such 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 + + + +Eastlake, Crocker & Schiller [Page 3] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + applications. + +2. Requirements + + Probably the most commonly encountered randomness requirement today + is the user password. This is usually a simple character string. + Obviously, if a password can be guessed, it 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 on ordinary + words. But this only affects 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. + + In some cases, such as the use of symmetric encryption with the one + time pads [CRYPTO*] or the US Data Encryption Standard [DES], the + parties who wish to communicate confidentially and/or with + authentication must all know the same secret key. In other cases, + using what are called asymmetric or "public key" cryptographic + techniques, 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 [ASYMMETRIC, CRYPTO*]. + + The frequency and volume of the requirement for random quantities + differs greatly for different cryptographic systems. Using pure RSA + [CRYPTO*], random quantities are required when the key pair is + generated, but thereafter any number of messages can be signed + without any further need for randomness. The public key Digital + Signature Algorithm that has been proposed by the US National + Institute of Standards and Technology (NIST) requires good random + numbers for each signature. And encrypting with a one time pad, in + principle the strongest possible encryption technique, requires a + volume of randomness equal to all the messages to be processed. + + 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 the information + theoretic sense [SHANNON]. This depends on the number of different + + + +Eastlake, Crocker & Schiller [Page 4] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + secret values possible and the probability of each value as follows: + + ----- + \ + Bits-of-info = \ - p * log ( p ) + / i 2 i + / + ----- + + where i varies from 1 to the number of possible secret values and p + sub i is the probability of the value numbered i. (Since 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, on the average, + have to try 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 + the adversary can know are impossible, or are of low probability, can + be initially ignored by an adversary, who will search through the + more probable values first. + + For example, consider a cryptographic system that uses 56 bit keys. + If these 56 bit keys are derived by 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 the 2^56 keys that + may at first appear to be the case. Only 8 bits of "information" are + in these 56 bit keys. + +3. Traditional Pseudo-Random Sequences + + Most traditional sources of random numbers use deterministic sources + of "pseudo-random" numbers. These typically start with a "seed" + quantity and use numeric or logical operations to produce a sequence + of values. + + [KNUTH] has a classic exposition on pseudo-random numbers. + Applications he mentions are simulation of natural phenomena, + sampling, numerical analysis, testing computer programs, decision + making, and games. None of these have the same characteristics as + the sort 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, + + + +Eastlake, Crocker & Schiller [Page 5] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + perhaps unlimited, chances at guessing the correct value and should + 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. They could be met by a + constant stored random sequence, such as the "random" sequence + printed in the CRC Standard Mathematical Tables [CRC]. + + A typical pseudo-random number generation technique, known as a + linear congruence pseudo-random number generator, is modular + arithmetic where the N+1th value is calculated from the Nth value 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: + + +----+ +----+ +----+ +----+ + | B | <-- | B | <-- | B | <-- . . . . . . <-- | B | <-+ + | 0 | | 1 | | 2 | | n | | + +----+ +----+ +----+ +----+ | + | | | | + | | V +-----+ + | V +----------------> | | + V +-----------------------------> | XOR | + +---------------------------------------------------> | | + +-----+ + + + V = ( ( V * 2 ) + B .xor. B ... )(Mod 2^n) + N+1 N 0 2 + + The goodness of traditional pseudo-random number generator algorithms + is measured by statistical tests on such sequences. Carefully chosen + values of the initial V and a, b, and c or the placement of shift + register tap in the above simple processes can produce excellent + statistics. + + + + + + +Eastlake, Crocker & Schiller [Page 6] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + These sequences may be adequate in simulations (Monte Carlo + experiments) as long as the sequence is orthogonal to the structure + of the space being explored. Even there, subtle patterns may cause + problems. However, such sequences are clearly bad for use in + security applications. They are fully predictable if the initial + state is known. Depending on the form of the pseudo-random number + generator, the sequence may be determinable from observation of a + short portion of the sequence [CRYPTO*, 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 is 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]. + +4. Unpredictability + + Randomness in the traditional sense described in section 3 is NOT the + same as the unpredictability required for security use. + + For example, use of a widely available constant sequence, such as + that from the CRC tables, is very weak against an adversary. Once + they learn of or guess it, they can easily break all security, future + and past, based on the sequence [CRC]. Yet the statistical + properties of these tables are good. + + The following sections describe the limitations of some randomness + generation techniques and sources. + +4.1 Problems with Clocks and Serial Numbers + + Computer clocks, or 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 on 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 + + + +Eastlake, Crocker & Schiller [Page 7] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + 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 + clocks that the code will execute on. + + Use of a hardware serial number such as an Ethernet 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 easily guessable based + on approximate date of manufacture or other data. For example, it is + likely that most of the Ethernet cards installed on Digital Equipment + Corporation (DEC) hardware within DEC were manufactured by DEC + itself, which significantly limits the range of built in addresses. + + Problems such as those described above related to clocks and serial + numbers make code to produce unpredictable quantities difficult if + the code is to be ported across a variety of computer platforms and + systems. + +4.2 Timing and Content 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, inputs + such as key strokes are 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 to sample timing details. + This makes it hard to build standard software intended for + distribution to a large range of machines based on this technique. + + The amount of mouse movement or the keys actually hit are usually + easier to access than timings but may yield less unpredictability as + the user may provide highly repetitive input. + + Other external events, such as network packet arrival times, can also + be used with care. In particular, the possibility of manipulation of + such times by an adversary must be considered. + +4.3 The Fallacy of Complex Manipulation + + One strategy which may give a misleading appearance of + unpredictability is to take a very complex algorithm (or an excellent + traditional pseudo-random number generator with good statistical + properties) and calculate a cryptographic key by starting with the + current value of a computer system clock as the seed. An adversary + who knew roughly when the generator was started would have a + + + +Eastlake, Crocker & Schiller [Page 8] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + relatively small number of seed values to test as they would know + likely values of the system clock. Large numbers of pseudo-random + bits could be generated but the search space an adversary would need + to check could be quite small. + + Thus very strong and/or complex manipulation of data will not help if + the adversary can learn what the manipulation is and there is not + enough unpredictability in the starting seed value. Even if they can + not learn what the manipulation is, they may be able to use the + limited number of results stemming from a limited number of seed + values to defeat security. + + Another serious strategy error is to assume that a very complex + pseudo-random number generation algorithm will produce strong random + numbers when there has been no theory behind or analysis of the + algorithm. There is a excellent example of this fallacy right near + the beginning of chapter 3 in [KNUTH] 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 randomness in a good seed! + +4.4 The Fallacy of Selection from a Large Database + + Another strategy that can give a misleading appearance of + unpredictability is selection of a quantity randomly from a database + and assume that its strength is related to the total number of bits + in the database. For example, typical USENET servers as of this date + process over 35 megabytes of information per day. Assume 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 after allowing that much of the data + is human language and probably has more like 2 or 3 bits of + information per byte, it doesn't yield 32*2.5 = 80 bits of + unguessability. For an adversary with access to the same 35 + megabytes the unguessability rests only on the starting point of the + selection. That is, at best, about 25 bits of unguessability in this + case. + + The same argument applies to selecting sequences from the data on a + CD ROM or Audio CD recording or any other large public database. If + the adversary has access to the same database, this "selection from a + + + +Eastlake, Crocker & Schiller [Page 9] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + large volume of data" step buys very 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 some + help. + +5. Hardware for Randomness + + Is there any hope for strong portable randomness in the future? + There might be. All that's needed is a physical source of + unpredictable numbers. + + A thermal noise or radioactive decay source and a fast, free-running + oscillator would do the trick directly [GIFFORD]. This is a trivial + amount of hardware, and could easily be included as a standard part + of a computer system's architecture. Furthermore, any system with a + spinning disk or the like has an adequate source of randomness + [DAVIS]. 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. + +5.1 Volume Required + + How much unpredictability is needed? Is it possible to quantify the + requirement in, say, number of random bits per second? + + The answer is not very much is needed. For DES, the key is 56 bits + and, as we show in an example in Section 8, even the highest security + system is unlikely to require a keying material of over 200 bits. If + a series of keys are needed, it can be generated from a strong random + seed using a cryptographically strong sequence as explained in + Section 6.3. A few hundred random bits generated once a day would be + enough using such techniques. 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 high security + applications to wait 200 seconds occasionally. + + These numbers are trivial to achieve. It could be done by a person + repeatedly tossing a coin. Almost any hardware process is likely to + be much faster. + +5.2 Sensitivity to Skew + + Is there any specific requirement on the shape of the distribution of + the random numbers? The good news is the distribution need not be + uniform. All that is needed is a conservative estimate of how non- + uniform it is to bound performance. Two simple techniques to de-skew + the bit stream are given below and stronger techniques are mentioned + in Section 6.1.2 below. + + + +Eastlake, Crocker & Schiller [Page 10] + +RFC 1750 Randomness Recommendations for Security December 1994 + + +5.2.1 Using Stream Parity to De-Skew + + Consider taking a sufficiently long string of bits and map 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 is absolutely trivial to implement in + hardware. + + The following analysis gives the number of bits that must be sampled: + + Suppose the ratio of ones to zeros is 0.5 + e : 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 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 one corresponds to the probability 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, i.e. then + + N + ( 0.5 + ( 0.5 * (2e) ) ) < 0.5 + d. + + + + + + +Eastlake, Crocker & Schiller [Page 11] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + 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 of the string which 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. + +5.2.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. You + could then discard any 00 or 11 pairs found, interpret 01 as a 0 and + 10 as a 1. Assume the probability of a 1 is 0.5+e and the + probability of a 0 is 0.5-e where e is the eccentricity of the source + and described in the previous section. Then the probability of each + pair is as follows: + + +------+-----------------------------------------+ + | 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 at the expense + of taking 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). + + + +Eastlake, Crocker & Schiller [Page 12] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + 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 not correlated, i.e., that the bits are + identical independent distributions. If alternate bits were 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 mis-read slightly so that overlapping successive bits + pairs were used instead of non-overlapping pairs, the statistical + analysis given is the same; however, instead of provided an unbiased + uncorrelated series of random 1's and 0's, it instead produces a + totally predictable sequence of exactly alternating 1's and 0's. + +5.2.3 Using FFT to De-Skew + + When real world data consists of strongly biased or correlated bits, + it may still contain useful amounts of randomness. This randomness + can be extracted through use of the discrete Fourier transform or its + optimized variant, the FFT. + + Using the Fourier transform of the data, strong correlations can be + discarded. If adequate data is processed and remaining correlations + decay, spectral lines approaching statistical independence and + normally distributed randomness can be produced [BRILLINGER]. + +5.2.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 + above 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 than 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. Thus the shorter sequences are de-skewed relative to the + input. + + However, many compression techniques add a somewhat predicatable + preface to their output stream and may insert such a sequence again + periodically in their output or otherwise introduce subtle patterns + of their own. They should be considered only a rough technique + compared with those described above or in Section 6.1.2. At a + minimum, the beginning of the compressed sequence should be skipped + and only later bits used for applications requiring random bits. + + + +Eastlake, Crocker & Schiller [Page 13] + +RFC 1750 Randomness Recommendations for Security December 1994 + + +5.3 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. + +5.3.1 Using Existing Sound/Video Input + + Increasingly computers are being built with inputs that digitize some + real world analog source, such as sound from a microphone or video + input from a camera. Under appropriate circumstances, such input can + provide reasonably high quality random bits. The "input" from a + sound digitizer with no source plugged in or a camera with the lens + cap on, if the system has enough gain to detect anything, is + essentially thermal noise. + + For example, on a SPARCstation, one can read from the /dev/audio + device with nothing plugged into the microphone jack. Such data is + essentially random noise although it should not be trusted without + some checking in case of hardware failure. It will, in any case, + need to be de-skewed as described elsewhere. + + Combining this with compression to de-skew one can, in UNIXese, + generate a huge amount of medium quality random data by doing + + cat /dev/audio | compress - >random-bits-file + +5.3.2 Using Existing Disk Drives + + Disk drives have small random fluctuations in their rotational speed + due to chaotic air turbulence [DAVIS]. By adding low level disk seek + time instrumentation to a system, a series of measurements can be + obtained that include this randomness. Such data is usually highly + correlated so that significant processing is needed, including FFT + (see section 5.2.3). Nevertheless experimentation has shown that, + with such processing, disk drives easily produce 100 bits a minute or + more of excellent random data. + + Partly offsetting this need for processing is the fact that disk + drive failure will normally be rapidly noticed. Thus, problems with + this method of random number generation due to hardware failure are + very unlikely. + +6. Recommended Non-Hardware Strategy + + What is the best overall strategy for meeting the requirement for + unguessable random numbers in the absence of a reliable hardware + source? It is to obtain random input from a large number of + uncorrelated sources and to mix them with a strong mixing function. + + + +Eastlake, Crocker & Schiller [Page 14] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + Such a function will preserve the randomness present in any of the + sources even if other quantities being combined are fixed or easily + guessable. This may be advisable even with a good hardware source as + hardware can also fail, though this should be weighed against any + increase in the chance of overall failure due to added software + complexity. + +6.1 Mixing Functions + + A strong mixing function is one which combines two or more inputs and + produces an output where 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 to a shorter stream which is more random, as discussed + in Section 5.2 above. This is simply another case where a strong + mixing function is desired, mixing the input bits to produce a + smaller number of output bits. The technique given in Section 5.2.1 + of using the parity of a number of bits is simply the result of + successively Exclusive Or'ing them which 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 6.1.2. + +6.1.1 A Trivial Mixing Function + + A trivial example for single bit inputs is the Exclusive Or function, + which 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 will still provide 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. If we assume an "eccentricity" e as defined in Section 5.2 + above, then the output eccentricity relates to the input eccentricity + + + +Eastlake, Crocker & Schiller [Page 15] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + 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 where 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, keep in mind 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. + +6.1.2 Stronger Mixing Functions + + The US Government Data Encryption Standard [DES] is an example of a + strong mixing function for multiple bit quantities. It takes up to + 120 bits of input (64 bits of "data" and 56 bits of "key") and + produces 64 bits of output each of which is dependent on a complex + non-linear function of all input bits. Other strong encryption + functions with this characteristic can also be used by considering + them to mix all of their key and data input bits. + + Another good family of mixing functions are the "message digest" or + hashing functions such as The US Government Secure Hash Standard + [SHS] and the MD2, MD4, MD5 [MD2, MD4, MD5] series. These functions + all take an arbitrary amount of input and produce an output mixing + all the input bits. The MD* series produce 128 bits of output and SHS + produces 160 bits. + + + + + + +Eastlake, Crocker & Schiller [Page 16] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + Although the message digest functions are designed for variable + amounts of input, DES and other encryption functions can also be used + to combine any number of inputs. If 64 bits of output is adequate, + the inputs can be packed into a 64 bit data quantity and successive + 56 bit keys, padding with zeros if needed, which are then used to + successively encrypt using DES in Electronic Codebook Mode [DES + MODES]. If more than 64 bits of output are needed, use more complex + mixing. For example, if inputs are packed into three quantities, A, + B, and C, use DES to encrypt A with B as a key and then with C as a + key to produce the 1st 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 to stretch things. The same can be + done with the hash functions by hashing various subsets of the input + data to produce multiple outputs. But keep in mind that it is + impossible to get more bits of "randomness" out than are put in. + + An example of using a strong mixing function would be to reconsider + the case of a string of 308 bits each of which is biased 99% towards + zero. The parity technique given in Section 5.2.1 above reduced 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 sequence has 5 bits of information in it. + Thus hashing it with SHS or MD5 and taking the bottom 5 bits of the + result would yield 5 unbiased random bits as opposed to the single + bit given by calculating the parity of the string. + +6.1.3 Diffie-Hellman as a Mixing Function + + Diffie-Hellman exponential key exchange is a technique that yields a + shared secret between two parties that can be made computationally + infeasible for a third party to determine 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 them + [D-H]. If these initial quantities are random, then the shared + secret contains the combined randomness of them both, assuming they + are uncorrelated. + +6.1.4 Using a Mixing Function to Stretch Random Bits + + While it is not necessary for a mixing function to produce the same + or fewer bits than its inputs, mixing bits cannot "stretch" the + amount of random unpredictability present in the inputs. Thus four + inputs of 32 bits each where there is 12 bits worth of + unpredicatability (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 + + + +Eastlake, Crocker & Schiller [Page 17] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + 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 way using Exclusive Or to produce one bit from two did + above. + + The last table in Section 6.1.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. + +6.1.5 Other Factors in Choosing a Mixing Function + + For local use, DES has the advantages that it has been widely tested + for flaws, is widely documented, and is widely implemented with + hardware and software implementations available all over the world + including source code available by anonymous FTP. The SHS and MD* + family are younger algorithms which have been less tested but there + is no particular reason to believe they are flawed. Both MD5 and SHS + were derived from the earlier MD4 algorithm. They all have source + code available by anonymous FTP [SHS, MD2, MD4, MD5]. + + DES and SHS have been vouched for the the US National Security Agency + (NSA) on the basis of criteria that primarily remain secret. While + this is 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. No concealed or special weakness has been found in DES. It is + almost certain that the NSA modification to MD4 to produce the SHS + similarly strengthened the algorithm, possibly against threats not + yet known in the public cryptographic community. + + DES, SHS, MD4, and MD5 are royalty free for all purposes. MD2 has + been freely licensed only for non-profit use in connection with + Privacy Enhanced Mail [PEM]. Between the MD* algorithms, some people + believe that, as with "Goldilocks and the Three Bears", MD2 is strong + but too slow, MD4 is fast but too weak, and MD5 is just right. + + Another advantage of the MD* or similar hashing algorithms over + encryption algorithms is that they are not subject to the same + regulations imposed by the US Government prohibiting the unlicensed + export or import of encryption/decryption software and hardware. The + same should be true of DES rigged to produce an irreversible hash + code but most DES packages are oriented to reversible encryption. + + + + + +Eastlake, Crocker & Schiller [Page 18] + +RFC 1750 Randomness Recommendations for Security December 1994 + + +6.2 Non-Hardware Sources of Randomness + + The best source of input for mixing would be a hardware randomness + such as disk drive timing affected by air turbulence, audio input + with thermal noise, or radioactive decay. However, if that is not + available there are other possibilities. These include system + clocks, system or input/output buffers, user/system/hardware/network + serial numbers and/or addresses and timing, and user input. + Unfortunately, any of these sources can produce limited or + predicatable values under some circumstances. + + Some of the sources listed above would be quite strong on multi-user + systems where, in essence, each user of the system is a source of + randomness. However, on a small single user system, such as a + typical IBM PC or Apple Macintosh, it might be possible for an + adversary to assemble a similar configuration. This could give the + adversary inputs to the mixing process that were sufficiently + correlated to those used originally as 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. For + example, the timing and content of requested "random" user keystrokes + can yield hundreds of random bits but conservative assumptions need + to be made. For example, assuming a few bits of randomness if the + inter-keystroke interval is unique in the sequence up to that point + and a similar assumption if the key hit is unique but assuming that + no bits of randomness are present in the initial key value or if the + timing or key value duplicate previous values. The results of mixing + these timings and characters typed could be further combined with + clock values and other inputs. + + This strategy may make practical portable code to produce 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 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. + +6.3 Cryptographically Strong Sequences + + In cases where a series of random quantities must be generated, an + adversary may learn some values in the sequence. In general, they + should not be able to predict other values from the ones that they + know. + + + + + + +Eastlake, Crocker & Schiller [Page 19] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + The correct technique is to start with a strong random seed, take + cryptographically strong steps from that seed [CRYPTO2, CRYPTO3], and + do not reveal the complete state of the generator in the sequence + elements. If each value in the sequence can be calculated in a fixed + way from the previous value, then when any value is compromised, all + future values can be determined. This would be the case, for + example, if each value were a constant function of the previously + used values, even if the function were a very strong, non-invertible + message digest function. + + It should be noted that if your technique for generating a sequence + of key values is fast enough, it can trivially be used as the basis + for a confidentiality system. If two parties use the same sequence + generating technique and start with the same seed material, they will + generate identical sequences. These could, for example, be xor'ed at + one end with data being send, encrypting it, and xor'ed with this + data as received, decrypting it due to the reversible properties of + the xor operation. + +6.3.1 Traditional Strong Sequences + + A traditional way to achieve a strong sequence has been to have the + values be produced by hashing the quantities produced by + concatenating the seed with successive integers or the like and then + mask the values obtained so as to limit the amount of generator state + available to the adversary. + + It may also be possible to use an "encryption" algorithm with a + random key and seed value to encrypt and feedback some or all of the + output encrypted value into the value to be encrypted for the next + iteration. Appropriate feedback techniques will usually be + recommended with the encryption algorithm. An example is shown below + where shifting and masking are used to combine the cypher output + feedback. This type of feedback is recommended by the US Government + in connection with DES [DES MODES]. + + + + + + + + + + + + + + + + +Eastlake, Crocker & Schiller [Page 20] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + +---------------+ + | V | + | | n | + +--+------------+ + | | +---------+ + | +---------> | | +-----+ + +--+ | Encrypt | <--- | Key | + | +-------- | | +-----+ + | | +---------+ + V V + +------------+--+ + | V | | + | n+1 | + +---------------+ + + Note that if a shift of one is used, this is the same as the shift + register technique described in Section 3 above but with the all + important difference that the feedback is determined by a complex + non-linear function of all bits rather than a simple linear or + polynomial combination of output from a few bit position taps. + + It has been shown by Donald W. Davies that this sort of shifted + partial output feedback significantly weakens an algorithm compared + will feeding all of the output bits back as input. In particular, + for DES, repeated 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 inverting the "non-invertible" hashing involved with + only partial information available. The less information revealed + 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 can be + broken if all of each generated value was revealed. + +6.3.2 The Blum Blum Shub Sequence Generator + + Currently the generator which has the strongest public proof of + strength is called the Blum Blum Shub generator after its inventors + [BBS]. It is also very simple and is based on quadratic residues. + It's only disadvantage is that is is computationally intensive + compared with the traditional techniques give in 6.3.1 above. This + is not a serious draw back if it is used for moderately infrequent + purposes, such as generating session keys. + + + +Eastlake, Crocker & Schiller [Page 21] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + Simply choose two large prime numbers, say p and q, which both have + the property that you get a remainder of 3 if you divide them by 4. + Let n = p * q. Then you choose a random number x relatively prime to + n. The initial seed for the generator and the method for calculating + subsequent values are then + + 2 + s = ( x )(Mod n) + 0 + + 2 + s = ( s )(Mod n) + i+1 i + + You must be careful to use only a few bits from the bottom of each s. + It is always safe to use only the lowest order bit. If you use no + more than the + + log ( log ( s ) ) + 2 2 i + + low order bits, then predicting any additional bits from a sequence + generated in this manner is provable as hard as factoring n. As long + as the initial x is secret, you can even make n public if you want. + + An intersting characteristic of this generator is that you can + directly calculate any of the s values. In particular + + i + ( ( 2 )(Mod (( p - 1 ) * ( q - 1 )) ) ) + s = ( s )(Mod n) + i 0 + + This means that in applications where many keys are generated in this + fashion, it is not necessary to save them all. Each key can be + effectively indexed and recovered from that small index and the + initial s and n. + +7. Key Generation Standards + + Several public standards are now in place for the generation of keys. + Two of these are described below. Both use DES but any equally + strong or stronger mixing function could be substituted. + + + + + + + + +Eastlake, Crocker & Schiller [Page 22] + +RFC 1750 Randomness Recommendations for Security December 1994 + + +7.1 US DoD Recommendations for Password Generation + + The United States Department of Defense has specific recommendations + for password generation [DoD]. They suggest using the US Data + Encryption Standard [DES] in Output Feedback Mode [DES MODES] as + follows: + + use an initialization vector determined from + the system clock, + system ID, + user ID, and + date and time; + use a key determined from + system interrupt registers, + system status registers, and + system counters; and, + as plain text, use an external randomly generated 64 bit + quantity such as 8 characters typed in by a system + administrator. + + The password can then be calculated from the 64 bit "cipher text" + generated in 64-bit Output Feedback Mode. As many bits as are needed + can be taken from these 64 bits and expanded into a pronounceable + word, phrase, or other format if a human being needs to remember the + password. + +7.2 X9.17 Key Generation + + The American National Standards Institute has specified a method for + generating a sequence of keys as follows: + + 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 + + + + + + + + +Eastlake, Crocker & Schiller [Page 23] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + 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. + +8. Examples of Randomness Required + + Below are two examples showing rough calculations of needed + randomness for security. The first is for moderate security + passwords while the second assumes a need for a very high security + cryptographic key. + +8.1 Password Generation + + Assume that user passwords change once a year and it is desired that + the probability that an adversary could guess the password for a + particular account be less than one in a thousand. Further assume + that sending a password to the system is the only way to try a + password. Then the crucial question is how often an adversary can + try possibilities. Assume that delays have been introduced into a + system so that, at most, an adversary can make one password try every + six seconds. That's 600 per hour or about 15,000 per day or about + 5,000,000 tries in a year. Assuming any sort of monitoring, it is + unlikely someone could actually try continuously for a year. In + fact, even if log files are only checked monthly, 500,000 tries is + more plausible before the attack is noticed and steps taken to change + passwords and make it harder to try more passwords. + + To have a one in a thousand chance of guessing the password in + 500,000 tries implies a universe of at least 500,000,000 passwords or + about 2^29. Thus 29 bits of randomness are needed. This can probably + be achieved using the US DoD recommended inputs for password + generation as it has 8 inputs which probably average over 5 bits of + randomness each (see section 7.1). Using a list of 1000 words, the + password could be expressed as a three word phrase (1,000,000,000 + possibilities) or, using case insensitive letters and digits, six + 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 + + + +Eastlake, Crocker & Schiller [Page 24] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + that was a four word phrase from a 1000 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 ten letter/digit password. + + In a real system, of course, there are also other factors. For + example, the larger and harder to remember passwords are, the more + likely users are to write them down resulting in an additional risk + of compromise. + +8.2 A Very High Security Cryptographic Key + + Assume that a very high security key is needed for symmetric + encryption / decryption between two parties. Assume an adversary can + observe communications and knows the algorithm being used. Within + the field of random possibilities, the adversary can try key values + in hopes of finding the one in use. Assume further that brute force + trial of keys is the best the adversary can do. + +8.2.1 Effort per Key Trial + + How much effort will it take to try each key? For very high security + applications it is best to assume a low value of effort. Even if it + would clearly take tens of thousands of computer cycles or more to + try a single key, there may be some pattern that enables huge blocks + of key values to be tested with much less effort per key. Thus it is + probably best to assume no more than a couple hundred cycles per key. + (There is no clear lower bound on this as computers operate in + parallel on a number of bits and a poor encryption algorithm could + allow many keys or even groups of keys to be tested in parallel. + However, we need to assume some value and can hope that a reasonably + strong algorithm has been chosen for our hypothetical high security + task.) + + If the adversary can command a highly parallel processor or a large + network of work stations, 2*10^10 cycles per second is probably a + minimum assumption for availability today. Looking forward just a + couple years, there should be at least an order of magnitude + improvement. Thus assuming 10^9 keys could be checked per second or + 3.6*10^11 per hour or 6*10^13 per week or 2.4*10^14 per month is + reasonable. This implies a need for a minimum of 51 bits of + randomness in keys to be sure they cannot be found in a month. Even + then it is possible that, a few years from now, a highly determined + and resourceful adversary could break the key in 2 weeks (on average + they need try only half the keys). + + + + + + + +Eastlake, Crocker & Schiller [Page 25] + +RFC 1750 Randomness Recommendations for Security December 1994 + + +8.2.2 Meet in the Middle Attacks + + If chosen or known plain text and the resulting encrypted text are + available, a "meet in the middle" attack is possible if the structure + of the encryption algorithm allows it. (In a known plain text + attack, the adversary knows all or part of the messages being + encrypted, possibly some standard header or trailer fields. In a + chosen plain text attack, the adversary can force some chosen plain + text to be encrypted, possibly by "leaking" an exciting text that + would then be sent by the adversary over an encrypted channel.) + + An oversimplified explanation of the meet in the middle attack is as + follows: the adversary can half-encrypt the known or chosen plain + text with all possible first half-keys, sort the output, then half- + decrypt the encoded text with all the second half-keys. If a match + is found, the full key can be assembled from the halves and used to + decrypt other parts of the message or other messages. At its best, + this type of attack can halve the exponent of the work required by + the adversary while adding a large but roughly constant factor of + effort. To be assured of safety against this, a doubling of the + amount of randomness in the key to a minimum of 102 bits is required. + + The meet in the middle attack assumes that the cryptographic + algorithm can be decomposed in this way but we can not rule that out + without a deep knowledge of the algorithm. 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 may 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 government traffic and several nations are believed to + spy on commercial traffic for economic advantage. + +8.2.3 Other Considerations + + Since we have not even considered the possibilities of special + purpose code breaking hardware or just how much of a safety margin we + want beyond our assumptions above, probably a good minimum for a very + high security cryptographic key is 128 bits of randomness which + implies a minimum key length of 128 bits. If the two parties agree + on a key by Diffie-Hellman exchange [D-H], then in principle only + half of this randomness would have to be supplied by each party. + However, there is probably some correlation between their random + inputs so it is probably best to assume that each party needs to + + + +Eastlake, Crocker & Schiller [Page 26] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + provide at least 96 bits worth of randomness for very high security + if Diffie-Hellman is used. + + This amount of randomness is 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. + + It should be noted that key length calculations such at 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 code breaking techniques and of the strength of + the algorithm in use could be satisfied with less than half of the + key size derived above. + +9. Conclusion + + Generation of unguessable "random" secret quantities for security use + is an essential but difficult task. + + We have shown that hardware techniques to produce such randomness + would be relatively simple. In particular, the volume and quality + would not need to be high and existing computer hardware, such as + disk drives, can be used. Computational techniques are available to + process low quality random quantities from multiple sources or a + larger quantity of such low quality input from one source and produce + a smaller quantity of higher quality, less predictable key material. + In the absence of hardware sources of randomness, a variety of user + and software sources can frequently be used instead with care; + however, most modern systems already have hardware, such as disk + drives or audio input, that could be used to produce high quality + randomness. + + Once a sufficient quantity of high quality seed key material (a few + hundred bits) is available, strong computational techniques are + available to produce cryptographically strong sequences of + unpredicatable quantities from this seed material. + +10. Security Considerations + + The entirety of this document concerns techniques and recommendations + for generating unguessable "random" quantities for use as passwords, + cryptographic keys, and similar security uses. + + + + + + + + +Eastlake, Crocker & Schiller [Page 27] + +RFC 1750 Randomness Recommendations for Security December 1994 + + +References + + [ASYMMETRIC] - Secure Communications and Asymmetric Cryptosystems, + edited by Gustavus J. Simmons, AAAS Selected Symposium 69, Westview + Press, Inc. + + [BBS] - A Simple Unpredictable Pseudo-Random Number Generator, SIAM + Journal on Computing, v. 15, n. 2, 1986, L. Blum, M. Blum, & M. Shub. + + [BRILLINGER] - Time Series: Data Analysis and Theory, Holden-Day, + 1981, David Brillinger. + + [CRC] - C.R.C. Standard Mathematical Tables, Chemical Rubber + Publishing Company. + + [CRYPTO1] - Cryptography: A Primer, A Wiley-Interscience Publication, + John Wiley & Sons, 1981, Alan G. Konheim. + + [CRYPTO2] - Cryptography: A New Dimension in Computer Data Security, + A Wiley-Interscience Publication, John Wiley & Sons, 1982, Carl H. + Meyer & Stephen M. Matyas. + + [CRYPTO3] - Applied Cryptography: Protocols, Algorithms, and Source + Code in C, John Wiley & Sons, 1994, Bruce Schneier. + + [DAVIS] - Cryptographic Randomness from Air Turbulence in Disk + Drives, Advances in Cryptology - Crypto '94, Springer-Verlag Lecture + Notes in Computer Science #839, 1984, Don Davis, Ross Ihaka, and + Philip Fenstermacher. + + [DES] - Data Encryption Standard, United States of America, + Department of Commerce, National Institute of Standards and + Technology, Federal Information Processing Standard (FIPS) 46-1. + - Data Encryption Algorithm, American National Standards Institute, + ANSI X3.92-1981. + (See also FIPS 112, Password Usage, which includes FORTRAN code for + performing DES.) + + [DES MODES] - DES Modes of Operation, United States of America, + Department of Commerce, National Institute of Standards and + Technology, Federal Information Processing Standard (FIPS) 81. + - Data Encryption Algorithm - Modes of Operation, American National + Standards Institute, ANSI X3.106-1983. + + [D-H] - New Directions in Cryptography, IEEE Transactions on + Information Technology, November, 1976, Whitfield Diffie and Martin + E. Hellman. + + + + +Eastlake, Crocker & Schiller [Page 28] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + [DoD] - Password Management Guideline, United States of America, + Department of Defense, Computer Security Center, CSC-STD-002-85. + (See also FIPS 112, Password Usage, which incorporates CSC-STD-002-85 + as one of its appendices.) + + [GIFFORD] - Natural Random Number, MIT/LCS/TM-371, September 1988, + David K. Gifford + + [KNUTH] - The Art of Computer Programming, Volume 2: Seminumerical + Algorithms, Chapter 3: Random Numbers. Addison Wesley Publishing + Company, Second Edition 1982, Donald E. Knuth. + + [KRAWCZYK] - How to Predict Congruential Generators, Journal of + Algorithms, V. 13, N. 4, December 1992, H. Krawczyk + + [MD2] - The MD2 Message-Digest Algorithm, RFC1319, April 1992, B. + Kaliski + [MD4] - The MD4 Message-Digest Algorithm, RFC1320, April 1992, R. + Rivest + [MD5] - The MD5 Message-Digest Algorithm, RFC1321, April 1992, R. + Rivest + + [PEM] - RFCs 1421 through 1424: + - RFC 1424, Privacy Enhancement for Internet Electronic Mail: Part + IV: Key Certification and Related Services, 02/10/1993, B. Kaliski + - RFC 1423, Privacy Enhancement for Internet Electronic Mail: Part + III: Algorithms, Modes, and Identifiers, 02/10/1993, D. Balenson + - RFC 1422, Privacy Enhancement for Internet Electronic Mail: Part + II: Certificate-Based Key Management, 02/10/1993, S. Kent + - RFC 1421, Privacy Enhancement for Internet Electronic Mail: Part I: + Message Encryption and Authentication Procedures, 02/10/1993, J. Linn + + [SHANNON] - The Mathematical Theory of Communication, University of + Illinois Press, 1963, Claude E. Shannon. (originally from: Bell + System Technical Journal, July and October 1948) + + [SHIFT1] - Shift Register Sequences, Aegean Park Press, Revised + Edition 1982, Solomon W. Golomb. + + [SHIFT2] - Cryptanalysis of Shift-Register Generated Stream Cypher + Systems, Aegean Park Press, 1984, Wayne G. Barker. + + [SHS] - Secure Hash Standard, United States of American, National + Institute of Science and Technology, Federal Information Processing + Standard (FIPS) 180, April 1993. + + [STERN] - Secret Linear Congruential Generators are not + Cryptograhically Secure, Proceedings of IEEE STOC, 1987, J. Stern. + + + +Eastlake, Crocker & Schiller [Page 29] + +RFC 1750 Randomness Recommendations for Security December 1994 + + + [VON NEUMANN] - Various techniques used in connection with random + digits, von Neumann's Collected Works, Vol. 5, Pergamon Press, 1963, + J. von Neumann. + +Authors' Addresses + + Donald E. Eastlake 3rd + Digital Equipment Corporation + 550 King Street, LKG2-1/BB3 + Littleton, MA 01460 + + Phone: +1 508 486 6577(w) +1 508 287 4877(h) + EMail: dee@lkg.dec.com + + + Stephen D. Crocker + CyberCash Inc. + 2086 Hunters Crest Way + Vienna, VA 22181 + + Phone: +1 703-620-1222(w) +1 703-391-2651 (fax) + EMail: crocker@cybercash.com + + + Jeffrey I. Schiller + Massachusetts Institute of Technology + 77 Massachusetts Avenue + Cambridge, MA 02139 + + Phone: +1 617 253 0161(w) + EMail: jis@mit.edu + + + + + + + + + + + + + + + + + + + + +Eastlake, Crocker & Schiller [Page 30] + |