diff options
Diffstat (limited to 'crypto/heimdal/doc/standardisation/rfc1750.txt')
| -rw-r--r-- | crypto/heimdal/doc/standardisation/rfc1750.txt | 1683 |
1 files changed, 0 insertions, 1683 deletions
diff --git a/crypto/heimdal/doc/standardisation/rfc1750.txt b/crypto/heimdal/doc/standardisation/rfc1750.txt deleted file mode 100644 index 56d478c..0000000 --- a/crypto/heimdal/doc/standardisation/rfc1750.txt +++ /dev/null @@ -1,1683 +0,0 @@ - - - - - - -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] - |
