Randomness Recommendations for Security
RFC 1750

• Status
• IESG evaluation record
• IESG writeups
• Email expansions
• History

• Versions
• 01

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