rfc1750.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 1,421 行 · 第 1/5 页

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
   8.2 A Very High Security Cryptographic Key............... 25
   8.2.1 Effort per Key Trial............................... 25
   8.2.2 Meet in the Middle Attacks......................... 26
   8.2.3 Other Considerations............................... 26
   9. Conclusion............................................ 27
   10. Security Considerations.............................. 27
   References............................................... 28
   Authors' Addresses....................................... 30

1. Introduction

   Software cryptography is coming into wider use.  Systems like
   Kerberos, PEM, PGP, etc. are maturing and becoming a part of the
   network landscape [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.

   For the present, the lack of generally available facilities for
   generating such unpredictable numbers is 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, the only safe strategy so far has been to force
   the local installation to supply a suitable routine to generate
   random numbers.  To say the least, this is an awkward, error-prone
   and unpalatable solution.

   It is important to keep in mind that the requirement is for data that
   an adversary has a very low probability of guessing or determining.
   This will fail if pseudo-random data is used which only meets
   traditional statistical tests for randomness or which is based on
   limited range sources, such as clocks.  Frequently such random
   quantities are determinable by an adversary searching through an
   embarrassingly small space of possibilities.

   This informational document suggests techniques for producing random
   quantities that will be resistant to such 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



Eastlake, Crocker & Schiller                                    [Page 3]

RFC 1750        Randomness Recommendations for Security    December 1994


   applications.

2. Requirements

   Probably the most commonly encountered randomness requirement today
   is the user password. This is usually a simple character string.
   Obviously, if a password can be guessed, it 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 on ordinary
   words.  But this only affects 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.

   In some cases, such as the use of symmetric encryption with the one
   time pads [CRYPTO*] or the US Data Encryption Standard [DES], the
   parties who wish to communicate confidentially and/or with
   authentication must all know the same secret key.  In other cases,
   using what are called asymmetric or "public key" cryptographic
   techniques, 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 [ASYMMETRIC, CRYPTO*].

   The frequency and volume of the requirement for random quantities
   differs greatly for different cryptographic systems.  Using pure RSA
   [CRYPTO*], random quantities are required when the key pair is
   generated, but thereafter any number of messages can be signed
   without any further need for randomness.  The public key Digital
   Signature Algorithm that has been proposed by the US National
   Institute of Standards and Technology (NIST) requires good random
   numbers for each signature.  And encrypting with a one time pad, in
   principle the strongest possible encryption technique, requires a
   volume of randomness equal to all the messages to be processed.

   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 the information
   theoretic sense [SHANNON].  This depends on the number of different



Eastlake, Crocker & Schiller                                    [Page 4]

RFC 1750        Randomness Recommendations for Security    December 1994


   secret values possible and the probability of each value as follows:

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

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

   For example, consider a cryptographic system that uses 56 bit keys.
   If these 56 bit keys are derived by 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 the 2^56 keys that
   may at first appear to be the case. Only 8 bits of "information" are
   in these 56 bit keys.

3. Traditional Pseudo-Random Sequences

   Most traditional sources of random numbers use deterministic sources
   of "pseudo-random" numbers.  These typically start with a "seed"
   quantity and use numeric or logical operations to produce a sequence
   of values.

   [KNUTH] has a classic exposition on pseudo-random numbers.
   Applications he mentions are simulation of natural phenomena,
   sampling, numerical analysis, testing computer programs, decision
   making, and games.  None of these have the same characteristics as
   the sort of security uses we are talking about.  Only in the last two
   could there be an adversary trying to find the random quantity.
   However, in these cases, the adversary normally has only a single
   chance to use a guessed value.  In guessing passwords or attempting
   to break an encryption scheme, the adversary normally has many,



Eastlake, Crocker & Schiller                                    [Page 5]

RFC 1750        Randomness Recommendations for Security    December 1994