Tech-invite   3GPPspecs   RFCs   SIP   Search in Tech-invite

in Index   Prev   Next

RFC 4086

Randomness Requirements for Security

Pages: 48
Group: ~sec
BCP 106
Obsoletes:  1750
Part 1 of 2 – Pages 1 to 21
None   None   Next

Top   ToC   RFC4086 - Page 1
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).


   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.
Top   ToC   RFC4086 - Page 2
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
           7.2.2. X9.17 Key Generation ...............................33
           7.2.3. DSS Pseudo-random Number Generation ................34
   8. Examples of Randomness Required ................................34
      8.1. Password Generation .......................................35
      8.2. A Very High Security Cryptographic Key ....................36
   9. Conclusion .....................................................38
  10. Security Considerations ........................................38
Top   ToC   RFC4086 - Page 3
  11. Acknowledgments ................................................39
  Appendix A: Changes from RFC 1750 ..................................40
  Informative References .............................................41

1.  Introduction and Overview

   Software cryptography is coming into wider use, although there is a
   long way to go until it becomes pervasive.  Systems such as SSH,
   IPSEC, TLS, S/MIME, PGP, DNSSEC, and Kerberos are maturing and
   becoming a part of the network landscape [SSH] [IPSEC] [TLS] [S/MIME]
   [MAIL_PGP*] [DNSSEC*].  For comparison, when the previous version of
   this document [RFC1750] was issued in 1994, the only Internet
   cryptographic security specification in the IETF was the Privacy
   Enhanced Mail protocol [MAIL_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.

   The lack of generally available facilities for generating such random
   numbers (that is, the lack of general availability of truly
   unpredictable sources) forms 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, this is a very real problem.

   Note that the requirement is for data that an adversary has a very
   low probability of guessing or determining.  This can easily fail if
   pseudo-random data is used that meets only traditional statistical
   tests for randomness, or that is based on limited-range sources such
   as clocks.  Sometimes such pseudo-random quantities can be guessed by
   an adversary searching through an embarrassingly small space of

   This Best Current Practice document describes techniques for
   producing random quantities that will be resistant to 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 applications.
Top   ToC   RFC4086 - Page 4
2.  General Requirements

   Today, a commonly encountered randomness requirement is to pick a
   user password, usually a simple character string.  Obviously, a
   password that can be guessed 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 of ordinary words.  But this affects only
   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.

   There are even TCP/IP protocol uses for randomness in picking initial
   sequence numbers [RFC1948].

   Generally speaking, the above examples also illustrate two different
   types of random quantities that may be wanted.  In the case of
   human-usable passwords, the only important characteristic is that
   they be unguessable.  It is not important that they may be composed
   of ASCII characters, so the top bit of every byte is zero, for
   example.  On the other hand, for fixed length keys and the like, one
   normally wants quantities that appear to be truly random, that is,
   quantities whose bits will pass statistical randomness tests.

   In some cases, such as the use of symmetric encryption with the one-
   time pads or an algorithm like the US Advanced Encryption Standard
   [AES], the parties who wish to communicate confidentially and/or with
   authentication must all know the same secret key.  In other cases,
   where asymmetric or "public key" cryptographic techniques are used,
   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, and knowledge of the public key is of no help to
   an adversary [ASYMMETRIC].  See general references [SCHNEIER,

   The frequency and volume of the requirement for random quantities
   differs greatly for different cryptographic systems.  With pure RSA,
   random quantities are required only when a new key pair is generated;
   thereafter, any number of messages can be signed without a further
   need for randomness.  The public key Digital Signature Algorithm
   devised by the US National Institute of Standards and Technology
   (NIST) requires good random numbers for each signature [DSS].  And
Top   ToC   RFC4086 - Page 5
   encrypting with a one-time pad (in principle the strongest possible
   encryption technique) requires randomness of equal volume to all the
   messages to be processed.  See general references [SCHNEIER,

   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 an
   information-theoretic sense [SHANNON].  This depends on the number of
   different secret values possible and the probability of each value,
   as follows:

        Bits of information =  \     - p   * log  ( p  )
                               /        i       2    i

   where i counts from 1 to the number of possible secret values and p
   sub i is the probability of the value numbered i.  (Because 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 have to try, on the
   average, 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
   an adversary can know to be impossible or of low probability can be
   initially ignored by the adversary, who will search through the more
   probable values first.

   For example, consider a cryptographic system that uses 128-bit keys.
   If these keys are derived 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 2^128 keys as may at first
   appear to be the case.  Only 8 bits of "information" are in these
   128-bit keys.
Top   ToC   RFC4086 - Page 6
   While the above analysis is correct on average, it can be misleading
   in some cases for cryptographic analysis where what is really
   important is the work factor for an adversary.  For example, assume
   that there is a pseudo-random number generator generating 128-bit
   keys, as in the previous paragraph, but that it generates zero half
   of the time and a random selection from the remaining 2^128 - 1
   values the rest of the time.  The Shannon equation above says that
   there are 64 bits of information in one of these key values, but an
   adversary, simply by trying the value zero, can break the security of
   half of the uses, albeit a random half.  Thus, for cryptographic
   purposes, it is also useful to look at other measures, such as min-
   entropy, defined as

        Min-entropy =  - log  ( maximum ( p  ) )

   where i is as above.  Using this equation, we get 1 bit of min-
   entropy for our new hypothetical distribution, as opposed to 64 bits
   of classical Shannon entropy.

   A continuous spectrum of entropies, sometimes called Renyi entropy,
   has been defined, specified by the parameter r.  Here r = 1 is
   Shannon entropy and r = infinity is min-entropy.  When r = zero, it
   is just log (n), where n is the number of non-zero probabilities.
   Renyi entropy is a non-increasing function of r, so min-entropy is
   always the most conservative measure of entropy and usually the best
   to use for cryptographic evaluation [LUBY].

   Statistically tested randomness in the traditional sense is NOT the
   same as the unpredictability required for security use.

   For example, the use of a widely available constant sequence, such as
   the random table from the CRC Standard Mathematical Tables, is very
   weak against an adversary.  An adversary who learns of or guesses it
   can easily break all security, future and past, based on the sequence
   [CRC].  As another example, using AES with a constant key to encrypt
   successive integers such as 1, 2, 3, ... will produce output that
   also has excellent statistical randomness properties but is
   predictable.  On the other hand, taking successive rolls of a six-
   sided die and encoding the resulting values in ASCII would produce
   statistically poor output with a substantial unpredictable component.
   So note that passing or failing statistical tests doesn't reveal
   whether something is unpredictable or predictable.
Top   ToC   RFC4086 - Page 7
3.  Entropy Sources

   Entropy sources tend to be very implementation dependent.  Once one
   has gathered sufficient entropy, it can be used as the seed to
   produce the required amount of cryptographically strong pseudo-
   randomness, as described in Sections 6 and 7, after being de-skewed
   or mixed as necessary, as described in Sections 4 and 5.

   Is there any hope for true, strong, portable randomness in the
   future?  There might be.  All that's needed is a physical source of
   unpredictable numbers.

   Thermal noise (sometimes called Johnson noise in integrated circuits)
   or a radioactive decay source and a fast, free-running oscillator
   would do the trick directly [GIFFORD].  This is a trivial amount of
   hardware, and it could easily be included as a standard part of a
   computer system's architecture.  Most audio (or video) input devices
   are usable [TURBID].  Furthermore, any system with a spinning disk or
   ring oscillator and a stable (crystal) time source or the like has an
   adequate source of randomness ([DAVIS] and Section 3.3).  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.

   ANSI X9 is currently developing a standard that includes a part
   devoted to entropy sources.  See Part 2 of [X9.82].

3.1.  Volume Required

   How much unpredictability is needed?  Is it possible to quantify the
   requirement in terms of, say, number of random bits per second?

   The answer is that not very much is needed.  For AES, the key can be
   128 bits, and, as we show in an example in Section 8, even the
   highest security system is unlikely to require strong keying material
   of much over 200 bits.  If a series of keys is needed, they can be
   generated from a strong random seed (starting value) using a
   cryptographically strong sequence, as explained in Section 6.2.  A
   few hundred random bits generated at start-up or once a day is enough
   if such techniques are used.  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 most high-security
   applications to wait 200 seconds occasionally.

   These numbers are trivial to achieve.  It could be achieved by a
   person repeatedly tossing a coin, and almost any hardware based
   process is likely to be much faster.
Top   ToC   RFC4086 - Page 8
3.2.  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.

3.2.1.  Using Existing Sound/Video Input

   Many computers are built with inputs that digitize some real-world
   analog source, such as sound from a microphone or video input from a
   camera.  The "input" from a sound digitizer with no source plugged in
   or from a camera with the lens cap on is essentially thermal noise.
   If the system has enough gain to detect anything, such input can
   provide reasonably high quality random bits.  This method is
   extremely dependent on the hardware implementation.

   For example, on some UNIX-based systems, one can read from the
   /dev/audio device with nothing plugged into the microphone jack or
   with the microphone receiving only low level background noise.  Such
   data is essentially random noise, although it should not be trusted
   without some checking, in case of hardware failure, and it will have
   to be de-skewed.

   Combining this approach with compression to de-skew (see Section 4),
   one can generate a huge amount of medium-quality random data with the
   UNIX-style command line:

        cat /dev/audio | compress - >random-bits-file

   A detailed examination of this type of randomness source appears in

3.2.2.  Using Existing Disk Drives

   Disk drives have small random fluctuations in their rotational speed
   due to chaotic air turbulence [DAVIS, Jakobsson].  The addition of
   low-level disk seek-time instrumentation produces a series of
   measurements that contain this randomness.  Such data is usually
   highly correlated, so significant processing is needed, as described
   in Section 5.2 below.  Nevertheless, experimentation a decade ago
   showed that, with such processing, even slow disk drives on the
   slower computers of that day could easily produce 100 bits a minute
   or more of excellent random data.

   Every increase in processor speed, which increases the resolution
   with which disk motion can be timed or increases the rate of disk
   seeks, increases the rate of random bit generation possible with this
   technique.  At the time of this paper and with modern hardware, a
   more typical rate of random bit production would be in excess of
Top   ToC   RFC4086 - Page 9
   10,000 bits a second.  This technique is used in random number
   generators included in many operating system libraries.

   Note: the inclusion of cache memories in disk controllers has little
   effect on this technique if very short seek times, which represent
   cache hits, are simply ignored.

3.3.  Ring Oscillator Sources

   If an integrated circuit is being designed or field-programmed, an
   odd number of gates can be connected in series to produce a free-
   running ring oscillator.  By sampling a point in the ring at a fixed
   frequency (for example, one determined by a stable crystal
   oscillator), some amount of entropy can be extracted due to
   variations in the free-running oscillator timing.  It is possible to
   increase the rate of entropy by XOR'ing sampled values from a few
   ring oscillators with relatively prime lengths.  It is sometimes
   recommended that an odd number of rings be used so that, even if the
   rings somehow become synchronously locked to each other, there will
   still be sampled bit transitions.  Another possible source to sample
   is the output of a noisy diode.

   Sampled bits from such sources will have to be heavily de-skewed, as
   disk rotation timings must be (see Section 4).  An engineering study
   would be needed to determine the amount of entropy being produced
   depending on the particular design.  In any case, these can be good
   sources whose cost is a trivial amount of hardware by modern

   As an example, IEEE 802.11i suggests the circuit below, with due
   attention in the design to isolation of the rings from each other and
   from clocked circuits to avoid undesired synchronization, etc., and
   with extensive post processing [IEEE_802.11i].
Top   ToC   RFC4086 - Page 10
             |\     |\                |\
         +-->| >0-->| >0-- 19 total --| >0--+-------+
         |   |/     |/                |/    |       |
         |                                  |       |
         +----------------------------------+       V
             |\     |\                |\         |     | output
         +-->| >0-->| >0-- 23 total --| >0--+--->| XOR |------>
         |   |/     |/                |/    |    |     |
         |                                  |    +-----+
         +----------------------------------+      ^ ^
                                                   | |
             |\     |\                |\           | |
         +-->| >0-->| >0-- 29 total --| >0--+------+ |
         |   |/     |/                |/    |        |
         |                                  |        |
         +----------------------------------+        |
             Other randomness, if available ---------+

3.4.  Problems with Clocks and Serial Numbers

   Computer clocks and 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 of 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
   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

   Use of a hardware serial number (such as an Ethernet MAC 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 may be easily
   guessable based on approximate date of manufacture or other data.
Top   ToC   RFC4086 - Page 11
   For example, it is likely that a company that manufactures both
   computers and Ethernet adapters will, at least internally, use its
   own adapters, which significantly limits the range of built-in

   Problems such as those described above make the production of code to
   generate unpredictable quantities difficult if the code is to be
   ported across a variety of computer platforms and systems.

3.5.  Timing and Value 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, input
   such as key strokes is 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 for sampling timing
   details.  This makes it hard to use this technique to build standard
   software intended for distribution to a large range of machines.

   The amount of mouse movement and the actual key strokes are usually
   easier to access than timings, but they may yield less
   unpredictability because the user may provide highly repetitive

   Other external events, such as network packet arrival times and
   lengths, can also be used, but only with great care.  In particular,
   the possibility of manipulation of such network traffic measurements
   by an adversary and the lack of history at system start-up must be
   carefully considered.  If this input is subject to manipulation, it
   must not be trusted as a source of entropy.

   In principle, almost any external sensor, such as raw radio reception
   or temperature sensing in appropriately equipped computers, can be
   used.  But in each case, careful consideration must be given to how
   much this data is subject to adversarial manipulation and to how much
   entropy it can actually provide.

   The above techniques are quite powerful against attackers that have
   no access to the quantities being measured.  For example, these
   techniques would be powerful against offline attackers who had no
   access to one's environment and who were trying to crack one's random
   seed after the fact.  In all cases, the more accurately one can
   measure the timing or value of an external sensor, the more rapidly
   one can generate bits.
Top   ToC   RFC4086 - Page 12
3.6.  Non-hardware Sources of Randomness

   The best source of input entropy would be a hardware-based random
   source such as ring oscillators, disk drive timing, thermal noise, or
   radioactive decay.  However, if none of these is available, there are
   other possibilities.  These include system clocks, system or
   input/output buffers, user/system/hardware/network serial numbers or
   addresses and timing, and user input.  Unfortunately, each of these
   sources can produce very limited or predictable values under some

   Some of the sources listed above would be quite strong on multi-user
   systems, where each user of the system is in essence a source of
   randomness.  However, on a small single-user or embedded system,
   especially at start-up, it might be possible for an adversary to
   assemble a similar configuration.  This could give the adversary
   inputs to the mixing process that were well-enough correlated to
   those used originally 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.  The
   timing and content of requested "random" user keystrokes can yield
   hundreds of random bits, but conservative assumptions need to be
   made.  For example, one reasonably conservative assumption would be
   that an inter-keystroke interval provides at most a few bits of
   randomness, but only when the interval is unique in the sequence of
   intervals up to that point.  A similar assumption would be that a key
   code provides a few bits of randomness, but only when the code is
   unique in the sequence.  Thus, an interval or key code that
   duplicated a previous value would be assumed to provide no additional
   randomness.  The results of mixing these timings with typed
   characters could be further combined with clock values and other

   This strategy may make practical portable code for producing 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, or embedded 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.

4.  De-skewing

   Is there any specific requirement on the shape of the distribution of
   quantities gathered for the entropy to produce the random numbers?
   The good news is that the distribution need not be uniform.  All that
   is needed to bound performance is a conservative estimate of how
Top   ToC   RFC4086 - Page 13
   non-uniform it is.  Simple techniques to de-skew a bit stream are
   given below, and stronger cryptographic techniques are described in
   Section 5.2.

4.1.  Using Stream Parity to De-Skew

   As a simple but not particularly practical example, consider taking a
   sufficiently long string of bits and mapping 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 that it is trivial to implement in hardware.

   The following analysis gives the number of bits that must be sampled:

   Suppose that the ratio of ones to zeros is ( 0.5 + E ) to
   ( 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 respective 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 )  )

                         N            N
        1/2 * ( ( p + q )  - ( p - q )  ).

   (Which formula corresponds to the probability that 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

        1/2 * [1 + (2E)  ]

        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, e.g., then
Top   ToC   RFC4086 - Page 14
        ( 0.5 + ( 0.5 * (2E)  ) )  <  0.5 + d.

   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 N of the string that 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.  But, as we shall see in section 5.2,
   there are much stronger techniques that extract more of the available

4.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.  One
   could then discard any 00 or 11 pairs found, interpret 01 as a 0 and
   10 as a 1.  Assume that the probability of a 1 is 0.5+E and that the
   probability of a 0 is 0.5-E, where E is the eccentricity of the
   source as described in the previous section.  Then the probability of
   each pair is shown in the following table:

            | 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  |
Top   ToC   RFC4086 - Page 15
   This technique will completely eliminate any bias but requires 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).

   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 uncorrelated, i.e., that the bits come from
   identical independent distributions.  If alternate bits are 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 misread slightly so that overlapping successive bits
   pairs were used instead of non-overlapping pairs, the statistical
   analysis given would be the same.  However, instead of providing an
   unbiased, uncorrelated series of random 1s and 0s, it would produce a
   totally predictable sequence of exactly alternating 1s and 0s.

4.3.  Using FFT to De-Skew

   When real-world data consists of strongly correlated bits, it may
   still contain useful amounts of entropy.  This entropy can be
   extracted through various transforms, the most powerful of which are
   described in section 5.2 below.

   Using the Fourier transform of the data or its optimized variant, the
   FFT, is interesting primarily for theoretical reasons.  It can be
   shown that this technique will discard strong correlations.  If
   adequate data is processed and if remaining correlations decay,
   spectral lines that approach statistical independence and normally
   distributed randomness can be produced [BRILLINGER].

4.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 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 as 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.
   Therefore, the shorter sequences must be de-skewed relative to the
Top   ToC   RFC4086 - Page 16
   However, many compression techniques add a somewhat predictable
   preface to their output stream and may insert a similar sequence
   periodically in their output or otherwise introduce subtle patterns
   of their own.  They should be considered only rough techniques
   compared to those described in Section 5.2.  At a minimum, the
   beginning of the compressed sequence should be skipped and only later
   bits should used for applications requiring roughly-random bits.

5.  Mixing

   What is the best overall strategy for obtaining unguessable random
   numbers in the absence of a strong, reliable hardware entropy source?
   It is to obtain input from a number of uncorrelated sources and to
   mix them with a strong mixing function.  Such a function will
   preserve the entropy present in any of the sources, even if other
   quantities being combined happen to be fixed or easily guessable (low
   entropy).  This approach may be advisable even with a good hardware
   source, as hardware can also fail.  However, this should be weighed
   against a possible increase in the chance of overall failure due to
   added software complexity.

   Once one has used good sources, such as some of those listed in
   Section 3, and mixed them as described in this section, one has a
   strong seed.  This can then be used to produce large quantities of
   cryptographically strong material as described in Sections 6 and 7.

   A strong mixing function is one that combines inputs and produces an
   output in which 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 or which has a somewhat predictable pattern to a
   shorter stream which is more random, as discussed in Section 4.  This
   is simply another case where a strong mixing function is desired, to
   mix the input bits and produce a smaller number of output bits.  The
   technique given in Section 4.1, using the parity of a number of bits,
   is simply the result of successively XORing them.  This 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 5.2.  See also [NASLUND].
Top   ToC   RFC4086 - Page 17
5.1.  A Trivial Mixing Function

   For expository purposes we describe a trivial example for single bit
   inputs using the Exclusive Or (XOR) function.  This function 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
   provides 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 are.  If we assume an "eccentricity" E as defined in Section
   4.1 above, then the output eccentricity relates to the input
   eccentricity 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 in which 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, note 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
Top   ToC   RFC4086 - Page 18
   than a minute.  Yet if they were both sampled and combined with XOR,
   the result would be zero most of the time.

5.2.  Stronger Mixing Functions

   The US Government Advanced Encryption Standard [AES] is an example of
   a strong mixing function for multiple bit quantities.  It takes up to
   384 bits of input (128 bits of "data" and 256 bits of "key") and
   produces 128 bits of output, each of which is dependent on a complex
   non-linear function of all input bits.  Other encryption functions
   with this characteristic, such as [DES], can also be used by
   considering them to mix all of their key and data input bits.

   Another good family of mixing functions is the "message digest" or
   hashing functions such as the US Government Secure Hash Standards
   [SHA*] and the MD4, MD5 [MD4, MD5] series.  These functions all take
   a practically unlimited amount of input and produce a relatively
   short fixed-length output mixing all the input bits.  The MD* series
   produces 128 bits of output, SHA-1 produces 160 bits, and other SHA
   functions produce up to 512 bits.

   Although the message digest functions are designed for variable
   amounts of input, AES and other encryption functions can also be used
   to combine any number of inputs.  If 128 bits of output is adequate,
   the inputs can be packed into a 128-bit data quantity and successive
   AES "keys", padding with zeros if needed; the quantity is then
   successively encrypted by the "keys" using AES in Electronic Codebook
   Mode.  Alternatively, the input could be packed into one 128-bit key
   and multiple data blocks and a CBC-MAC could be calculated [MODES].

   More complex mixing should be used if more than 128 bits of output
   are needed and one wants to employ AES (but note that it is
   absolutely impossible to get more bits of "randomness" out than are
   put in).  For example, suppose that inputs are packed into three
   quantities, A, B, and C.  One may use AES to encrypt A with B and
   then with C as keys to produce the first 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.  The
   same can be done with the hash functions, hashing various subsets of
   the input data or different copies of the input data with different
   prefixes and/or suffixes to produce multiple outputs.

   For an example of using a strong mixing function, reconsider the case
   of a string of 308 bits, each of which is biased 99% toward zero.
   The parity technique given in Section 4.1 reduces 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
Top   ToC   RFC4086 - Page 19
   308-bit skewed sequence contains over 5 bits of information.  Thus,
   hashing it with SHA-1 and taking the bottom 5 bits of the result
   would yield 5 unbiased random bits and not the single bit given by
   calculating the parity of the string.  Alternatively, for some
   applications, you could use the entire hash output to retain almost
   all of the 5+ bits of entropy in a 160-bit quantity.

5.3.  Using S-Boxes for Mixing

   Many modern block encryption functions, including DES and AES,
   incorporate modules known as S-Boxes (substitution boxes).  These
   produce a smaller number of outputs from a larger number of inputs
   through a complex non-linear mixing function that has the effect of
   concentrating limited entropy from the inputs into the output.

   S-Boxes sometimes incorporate bent Boolean functions (functions of an
   even number of bits producing one output bit with maximum non-
   linearity).  Looking at the output for all input pairs differing in
   any particular bit position, exactly half the outputs are different.
   An S-Box in which each output bit is produced by a bent function such
   that any linear combination of these functions is also a bent
   function is called a "perfect S-Box".

   S-boxes and various repeated applications or cascades of such boxes
   can be used for mixing [SBOX1, SBOX2].

5.4.  Diffie-Hellman as a Mixing Function

   Diffie-Hellman exponential key exchange is a technique that yields a
   shared secret between two parties.  It can be computationally
   infeasible for a third party to determine this secret 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 the parties [D-H].

   If these initial quantities are random and uncorrelated, then the
   shared secret combines their entropy but, of course, can not produce
   more randomness than the size of the shared secret generated.

   Although this is true if the Diffie-Hellman computation is performed
   privately, an adversary who can observe either of the public keys and
   knows the modulus being used need only search through the space of
   the other secret key in order to be able to calculate the shared
   secret [D-H].  So, conservatively, it would be best to consider
   public Diffie-Hellman to produce a quantity whose guessability
   corresponds to the worse of the two inputs.  Because of this and the
   fact that Diffie-Hellman is computationally intensive, its use as a
   mixing function is not recommended.
Top   ToC   RFC4086 - Page 20
5.5.  Using a Mixing Function to Stretch Random Bits

   Although it is not necessary for a mixing function to produce the
   same or fewer output bits than its inputs, mixing bits cannot
   "stretch" the amount of random unpredictability present in the
   inputs.  Thus, four inputs of 32 bits each, in which there are 12
   bits worth of unpredictability (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 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 last table in Section 5.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.

5.6.  Other Factors in Choosing a Mixing Function

   For local use, AES has the advantages that it has been widely tested
   for flaws, is reasonably efficient in software, and is widely
   documented and implemented with hardware and software implementations
   available all over the world including open source code.  The SHA*
   family have had a little less study and tend to require more CPU
   cycles than AES but there is no reason to believe they are flawed.
   Both SHA* and MD5 were derived from the earlier MD4 algorithm.  They
   all have source code available [SHA*, MD4, MD5].  Some signs of
   weakness have been found in MD4 and MD5.  In particular, MD4 has only
   three rounds and there are several independent breaks of the first
   two or last two rounds.  And some collisions have been found in MD5

   AES was selected by a robust, public, and international process.  It
   and SHA* have been vouched for by the US National Security Agency
   (NSA) on the basis of criteria that mostly remain secret, as was DES.
   While this has been 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.  There has been no announcement
   of a concealed or special weakness being found in DES.  It is likely
   that the NSA modifications to MD4 to produce the SHA algorithms
   similarly strengthened these algorithms, possibly against threats not
   yet known in the public cryptographic community.
Top   ToC   RFC4086 - Page 21
   Where input lengths are unpredictable, hash algorithms are more
   convenient to use than block encryption algorithms since they are
   generally designed to accept variable length inputs.  Block
   encryption algorithms generally require an additional padding
   algorithm to accommodate inputs that are not an even multiple of the
   block size.

   As of the time of this document, the authors know of no patent claims
   to the basic AES, DES, SHA*, MD4, and MD5 algorithms other than
   patents for which an irrevocable royalty free license has been
   granted to the world.  There may, of course, be essential patents of
   which the authors are unaware or patents on implementations or uses
   or other relevant patents issued or to be issued.

(page 21 continued on part 2)

Next Section