RFC 1750 (rfc1750) - Page 2 of 30

Randomness Recommendations for Security

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