Randomness Requirements for Security
RFC 4086

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

• Versions
• 10

Network Working Group                                   D. Eastlake, 3rd
Request for Comments: 4086                         Motorola Laboratories
BCP: 106                                                     J. Schiller
Obsoletes: 1750                                                      MIT
Category: Best Current Practice                               S. Crocker
                                                               June 2005

                  Randomness Requirements for Security

Status of This Memo

   This document specifies an Internet Best Current Practices for the
   Internet Community, and requests discussion and suggestions for
   improvements.  Distribution of this memo is unlimited.

Copyright Notice

   Copyright (C) The Internet Society (2005).

Abstract

   Security systems are built on 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.  A sophisticated attacker may find it easier to reproduce
   the environment that produced the secret quantities and to search the
   resulting small set of possibilities than to locate the quantities in
   the whole of the potential number space.

   Choosing random quantities to foil a resourceful and motivated
   adversary is surprisingly difficult.  This document points out many
   pitfalls in using poor entropy sources or traditional pseudo-random
   number generation techniques for generating 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 applications.

Eastlake, et al.            Standards Track                     [Page 1]
RFC 4086         Randomness Requirements for Security          June 2005

Table of Contents

   1. Introduction and Overview .......................................3
   2. General Requirements ............................................4
   3. Entropy Sources .................................................7
      3.1. Volume Required ............................................7
      3.2. Existing Hardware Can Be Used For Randomness ...............8
           3.2.1. Using Existing Sound/Video Input ....................8
           3.2.2. Using Existing Disk Drives ..........................8
      3.3. Ring Oscillator Sources ....................................9
      3.4. Problems with Clocks and Serial Numbers ...................10
      3.5. Timing and Value of External Events .......................11
      3.6. Non-hardware Sources of Randomness ........................12
   4. De-skewing .....................................................12
      4.1. Using Stream Parity to De-Skew ............................13
      4.2. Using Transition Mappings to De-Skew ......................14
      4.3. Using FFT to De-Skew ......................................15
      4.4. Using Compression to De-Skew ..............................15
   5. Mixing .........................................................16
      5.1. A Trivial Mixing Function .................................17
      5.2. Stronger Mixing Functions .................................18
      5.3. Using S-Boxes for Mixing ..................................19
      5.4. Diffie-Hellman as a Mixing Function .......................19
      5.5. Using a Mixing Function to Stretch Random Bits ............20
      5.6. Other Factors in Choosing a Mixing Function ...............20
   6. Pseudo-random Number Generators ................................21
      6.1. Some Bad Ideas ............................................21
           6.1.1. The Fallacy of Complex Manipulation ................21
           6.1.2. The Fallacy of Selection from a Large Database .....22
           6.1.3. Traditional Pseudo-random Sequences ................23
      6.2. Cryptographically Strong Sequences ........................24
           6.2.1. OFB and CTR Sequences ..............................25
           6.2.2. The Blum Blum Shub Sequence Generator ..............26
      6.3. Entropy Pool Techniques ...................................27
   7. Randomness Generation Examples and Standards ...................28
      7.1. Complete Randomness Generators ............................28
           7.1.1. US DoD Recommendations for Password Generation .....28
           7.1.2. The /dev/random Device .............................29
           7.1.3. Windows CryptGenRandom .............................30
      7.2. Generators Assuming a Source of Entropy ...................31
           7.2.1. X9.82 Pseudo-Random Number Generation ..............31