< draft-eastlake-randomness2-01.txt   draft-eastlake-randomness2-02.txt >
Network Working Group Donald E. Eastlake, 3rd Network Working Group Donald E. Eastlake, 3rd
OBSOLETES RFC 1750 Jeffrey I. Schiller OBSOLETES RFC 1750 Jeffrey I. Schiller
Steve Crocker Steve Crocker
Expires May 2001 November 2000 Expires October 2001 April 2001
Randomness Requirements for Security Randomness Requirements for Security
---------- ------------ --- -------- ---------- ------------ --- --------
<draft-eastlake-randomness2-01.txt> <draft-eastlake-randomness2-02.txt>
Status of This Document Status of This Document
This document is intended to become a Best Current Practice. This document is intended to become a Best Current Practice.
Comments should be sent to the authors. Distribution is unlimited. Comments should be sent to the authors. Distribution is unlimited.
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026. Internet-Drafts are working all provisions of Section 10 of RFC 2026. Internet-Drafts are
documents of the Internet Engineering Task Force (IETF), its areas, working documents of the Internet Engineering Task Force (IETF), its
and its working groups. Note that other groups may also distribute areas, and its working groups. Note that other groups may also
working documents as Internet-Drafts. distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six Internet-Drafts are draft documents valid for a maximum of six months
months. Internet-Drafts may be updated, replaced, or obsoleted by and may be updated, replaced, or obsoleted by other documents at any
other documents at any time. It is not appropriate to use Internet- time. It is inappropriate to use Internet- Drafts as reference
Drafts as reference material or to cite them other than as a material or to cite them other than as "work in progress."
``working draft'' or ``work in progress.''
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
Abstract Abstract
Security systems today are built on increasingly strong cryptographic Security systems today are built on increasingly strong cryptographic
skipping to change at page 2, line 26 skipping to change at page 2, line 26
number space. number space.
Choosing random quantities to foil a resourceful and motivated Choosing random quantities to foil a resourceful and motivated
adversary is surprisingly difficult. This document points out many adversary is surprisingly difficult. This document points out many
pitfalls in using traditional pseudo-random number generation pitfalls in using traditional pseudo-random number generation
techniques for choosing such quantities. It recommends the use of techniques for choosing such quantities. It recommends the use of
truly random hardware techniques and shows that the existing hardware truly random hardware techniques and shows that the existing hardware
on many systems can be used for this purpose. It provides on many systems can be used for this purpose. It provides
suggestions to ameliorate the problem when a hardware solution is not suggestions to ameliorate the problem when a hardware solution is not
available. And it gives examples of how large such quantities need available. And it gives examples of how large such quantities need
to be for some particular applications. to be for some applications.
Acknowledgements Acknowledgements
Special thanks to Special thanks to
(1) The authors of "Minimal Key Lengths for Symmetric Ciphers to (1) The authors of "Minimal Key Lengths for Symmetric Ciphers to
Provide Adequate Commercial Security" which is incorporated as Provide Adequate Commercial Security" which is incorporated as
Appendix A. Appendix A.
(2) Peter Gutmann who has permitted the incorporation into this (2) Peter Gutmann who has permitted the incorporation into this
replacement for RFC 1750 of materila from is paper "Software replacement for RFC 1750 of materila from is paper "Software
Generation of Practially Strong Random Numbers". Generation of Practially Strong Random Numbers".
The following other persons (in alphabetic order) contributed to this The following other persons (in alphabetic order) contributed to this
document: document:
(tbd) (tbd)
The following persons (in alpahbetic order) contributed to RFC 1750, The following persons (in alpahbetic order) contributed to RFC 1750,
the predeceasor of this document: the predeceasor of this document:
David M. Balenson, Don T. Davis, Carl Ellison, Marc Horowitz, David M. Balenson, Don T. Davis, Carl Ellison, Marc Horowitz,
Christian Huitema, Charlie Kaufman, Steve Kent, Hal Murray, Neil Christian Huitema, Charlie Kaufman, Steve Kent, Hal Murray, Neil
Haller, Richard Pitkin, Tim Redmond, Doug Tygar. Haller, Richard Pitkin, Tim Redmond, Doug Tygar.
Table of Contents
Status of This Document....................................1 Status of This Document....................................1
Abstract...................................................2 Abstract...................................................2
Acknowledgements...........................................2 Acknowledgements...........................................2
Table of Contents..........................................3 Table of Contents..........................................3
1. Introduction............................................5 1. Introduction............................................5
2. Requirements............................................6 2. Requirements............................................6
skipping to change at page 4, line 4 skipping to change at page 4, line 4
6.2 Non-Hardware Sources of Randomness....................22 6.2 Non-Hardware Sources of Randomness....................22
6.3 Cryptographically Strong Sequences....................23 6.3 Cryptographically Strong Sequences....................23
6.3.1 Traditional Strong Sequences........................23 6.3.1 Traditional Strong Sequences........................23
6.3.2 The Blum Blum Shub Sequence Generator...............24 6.3.2 The Blum Blum Shub Sequence Generator...............24
7. Key Generation Standards and Examples..................26 7. Key Generation Standards and Examples..................26
7.1 US DoD Recommendations for Password Generation........26 7.1 US DoD Recommendations for Password Generation........26
7.2 X9.17 Key Generation..................................26 7.2 X9.17 Key Generation..................................26
7.3 The /dev/random Device under Linux....................27 7.3 The /dev/random Device under Linux....................27
7.4 additional example....................................28 7.4 additional example....................................28
More Table of Contents
8. Examples of Randomness Required........................29 8. Examples of Randomness Required........................29
8.1 Password Generation..................................29 8.1 Password Generation..................................29
8.2 A Very High Security Cryptographic Key................30 8.2 A Very High Security Cryptographic Key................30
8.2.1 Effort per Key Trial................................30 8.2.1 Effort per Key Trial................................30
8.2.2 Meet in the Middle Attacks..........................30 8.2.2 Meet in the Middle Attacks..........................30
9. Conclusion.............................................32 9. Conclusion.............................................32
10. Security Considerations...............................32 10. Security Considerations...............................32
Appendix: Minimal Secure Key Lengths Study................33 Appendix: Minimal Secure Key Lengths Study................33
skipping to change at page 5, line 7 skipping to change at page 5, line 7
A.6 About the Authors.....................................44 A.6 About the Authors.....................................44
A.7 Acknowledgement.......................................45 A.7 Acknowledgement.......................................45
References................................................46 References................................................46
Authors Addresses.........................................49 Authors Addresses.........................................49
File Name and Expiration..................................49 File Name and Expiration..................................49
1. Introduction 1. Introduction
Software cryptography has come into wider use and in continuing Software cryptography is coming into wider use and is continuing to
spread, although there is a long way to go until it becomes spread, although there is a long way to go until it becomes
pervasive. Systems like IPSEC, TLS, S/MIME, PGP, DNSSEC, Kerberos, pervasive.
etc. are maturing and becoming a part of the network landscape
[DNSSEC, IPSEC, MAIL*, TLS]. By comparison, when the previous Systems like IPSEC, TLS, S/MIME, PGP, DNSSEC, Kerberos, etc. are
version of this document [RFC 1750] was issued in 1994, about the maturing and becoming a part of the network landscape [DNSSEC, IPSEC,
only cryptographic security specification in the IETF was the Privacy MAIL*, TLS]. By comparison, when the previous version of this
Enhanced Mail protocol [MAIL PEM]. document [RFC 1750] was issued in 1994, about the only cryptographic
security specification in the IETF was the Privacy Enhanced Mail
protocol [MAIL PEM].
These systems provide substantial protection against snooping and These systems provide substantial protection against snooping and
spoofing. However, there is a potential flaw. At the heart of all spoofing. However, there is a potential flaw. At the heart of all
cryptographic systems is the generation of secret, unguessable (i.e., cryptographic systems is the generation of secret, unguessable (i.e.,
random) numbers. random) numbers.
For the present, the lack of generally available facilities for For the present, the lack of generally available facilities for
generating such unpredictable numbers is an open wound in the design generating such unpredictable numbers is an open wound in the design
of cryptographic software. For the software developer who wants to of cryptographic software. For the software developer who wants to
build a key or password generation procedure that runs on a wide 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 range of hardware, the only safe strategy so far has been to force
the local installation to supply a suitable routine to generate the local installation to supply a suitable routine to generate
random numbers. To say the least, this is an awkward, error-prone random numbers. To say the least, this is an awkward, error-prone
and unpalatable solution. and unpalatable solution.
It is important to keep in mind that the requirement is for data that 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. an adversary has a very low probability of guessing or determining.
This will fail if pseudo-random data is used which only meets This can easily fail if pseudo-random data is used which only meets
traditional statistical tests for randomness or which is based on traditional statistical tests for randomness or which is based on
limited range sources, such as clocks. Frequently such random limited range sources, such as clocks. Frequently such random
quantities are determinable by an adversary searching through an quantities are determinable by an adversary searching through an
embarrassingly small space of possibilities. embarrassingly small space of possibilities.
This informational document suggests techniques for producing random This informational document suggests techniques for producing random
quantities that will be resistant to such attack. It recommends that quantities that will be resistant to such attack. It recommends that
future systems include hardware random number generation or provide future systems include hardware random number generation or provide
access to existing hardware that can be used for this purpose. It access to existing hardware that can be used for this purpose. It
suggests methods for use if such hardware is not available. And it suggests methods for use if such hardware is not available. And it
skipping to change at page 6, line 23 skipping to change at page 6, line 23
words. But this only affects the format of the password information, words. But this only affects the format of the password information,
not the requirement that the password be very hard to guess.) not the requirement that the password be very hard to guess.)
Many other requirements come from the cryptographic arena. Many other requirements come from the cryptographic arena.
Cryptographic techniques can be used to provide a variety of services Cryptographic techniques can be used to provide a variety of services
including confidentiality and authentication. Such services are including confidentiality and authentication. Such services are
based on quantities, traditionally called "keys", that are unknown to based on quantities, traditionally called "keys", that are unknown to
and unguessable by an adversary. and unguessable by an adversary.
In some cases, such as the use of symmetric encryption with the one In some cases, such as the use of symmetric encryption with the one
time pads [CRYPTO*] or the US Data Encryption Standard [DES], the time pads [CRYPTO*] or the US Data Encryption Standard [DES] or
parties who wish to communicate confidentially and/or with Advanced Encryption Standard [AES], the parties who wish to
authentication must all know the same secret key. In other cases, communicate confidentially and/or with authentication must all know
using what are called asymmetric or "public key" cryptographic the same secret key. In other cases, using what are called
techniques, keys come in pairs. One key of the pair is private and asymmetric or "public key" cryptographic techniques, keys come in
must be kept secret by one party, the other is public and can be pairs. One key of the pair is private and must be kept secret by one
published to the world. It is computationally infeasible to party, the other is public and can be published to the world. It is
determine the private key from the public key. [ASYMMETRIC, CRYPTO*] computationally infeasible to determine the private key from the
public key. [ASYMMETRIC, CRYPTO*]
The frequency and volume of the requirement for random quantities The frequency and volume of the requirement for random quantities
differs greatly for different cryptographic systems. Using pure RSA differs greatly for different cryptographic systems. Using pure RSA
[CRYPTO*], random quantities are required when the key pair is [CRYPTO*], random quantities are required when the key pair is
generated, but thereafter any number of messages can be signed generated, but thereafter any number of messages can be signed
without any further need for randomness. The public key Digital without any further need for randomness. The public key Digital
Signature Algorithm devused by the US National Institute of Standards Signature Algorithm devused by the US National Institute of Standards
and Technology (NIST) requires good random numbers for each and Technology (NIST) requires good random numbers for each
signature. And encrypting with a one time pad, in principle the signature. And encrypting with a one time pad, in principle the
strongest possible encryption technique, requires a volume of strongest possible encryption technique, requires a volume of
skipping to change at page 7, line 27 skipping to change at page 7, line 27
If there are 2^n different values of equal probability, then n bits If there are 2^n different values of equal probability, then n bits
of information are present and an adversary would, on the average, 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 have to try half of the values, or 2^(n-1) , before guessing the
secret quantity. If the probability of different values is unequal, secret quantity. If the probability of different values is unequal,
then there is less information present and fewer guesses will, on then there is less information present and fewer guesses will, on
average, be required by an adversary. In particular, any values that average, be required by an adversary. In particular, any values that
the adversary can know are impossible, or are of low probability, can the adversary can know are impossible, or are of low probability, can
be initially ignored by an adversary, who will search through the be initially ignored by an adversary, who will search through the
more probable values first. more probable values first.
For example, consider a cryptographic system that uses 56 bit keys. For example, consider a cryptographic system that uses 128 bit keys.
If these 56 bit keys are derived by using a fixed pseudo-random If these 128 bit keys are derived by using a fixed pseudo-random
number generator that is seeded with an 8 bit seed, then an adversary 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 needs to search through only 256 keys (by running the pseudo-random
number generator with every possible seed), not the 2^56 keys that number generator with every possible seed), not the 2^128 keys that
may at first appear to be the case. Only 8 bits of "information" are may at first appear to be the case. Only 8 bits of "information" are
in these 56 bit keys. in these 128 bit keys.
3. Traditional Pseudo-Random Sequences 3. Traditional Pseudo-Random Sequences
Most traditional sources of random numbers use deterministic sources Most traditional sources of random numbers use deterministic sources
of "pseudo-random" numbers. These typically start with a "seed" of "pseudo-random" numbers. These typically start with a "seed"
quantity and use numeric or logical operations to produce a sequence quantity and use numeric or logical operations to produce a sequence
of values. of values.
[KNUTH] has a classic exposition on pseudo-random numbers. [KNUTH] has a classic exposition on pseudo-random numbers.
Applications he mentions are simulation of natural phenomena, Applications he mentions are simulation of natural phenomena,
skipping to change at page 13, line 25 skipping to change at page 13, line 25
spinning disk or the like has an adequate source of randomness spinning disk or the like has an adequate source of randomness
[DAVIS]. All that's needed is the common perception among computer [DAVIS]. All that's needed is the common perception among computer
vendors that this small additional hardware and the software to vendors that this small additional hardware and the software to
access it is necessary and useful. access it is necessary and useful.
5.1 Volume Required 5.1 Volume Required
How much unpredictability is needed? Is it possible to quantify the How much unpredictability is needed? Is it possible to quantify the
requirement in, say, number of random bits per second? requirement in, say, number of random bits per second?
The answer is not very much is needed. For DES, the key is 56 bits The answer is not very much is needed. For AES, the key can be 128
and, as we show in an example in Section 8, even the highest security bits and, as we show in an example in Section 8, even the highest
system is unlikely to require a keying material of over 200 bits. If security system is unlikely to require a keying material of much over
a series of keys are needed, they can be generated from a strong 200 bits. If a series of keys are needed, they can be generated from
random seed using a cryptographically strong sequence as explained in a strong random seed using a cryptographically strong sequence as
Section 6.3. A few hundred random bits generated once a day would be explained in Section 6.3. A few hundred random bits generated once a
enough using such techniques. Even if the random bits are generated day would be enough using such techniques. Even if the random bits
as slowly as one per second and it is not possible to overlap the are generated as slowly as one per second and it is not possible to
generation process, it should be tolerable in high security overlap the generation process, it should be tolerable in high
applications to wait 200 seconds occasionally. security applications to wait 200 seconds occasionally.
These numbers are trivial to achieve. It could be done by a person These numbers are trivial to achieve. It could be done by a person
repeatedly tossing a coin. Almost any hardware process is likely to repeatedly tossing a coin. Almost any hardware process is likely to
be much faster. be much faster.
5.2 Sensitivity to Skew 5.2 Sensitivity to Skew
Is there any specific requirement on the shape of the distribution of Is there any specific requirement on the shape of the distribution of
the random numbers? The good news is the distribution need not be the random numbers? The good news is the distribution need not be
uniform. All that is needed is a conservative estimate of how non- uniform. All that is needed is a conservative estimate of how non-
skipping to change at page 17, line 45 skipping to change at page 17, line 45
time instrumentation to a system, a series of measurements can be time instrumentation to a system, a series of measurements can be
obtained that include this randomness. Such data is usually highly obtained that include this randomness. Such data is usually highly
correlated so that significant processing is needed, including FFT correlated so that significant processing is needed, including FFT
(see section 5.2.3). Nevertheless experimentation has shown that, (see section 5.2.3). Nevertheless experimentation has shown that,
with such processing, disk drives easily produce 100 bits a minute or with such processing, disk drives easily produce 100 bits a minute or
more of excellent random data. more of excellent random data.
Partly offsetting this need for processing is the fact that disk Partly offsetting this need for processing is the fact that disk
drive failure will normally be rapidly noticed. Thus, problems with drive failure will normally be rapidly noticed. Thus, problems with
this method of random number generation due to hardware failure are this method of random number generation due to hardware failure are
very unlikely. unlikely.
6. Recommended Non-Hardware Strategy 6. Recommended Non-Hardware Strategy
What is the best overall strategy for meeting the requirement for What is the best overall strategy for meeting the requirement for
unguessable random numbers in the absence of a reliable hardware unguessable random numbers in the absence of a reliable hardware
source? It is to obtain random input from a number of uncorrelated source? It is to obtain random input from a number of uncorrelated
sources and to mix them with a strong mixing function. Such a sources and to mix them with a strong mixing function. Such a
function will preserve the randomness present in any of the sources function will preserve the randomness present in any of the sources
even if other quantities being combined are fixed or easily even if other quantities being combined are fixed or easily
guessable. This may be advisable even with a good hardware source as guessable. This may be advisable even with a good hardware source,
hardware can also fail, though this should be weighed against any as hardware can also fail, though this should be weighed against any
increase in the chance of overall failure due to added software increase in the chance of overall failure due to added software
complexity. complexity.
6.1 Mixing Functions 6.1 Mixing Functions
A strong mixing function is one which combines two or more inputs and A strong mixing function is one which combines two or more inputs and
produces an output where each output bit is a different complex non- produces an output where each output bit is a different complex non-
linear function of all the input bits. On average, changing any linear function of all the input bits. On average, changing any
input bit will change about half the output bits. But because the input bit will change about half the output bits. But because the
relationship is complex and non-linear, no particular output bit is relationship is complex and non-linear, no particular output bit is
skipping to change at page 19, line 49 skipping to change at page 19, line 49
However, keep in mind that the above calculations assume that the However, keep in mind that the above calculations assume that the
inputs are not correlated. If the inputs were, say, the parity of 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 the number of minutes from midnight on two clocks accurate to a few
seconds, then each might appear random if sampled at random intervals seconds, then each might appear random if sampled at random intervals
much longer than a minute. Yet if they were both sampled and much longer than a minute. Yet if they were both sampled and
combined with xor, the result would be zero most of the time. combined with xor, the result would be zero most of the time.
6.1.2 Stronger Mixing Functions 6.1.2 Stronger Mixing Functions
The US Government Data Encryption Standard [DES] is an example of a The US Government Advanced Encryption Standard [AES] is an example of
strong mixing function for multiple bit quantities. It takes up to a strong mixing function for multiple bit quantities. It takes up to
120 bits of input (64 bits of "data" and 56 bits of "key") and 384 bits of input (128 bits of "data" and 256 bits of "key") and
produces 64 bits of output each of which is dependent on a complex produces 128 bits of output each of which is dependent on a complex
non-linear function of all input bits. Other strong encryption non-linear function of all input bits. Other encryption functions
functions with this characteristic can also be used by considering with this characteristic, such as [DES], can also be used by
them to mix all of their key and data input bits. considering them to mix all of their key and data input bits.
Another good family of mixing functions are the "message digest" or Another good family of mixing functions are the "message digest" or
hashing functions such as The US Government Secure Hash Standard hashing functions such as The US Government Secure Hash Standards
[SHA1] and the MD4, MD5 [MD4, MD5] series. These functions all take [SHA*] and the MD4, MD5 [MD4, MD5] series. These functions all take
an arbitrary amount of input and produce an output mixing all the an arbitrary amount of input and produce an output mixing all the
input bits. The MD* series produce 128 bits of output and SHA1 input bits. The MD* series produce 128 bits of output, SHA-1 produces
produces 160 bits. 160 bits, and SHA-256 and SHA-512 produce 256 and 512 bits
respectively.
Although the message digest functions are designed for variable Although the message digest functions are designed for variable
amounts of input, DES and other encryption functions can also be used amounts of input, AES and other encryption functions can also be used
to combine any number of inputs. If 64 bits of output is adequate, to combine any number of inputs. If 128 bits of output is adequate,
the inputs can be packed into a 64 bit data quantity and successive the inputs can be packed into a 128 bit data quantity and successive
56 bit keys, padding with zeros if needed, which are then used to AES keys, padding with zeros if needed, which are then used to
successively encrypt using DES in Electronic Codebook Mode [DES successively encrypt using AES in Electronic Codebook Mode [DES
MODES]. If more than 64 bits of output are needed, use more complex MODES]. If more than 128 bits of output are needed, use more complex
mixing. For example, if inputs are packed into three quantities, A, mixing. For example, if inputs are packed into three quantities, A,
B, and C, use DES to encrypt A with B as a key and then with C as a B, and C, use AES to encrypt A with B as a key and then with C as a
key to produce the 1st part of the output, then encrypt B with C and key to produce the 1st 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 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 for yet more output. Still more output can be produced by reversing
the order of the keys given above to stretch things. The same can be the order of the keys given above to stretch things. The same can be
done with the hash functions by hashing various subsets of the input done with the hash functions by hashing various subsets of the input
data to produce multiple outputs. But keep in mind that it is data to produce multiple outputs. But keep in mind that it is
impossible to get more bits of "randomness" out than are put in. impossible to get more bits of "randomness" out than are put in.
An example of using a strong mixing function would be to reconsider An example of using a strong mixing function would be to reconsider
the case of a string of 308 bits each of which is biased 99% towards the case of a string of 308 bits each of which is biased 99% towards
zero. The parity technique given in Section 5.2.1 above reduced this zero. The parity technique given in Section 5.2.1 above reduced this
to one bit with only a 1/1000 deviance from being equally likely a 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 zero or one. But, applying the equation for information given in
Section 2, this 308 bit skewed sequence has over 5 bits of Section 2, this 308 bit skewed sequence has over 5 bits of
information in it. Thus hashing it with SHA1 or MD5 and taking the information in it. Thus hashing it with SHA-1 and taking the bottom
bottom 5 bits of the result would yield 5 unbiased random bits as 5 bits of the result would yield 5 unbiased random bits as opposed to
opposed to the single bit given by calculating the parity of the the single bit given by calculating the parity of the string.
string.
6.1.3 Diff-Hellman as a Mixing Function 6.1.3 Diff-Hellman as a Mixing Function
Diffie-Hellman exponential key exchange is a technique that yields a Diffie-Hellman exponential key exchange is a technique that yields a
shared secret between two parties that can be made computationally shared secret between two parties that can be made computationally
infeasible for a third party to determine even if they can observe infeasible for a third party to determine even if they can observe
all the messages between the two communicating parties. This shared all the messages between the two communicating parties. This shared
secret is a mixture of initial quantities generated by each of them secret is a mixture of initial quantities generated by each of them
[D-H]. If these initial quantities are random, then the shared [D-H]. If these initial quantities are random, then the shared
secret contains the combined randomness of them both, assuming they secret contains the combined randomness of them both, assuming they
skipping to change at page 21, line 31 skipping to change at page 21, line 31
The last table in Section 6.1.1 shows that mixing a random bit with a The last table in Section 6.1.1 shows that mixing a random bit with a
constant bit with Exclusive Or will produce a random bit. While this 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 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 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 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 either 01 or 10. Since there are only two possible values, there is
still only the one bit of original randomness. still only the one bit of original randomness.
6.1.5 Other Factors in Choosing a Mixing Function 6.1.5 Other Factors in Choosing a Mixing Function
For local use, DES has the advantages that it has been widely tested For local use, AES has the advantages that it has been widely tested
for flaws, is widely documented, and is widely implemented with for flaws, is reasonably efficient in software, and will be widely
hardware and software implementations available all over the world documented and implemented with hardware and software implementations
including source code available on the Internet. The SHA1 and MD* available all over the world including source code available on the
family are younger algorithms which have been less tested but there Internet. The SHA* family are younger algorithms but there is no
is no particular reason to believe they are flawed. Both MD5 and SHS particular reason to believe they are flawed. Both SHA* and MD5 were
were derived from the earlier MD4 algorithm. They all have source derived from the earlier MD4 algorithm. Some signs of weakness have
code available [SHS, MD4, MD5]. been found in MD4 and MD5. They all have source code available [SHA*,
MD*].
DES and SHA1 have been vouched for the the US National Security AES and SHA* have been vouched for the the US National Security
Agency (NSA) on the basis of criteria that primarily remain secret. Agency (NSA) on the basis of criteria that primarily remain secret,
While this is the cause of much speculation and doubt, investigation as was DES. While this is the cause of much speculation and doubt,
of DES over the years has indicated that NSA involvement in investigation of DES over the years has indicated that NSA
modifications to its design, which originated with IBM, was primarily involvement in modifications to its design, which originated with
to strengthen it. No concealed or special weakness has been found in IBM, was primarily to strengthen it. No concealed or special
DES. It is almost certain that the NSA modification to MD4 to weakness has been found in DES. It is almost certain that the NSA
produce the SHA1 similarly strengthened the algorithm, possibly modifications to MD4 to produce the SHA* similarly strengthened these
against threats not yet known in the public cryptographic community. algorithms, possibly against threats not yet known in the public
cryptographic community.
DES, SHA1, MD4, and MD5 are royalty free for all purposes. Continued AES, DES, SHA*, MD4, and MD5 are royalty free for all purposes.
advances in crypography and computing power have cast some doubts on Continued advances in crypography and computing power have cast some
MD4 and MD5 so their use is not recommended. doubts on MD4 and MD5 so their use is NOT RECOMMENDED.
Another advantage of the MD* or similar hashing algorithms over Another advantage of the SHA* or similar hashing algorithms over
encryption algorithms is that they are not subject to the same encryption algorithms in the past was that they are not subject to
regulations imposed by the US Government prohibiting the unlicensed the same regulations imposed by the US Government prohibiting the
export or import of encryption/decryption software and hardware. The unlicensed export or import of encryption/decryption software and
same should be true of DES rigged to produce an irreversible hash hardware.
code but most DES packages are oriented to reversible encryption.
6.2 Non-Hardware Sources of Randomness 6.2 Non-Hardware Sources of Randomness
The best source of input for mixing would be a hardware randomness The best source of input for mixing would be a hardware randomness
such as disk drive timing effected by air turbulence, audio input such as disk drive timing effected by air turbulence, audio input
with thermal noise, or radioactive decay. However, if that is not with thermal noise, or radioactive decay. However, if that is not
available there are other possibilities. These include system available there are other possibilities. These include system
clocks, system or input/output buffers, user/system/hardware/network clocks, system or input/output buffers, user/system/hardware/network
serial numbers and/or addresses and timing, and user input. serial numbers and/or addresses and timing, and user input.
Unfortunately, any of these sources can produce limited or Unfortunately, any of these sources can produce limited or
predicatable values under some circumstances. predicatable values under some circumstances.
Some of the sources listed above would be quite strong on multi-user Some of the sources listed above would be quite strong on multi-user
systems where, in essence, each user of the system is a source of systems where, in essence, each user of the system is a source of
randomness. However, on a small single user system, it might be randomness. However, on a small single user system, especially at
possible for an adversary to assemble a similar configuration. This start up, it might be possible for an adversary to assemble a similar
could give the adversary inputs to the mixing process that were configuration. This could give the adversary inputs to the mixing
sufficiently correlated to those used originally as to make process that were sufficiently correlated to those used originally as
exhaustive search practical. to make exhaustive search practical.
The use of multiple random inputs with a strong mixing function is The use of multiple random inputs with a strong mixing function is
recommended and can overcome weakness in any particular input. For recommended and can overcome weakness in any particular input. For
example, the timing and content of requested "random" user keystrokes example, the timing and content of requested "random" user keystrokes
can yield hundreds of random bits but conservative assumptions need can yield hundreds of random bits but conservative assumptions need
to be made. For example, assuming a few bits of randomness if the to be made. For example, assuming a few bits of randomness if the
inter-keystroke interval is unique in the sequence up to that point inter-keystroke interval is unique in the sequence up to that point
and a similar assumption if the key hit is unique but assuming that and a similar assumption if the key hit is unique but assuming that
no bits of randomness are present in the initial key value or if the no bits of randomness are present in the initial key value or if the
timing or key value duplicate previous values. The results of mixing timing or key value duplicate previous values. The results of mixing
skipping to change at page 23, line 46 skipping to change at page 23, line 47
mask the values obtained so as to limit the amount of generator state mask the values obtained so as to limit the amount of generator state
available to the adversary. available to the adversary.
It may also be possible to use an "encryption" algorithm with a It may also be possible to use an "encryption" algorithm with a
random key and seed value to encrypt and feedback some or all of the random key and seed value to encrypt and feedback some or all of the
output encrypted value into the value to be encrypted for the next output encrypted value into the value to be encrypted for the next
iteration. Appropriate feedback techniques will usually be iteration. Appropriate feedback techniques will usually be
recommended with the encryption algorithm. An example is shown below recommended with the encryption algorithm. An example is shown below
where shifting and masking are used to combine the cypher output where shifting and masking are used to combine the cypher output
feedback. This type of feedback is recommended by the US Government feedback. This type of feedback is recommended by the US Government
in connection with DES [DES MODES]. in connection with DES [DES MODES] but should be avoided for reasons
described below.
+---------------+ +---------------+
| V | | V |
| | n | | | n |
+--+------------+ +--+------------+
| | +---------+ | | +---------+
| +---------> | | +-----+ | +---------> | | +-----+
+--+ | Encrypt | <--- | Key | +--+ | Encrypt | <--- | Key |
| +-------- | | +-----+ | +-------- | | +-----+
| | +---------+ | | +---------+
skipping to change at page 24, line 51 skipping to change at page 24, line 51
system even when the cryptographic system is invertible and can be system even when the cryptographic system is invertible and can be
broken if all of each generated value was revealed. broken if all of each generated value was revealed.
6.3.2 The Blum Blum Shub Sequence Generator 6.3.2 The Blum Blum Shub Sequence Generator
Currently the generator which has the strongest public proof of Currently the generator which has the strongest public proof of
strength is called the Blum Blum Shub generator after its inventors strength is called the Blum Blum Shub generator after its inventors
[BBS]. It is also very simple and is based on quadratic residues. [BBS]. It is also very simple and is based on quadratic residues.
It's only disadvantage is that is is computationally intensive It's only disadvantage is that is is computationally intensive
compared with the traditional techniques give in 6.3.1 above. This compared with the traditional techniques give in 6.3.1 above. This
is not a serious draw back if it is used for moderately infrequent is not a major draw back if it is used for moderately infrequent
purposes, such as generating session keys. purposes, such as generating session keys.
Simply choose two large prime numbers, say p and q, which both have Simply choose two large prime numbers, say p and q, which both have
the property that you get a remainder of 3 if you divide them by 4. the property that you get a remainder of 3 if you divide them by 4.
Let n = p * q. Then you choose a random number x relatively prime to Let n = p * q. Then you choose a random number x relatively prime to
n. The initial seed for the generator and the method for calculating n. The initial seed for the generator and the method for calculating
subsequent values are then subsequent values are then
2 2
s = ( x )(Mod n) s = ( x )(Mod n)
skipping to change at page 27, line 44 skipping to change at page 27, line 44
likely true entropy the input contains. The pool itself contains a likely true entropy the input contains. The pool itself contains a
accumulator that estimates the total over all entropy of the pool. accumulator that estimates the total over all entropy of the pool.
Input events come from several sources: Input events come from several sources:
1. Keyboard interrupts. The time of the interrupt as well as the scan 1. Keyboard interrupts. The time of the interrupt as well as the scan
code are added to the pool. This in effect adds entropy from the code are added to the pool. This in effect adds entropy from the
human operator by measuring inter-keystroke arrival times. human operator by measuring inter-keystroke arrival times.
2. Disk completion and other interrupts. A system being used by a 2. Disk completion and other interrupts. A system being used by a
person will likely have a hard to predict pattern of disk person will likely have a hard to predict pattern of disk
accesses. accesses.
3. Mouse motion. The timing as well as mouse position is added in. 3. Mouse motion. The timing as well as mouse position is added in.
When random bytes are required, the pool is hashed with SHA-1 [SHA1] When random bytes are required, the pool is hashed with SHA-1 [SHA1]
to yield the returned bytes of randomness. If more bytes are required to yield the returned bytes of randomness. If more bytes are required
than the output of SHA-1 (20 bytes), then the hashed output is than the output of SHA-1 (20 bytes), then the hashed output is
stirred back into the pool and a new hash performed to obtain the stirred back into the pool and a new hash performed to obtain the
next 20 bytes. As bytes are removed from the pool, the estimate of next 20 bytes. As bytes are removed from the pool, the estimate of
entropy is similarly decremented. entropy is similarly decremented.
skipping to change at page 29, line 12 skipping to change at page 29, line 12
(tba) (tba)
8. Examples of Randomness Required 8. Examples of Randomness Required
Below are two examples showing rough calculations of needed Below are two examples showing rough calculations of needed
randomness for security. The first is for moderate security randomness for security. The first is for moderate security
passwords while the second assumes a need for a very high security passwords while the second assumes a need for a very high security
cryptographic key. cryptographic key.
In addition [ORMAN] provides information on the public key lengths
that should be used for exchanging symmetric keys.
8.1 Password Generation 8.1 Password Generation
Assume that user passwords change once a year and it is desired that Assume that user passwords change once a year and it is desired that
the probability that an adversary could guess the password for a the probability that an adversary could guess the password for a
particular account be less than one in a thousand. Further assume particular account be less than one in a thousand. Further assume
that sending a password to the system is the only way to try a that sending a password to the system is the only way to try a
password. Then the crucial question is how often an adversary can password. Then the crucial question is how often an adversary can
try possibilities. Assume that delays have been introduced into a try possibilities. Assume that delays have been introduced into a
system so that, at most, an adversary can make one password try every system so that, at most, an adversary can make one password try every
six seconds. That's 600 per hour or about 15,000 per day or about six seconds. That's 600 per hour or about 15,000 per day or about
skipping to change at page 30, line 46 skipping to change at page 30, line 47
An oversimplified explanation of the meet in the middle attack is as An oversimplified explanation of the meet in the middle attack is as
follows: the adversary can half-encrypt the known or chosen plain follows: the adversary can half-encrypt the known or chosen plain
text with all possible first half-keys, sort the output, then half- text with all possible first half-keys, sort the output, then half-
decrypt the encoded text with all the second half-keys. If a match decrypt the encoded text with all the second half-keys. If a match
is found, the full key can be assembled from the halves and used to is found, the full key can be assembled from the halves and used to
decrypt other parts of the message or other messages. At its best, decrypt other parts of the message or other messages. At its best,
this type of attack can halve the exponent of the work required by this type of attack can halve the exponent of the work required by
the adversary while adding a large but roughly constant factor of the adversary while adding a large but roughly constant factor of
effort. To be assured of safety against this, a doubling of the effort. To be assured of safety against this, a doubling of the
amount of randomness in a very strong key to a minimum of 176 bits is amount of randomness in the very strong key to a minimum of 176 bits
required for the year 2001 based on the Appendix A analysis. is required for the year 2001 based on the Appendix A analysis.
This amount of randomness is beyond the limit of that in the inputs This amount of randomness is beyond the limit of that in the inputs
recommended by the US DoD for password generation and could require recommended by the US DoD for password generation and could require
user typing timing, hardware random number generation, or other user typing timing, hardware random number generation, or other
sources. sources.
The meet in the middle attack assumes that the cryptographic The meet in the middle attack assumes that the cryptographic
algorithm can be decomposed in this way but we can not rule that out algorithm can be decomposed in this way but we can not rule that out
without a thorough knowledge of the algorithm. Even if a basic without a deepthorough knowledge of the algorithm. Even if a basic
algorithm is not subject to a meet in the middle attack, an attempt algorithm is not subject to a meet in the middle attack, an attempt
to produce a stronger algorithm by applying the basic algorithm twice to produce a stronger algorithm by applying the basic algorithm twice
(or two different algorithms sequentially) with different keys may (or two different algorithms sequentially) with different keys may
gain less added security than would be expected. Such a composite gain less added security than would be expected. Such a composite
algorithm would be subject to a meet in the middle attack. algorithm would be subject to a meet in the middle attack.
Enormous resources may be required to mount a meet in the middle Enormous resources may be required to mount a meet in the middle
attack but they are probably within the range of the national attack but they are probably within the range of the national
security services of a major nation. Essentially all nations spy on security services of a major nation. Essentially all nations spy on
other nations government traffic and several nations are believed to other nations government traffic and several nations are believed to
skipping to change at page 46, line 7 skipping to change at page 46, line 7
as well). as well).
A.7 Acknowledgement A.7 Acknowledgement
The [Appendix] authors would like to thank the Business Software The [Appendix] authors would like to thank the Business Software
Alliance, which provided support for a one-day meeting, held in Alliance, which provided support for a one-day meeting, held in
Chicago on 20 November 1995. Chicago on 20 November 1995.
References References
[AES] - "Advanced Encryption Standard", United States of America,
Department of Commerce, National Institute of Standards and
Technology, Federal Information Processing Standard (FIPS) xxx.
[ASYMMETRIC] - "Secure Communications and Asymmetric Cryptosystems", [ASYMMETRIC] - "Secure Communications and Asymmetric Cryptosystems",
edited by Gustavus J. Simmons, AAAS Selected Symposium 69, Westview edited by Gustavus J. Simmons, AAAS Selected Symposium 69, Westview
Press, Inc. Press, Inc.
[BBS] - "A Simple Unpredictable Pseudo-Random Number Generator", SIAM [BBS] - "A Simple Unpredictable Pseudo-Random Number Generator", SIAM
Journal on Computing, v. 15, n. 2, 1986, L. Blum, M. Blum, & M. Shub. Journal on Computing, v. 15, n. 2, 1986, L. Blum, M. Blum, & M. Shub.
[BRILLINGER] - "Time Series: Data Analysis and Theory", Holden-Day, [BRILLINGER] - "Time Series: Data Analysis and Theory", Holden-Day,
1981, David Brillinger. 1981, David Brillinger.
skipping to change at page 47, line 39 skipping to change at page 47, line 43
II: Certificate-Based Key Management, 02/10/1993, S. Kent II: Certificate-Based Key Management, 02/10/1993, S. Kent
- RFC 1421, Privacy Enhancement for Internet Electronic Mail: Part I: - RFC 1421, Privacy Enhancement for Internet Electronic Mail: Part I:
Message Encryption and Authentication Procedures, 02/10/1993, J. Linn Message Encryption and Authentication Procedures, 02/10/1993, J. Linn
[MAIL PGP] - RFC 2440, "OpenPGP Message Format", J. Callas, L. [MAIL PGP] - RFC 2440, "OpenPGP Message Format", J. Callas, L.
Donnerhacke, H. Finney, R. Thayer", November 1998 Donnerhacke, H. Finney, R. Thayer", November 1998
[MAIL S/MIME] - RFC 2633, "S/MIME Version 3 Message Specification", [MAIL S/MIME] - RFC 2633, "S/MIME Version 3 Message Specification",
B. Ramsdell, Ed., June 1999. B. Ramsdell, Ed., June 1999.
[MD4] - The MD4 Message-Digest Algorithm, RFC1320, April 1992, R. [MD4] - "The MD4 Message-Digest Algorithm", RFC1320, April 1992, R.
Rivest Rivest
[MD5] - The MD5 Message-Digest Algorithm, RFC1321, April 1992, R. [MD5] - "The MD5 Message-Digest Algorithm", RFC1321, April 1992, R.
Rivest Rivest
[MOORE] - [MOORE] - Moore's Law: the exponential increase the logic density of
silicon circuts. Originally formulated by Gordon Moore in 1964 as a
doubling every year starting in 1962, in the late 1970s the rate fell
to a doubling every 18 months and has remained there through the date
of this document. See "The New Hacker's Dictionary", Third Edition,
MIT Press, ISBN 0-262-18178-9, Eric S. Raymondm 1996.
[ORMAN] - "Determining Strengths For Public Keys Used For Exchanging
Symmetric Keys", draft-orman-public-key-lengths-*.txt, Hilarie Orman,
Paul Hoffman, work in progress.
[RFC 1750] - "Randomness Requirements for Security", D. Eastlake, S. [RFC 1750] - "Randomness Requirements for Security", D. Eastlake, S.
Crocker, J. Schiller, December 1994. Crocker, J. Schiller, December 1994.
[SHANNON] - "The Mathematical Theory of Communication", University of [SHANNON] - "The Mathematical Theory of Communication", University of
Illinois Press, 1963, Claude E. Shannon. (originally from: Bell Illinois Press, 1963, Claude E. Shannon. (originally from: Bell
System Technical Journal, July and October 1948) System Technical Journal, July and October 1948)
[SHIFT1] - "Shift Register Sequences", Aegean Park Press, Revised [SHIFT1] - "Shift Register Sequences", Aegean Park Press, Revised
Edition 1982, Solomon W. Golomb. Edition 1982, Solomon W. Golomb.
[SHIFT2] - "Cryptanalysis of Shift-Register Generated Stream Cypher [SHIFT2] - "Cryptanalysis of Shift-Register Generated Stream Cypher
Systems", Aegean Park Press, 1984, Wayne G. Barker. Systems", Aegean Park Press, 1984, Wayne G. Barker.
[SHA1] - Secure Hash Standard, United States of American, National [SHA-1] - "Secure Hash Standard", United States of American, National
Institute of Science and Technology, Federal Information Processing Institute of Science and Technology, Federal Information Processing
Standard (FIPS) 180-1, April 1993. Standard (FIPS) 180-1, April 1993.
- "US Secure Hash Algorithm 1 (SHA1)", D. Eastlake, P. Jones, draft-
eastlake-sha1-01.txt, work in progress.
[SHA-256] -
[SHA-512] -
[STERN] - "Secret Linear Congruential Generators are not [STERN] - "Secret Linear Congruential Generators are not
Cryptograhically Secure", Proceedings of IEEE STOC, 1987, J. Stern. Cryptograhically Secure", Proceedings of IEEE STOC, 1987, J. Stern.
[TLS] - RFC 2246, "The TLS Protocol Version 1.0", T. Dierks, C. [TLS] - RFC 2246, "The TLS Protocol Version 1.0", T. Dierks, C.
Allen, January 1999. Allen, January 1999.
[VON NEUMANN] - "Various techniques used in connection with random [VON NEUMANN] - "Various techniques used in connection with random
digits", von Neumann's Collected Works, Vol. 5, Pergamon Press, 1963, digits", von Neumann's Collected Works, Vol. 5, Pergamon Press, 1963,
J. von Neumann. J. von Neumann.
skipping to change at page 49, line 37 skipping to change at page 49, line 37
Suite 100 Suite 100
1319 Shepard Drive 1319 Shepard Drive
Sterling, VA 20164 USA Sterling, VA 20164 USA
Telephone: +1 703-433-0808 x206 Telephone: +1 703-433-0808 x206
FAX: +1 202-478-0458 FAX: +1 202-478-0458
EMail: steve@stevecrocker.com EMail: steve@stevecrocker.com
File Name and Expiration File Name and Expiration
This is file draft-eastlake-randomness2-01.txt. This is file draft-eastlake-randomness2-02.txt.
It expires May 2001. It expires October 2001.
 End of changes. 45 change blocks. 
112 lines changed or deleted 142 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/