Randomness Recommendations for Security
RFC 1750
Document | Type |
RFC - Informational
(December 1994; No errata)
Obsoleted by RFC 4086
Was draft-ietf-security-randomness (individual)
|
|
---|---|---|---|
Authors | Steve Crocker , Donald Eastlake , Jeffrey Schiller | ||
Last updated | 2013-03-02 | ||
Stream | Legacy stream | ||
Formats | plain text html pdf htmlized (tools) htmlized bibtex | ||
Stream | Legacy state | (None) | |
Consensus Boilerplate | Unknown | ||
RFC Editor Note | (None) | ||
IESG | IESG state | RFC 1750 (Informational) | |
Telechat date | |||
Responsible AD | (None) | ||
Send notices to | (None) |
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................................. 24Show full document text