< draft-eastlake-randomness2-02.txt   draft-eastlake-randomness2-03.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 October 2001 April 2001 Expires January 2003 July 2002
Randomness Requirements for Security Randomness Requirements for Security
---------- ------------ --- -------- ---------- ------------ --- --------
<draft-eastlake-randomness2-02.txt> <draft-eastlake-randomness2-03.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 RFC 2026. Internet-Drafts are all provisions of Section 10 of RFC 2026. Internet-Drafts are
working documents of the Internet Engineering Task Force (IETF), its working documents of the Internet Engineering Task Force (IETF), its
areas, and its working groups. Note that other groups may also areas, and its working groups. Note that other groups may also
skipping to change at page 2, line 7 skipping to change at page 2, line 7
material or to cite them other than as "work in progress." material or to cite them other than as "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 strong cryptographic algorithms
algorithms that foil pattern analysis attempts. However, the security that foil pattern analysis attempts. However, the security of these
of these systems is dependent on generating secret quantities for systems is dependent on generating secret quantities for passwords,
passwords, cryptographic keys, and similar quantities. The use of cryptographic keys, and similar quantities. The use of pseudo-random
pseudo-random processes to generate secret quantities can result in processes to generate secret quantities can result in pseudo-
pseudo-security. The sophisticated attacker of these security security. The sophisticated attacker of these security systems may
systems may find it easier to reproduce the environment that produced find it easier to reproduce the environment that produced the secret
the secret quantities, searching the resulting small set of quantities, searching the resulting small set of possibilities, than
possibilities, than to locate the quantities in the whole of the to locate the quantities in the whole of the potential 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 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 material 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) Tony Hansen, Sandy Harris
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, and Doug Tygar.
Table of Contents 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
skipping to change at page 3, line 32 skipping to change at page 3, line 32
4.2 Timing and Content of External Events.................11 4.2 Timing and Content of External Events.................11
4.3 The Fallacy of Complex Manipulation...................11 4.3 The Fallacy of Complex Manipulation...................11
4.4 The Fallacy of Selection from a Large Database........12 4.4 The Fallacy of Selection from a Large Database........12
5. Hardware for Randomness................................13 5. Hardware for Randomness................................13
5.1 Volume Required.......................................13 5.1 Volume Required.......................................13
5.2 Sensitivity to Skew...................................13 5.2 Sensitivity to Skew...................................13
5.2.1 Using Stream Parity to De-Skew......................14 5.2.1 Using Stream Parity to De-Skew......................14
5.2.2 Using Transition Mappings to De-Skew................15 5.2.2 Using Transition Mappings to De-Skew................15
5.2.3 Using FFT to De-Skew................................16 5.2.3 Using FFT to De-Skew................................16
5.2.4 Using Compression to De-Skew........................16 5.2.4 Using S-Boxes to De-Skew............................16
5.2.5 Using Compression to De-Skew........................17
5.3 Existing Hardware Can Be Used For Randomness..........17 5.3 Existing Hardware Can Be Used For Randomness..........17
5.3.1 Using Existing Sound/Video Input....................17 5.3.1 Using Existing Sound/Video Input....................17
5.3.2 Using Existing Disk Drives..........................17 5.3.2 Using Existing Disk Drives..........................18
5.4 Ring Oscillator Sources...............................18
6. Recommended Non-Hardware Strategy......................18
6.1 Mixing Functions......................................18
6.1.1 A Trivial Mixing Function...........................18
6.1.2 Stronger Mixing Functions...........................19
6.1.3 Diff-Hellman as a Mixing Function...................20
6.1.4 Using a Mixing Function to Stretch Random Bits......21
6.1.5 Other Factors in Choosing a Mixing Function.........21
6.2 Non-Hardware Sources of Randomness....................22
6.3 Cryptographically Strong Sequences....................23
6.3.1 Traditional Strong Sequences........................23
6.3.2 The Blum Blum Shub Sequence Generator...............24
7. Key Generation Standards and Examples..................26 6. Recommended Software Strategy..........................19
7.1 US DoD Recommendations for Password Generation........26 6.1 Mixing Functions......................................19
7.2 X9.17 Key Generation..................................26 6.1.1 A Trivial Mixing Function...........................19
7.3 The /dev/random Device under Linux....................27 6.1.2 Stronger Mixing Functions...........................20
7.4 additional example....................................28 6.1.3 Diff-Hellman as a Mixing Function...................21
6.1.4 Using a Mixing Function to Stretch Random Bits......22
6.1.5 Other Factors in Choosing a Mixing Function.........22
6.2 Non-Hardware Sources of Randomness....................23
6.3 Cryptographically Strong Sequences....................24
6.3.1 Traditional Strong Sequences........................24
6.3.2 The Blum Blum Shub Sequence Generator...............25
6.3.3 Entropy Pool Techniques.............................26
More Table of Contents 7. Key Generation Standards and Examples..................28
7.1 US DoD Recommendations for Password Generation........28
7.2 X9.17 Key Generation..................................28
7.3 The /dev/random Device under Linux....................29
8. Examples of Randomness Required........................29 8. Examples of Randomness Required........................31
8.1 Password Generation..................................29 8.1 Password Generation..................................31
8.2 A Very High Security Cryptographic Key................30 8.2 A Very High Security Cryptographic Key................32
8.2.1 Effort per Key Trial................................30 8.2.1 Effort per Key Trial................................32
8.2.2 Meet in the Middle Attacks..........................30 8.2.2 Meet in the Middle Attacks..........................32
9. Conclusion.............................................32 9. Conclusion.............................................34
10. Security Considerations...............................32 10. Security Considerations...............................34
Appendix: Minimal Secure Key Lengths Study................33 Appendix: Minimal Secure Key Lengths Study................35
A.0 Abstract..............................................33 A.0 Abstract..............................................35
A.1. Encryption Plays an Essential Role in Protecting.....34 A.1. Encryption Plays an Essential Role in Protecting.....36
A.1.1 There is a need for information security............34 A.1.1 There is a need for information security............36
A.1.2 Encryption to protect confidentiality...............35 A.1.2 Encryption to protect confidentiality...............37
A.1.3 There are a variety of attackers....................36 A.1.3 There are a variety of attackers....................38
A.1.4 Strong encryption is not expensive..................37 A.1.4 Strong encryption is not expensive..................39
A.2. Brute-Forece is becoming easier......................37 A.2. Brute-Forece is becoming easier......................39
A.3. 40-Bit Key Lengths Offer Virtually No Protection.....39 A.3. 40-Bit Key Lengths Offer Virtually No Protection.....41
A.4. Even DES with 56-Bit Keys Is Increasingly Inadequate.40 A.4. Even DES with 56-Bit Keys Is Increasingly Inadequate.42
A.4.1 DES is no panacea today.............................40 A.4.1 DES is no panacea today.............................42
A.4.2 There are smarter avenues of attack than brute force41 A.4.2 There are smarter attacks than brute force..........43
A.4.3 Other algorithms are similar........................41 A.4.3 Other algorithms are similar........................43
A.5. Appropriate Key Lengths for the Future --- A Proposal42 A.5. Appropriate Key Lengths for the Future - A Proposal..44
A.6 About the Authors.....................................44 A.6 About the Authors.....................................46
A.7 Acknowledgement.......................................45 A.7 Acknowledgement.......................................47
References................................................46 References................................................48
Authors Addresses.........................................49 Authors Addresses.........................................52
File Name and Expiration..................................49 File Name and Expiration..................................52
1. Introduction 1. Introduction
Software cryptography is coming into wider use and is continuing to 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. pervasive.
Systems like IPSEC, TLS, S/MIME, PGP, DNSSEC, Kerberos, etc. are Systems like SSH, IPSEC, TLS, S/MIME, PGP, DNSSEC, Kerberos, etc. are
maturing and becoming a part of the network landscape [DNSSEC, IPSEC, maturing and becoming a part of the network landscape [SSH, DNSSEC,
MAIL*, TLS]. By comparison, when the previous version of this IPSEC, MAIL*, TLS]. By comparison, when the previous version of this
document [RFC 1750] was issued in 1994, about the only cryptographic document [RFC 1750] was issued in 1994, about the only cryptographic
security specification in the IETF was the Privacy Enhanced Mail security specification in the IETF was the Privacy Enhanced Mail
protocol [MAIL PEM]. 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
skipping to change at page 5, line 40 skipping to change at page 5, line 40
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 can easily 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 Best Current Practice describes 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
gives some estimates of the number of random bits required for sample gives some estimates of the number of random bits required for sample
applications. applications.
2. Requirements 2. Requirements
Probably the most commonly encountered randomness requirement today A commonly encountered randomness requirement today is the user
is the user password. This is usually a simple character string. password. This is usually a simple character string. Obviously, if a
Obviously, if a password can be guessed, it does not provide password can be guessed, it does not provide security. (For re-
security. (For re-usable passwords, it is desirable that users be usable passwords, it is desirable that users be able to remember the
able to remember the password. This may make it advisable to use password. This may make it advisable to use pronounceable character
pronounceable character strings or phrases composed on ordinary strings or phrases composed on ordinary words. But this only affects
words. But this only affects the format of the password information, the format of the password information, not the requirement that the
not the requirement that the password be very hard to guess.) 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] or time pads [CRYPTO*] or the US Data Encryption Standard [DES] or
Advanced Encryption Standard [AES], the parties who wish to Advanced Encryption Standard [AES], the parties who wish to
communicate confidentially and/or with authentication must all know communicate confidentially and/or with authentication must all know
the same secret key. In other cases, using what are called the same secret key. In other cases, using what are called
asymmetric or "public key" cryptographic techniques, keys come in asymmetric or "public key" cryptographic techniques, keys come in
pairs. One key of the pair is private and must be kept secret by one 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 party, the other is public and can be published to the world. It is
computationally infeasible to determine the private key from the computationally infeasible to determine the private key from the
public key. [ASYMMETRIC, CRYPTO*] public key and knowledge of the public is of no help to an adversary.
[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 a further need for randomness. The public key Digital
Signature Algorithm devused by the US National Institute of Standards Signature Algorithm devised 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
signature. And encrypting with a one time pad, in principle the [DSS]. 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
randomness equal to all the messages to be processed. randomness equal to all the messages to be processed [CRYPTO*].
In most of these cases, an adversary can try to determine the 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 "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 key is enough smaller than the message that the correct key can be
uniquely identified.) The probability of an adversary succeeding at uniquely identified.) The probability of an adversary succeeding at
this must be made acceptably low, depending on the particular this must be made acceptably low, depending on the particular
application. The size of the space the adversary must search is application. The size of the space the adversary must search is
related to the amount of key "information" present in the information related to the amount of key "information" present in the information
theoretic sense [SHANNON]. This depends on the number of different theoretic sense [SHANNON]. This depends on the number of different
secret values possible and the probability of each value as follows: secret values possible and the probability of each value as follows:
----- -----
\ \
Bits-of-info = \ - p * log ( p ) Bits-of-info = \ - p * log ( p )
/ i 2 i / i 2 i
/ /
----- -----
where i varies from 1 to the number of possible secret values and p where i counts 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 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 less than one, the log will be negative so each term in the sum will
be non-negative.) be non-negative.)
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
skipping to change at page 8, line 21 skipping to change at page 8, line 21
[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,
sampling, numerical analysis, testing computer programs, decision sampling, numerical analysis, testing computer programs, decision
making, and games. None of these have the same characteristics as 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 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. could there be an adversary trying to find the random quantity.
However, in these cases, the adversary normally has only a single However, in these cases, the adversary normally has only a single
chance to use a guessed value. In guessing passwords or attempting chance to use a guessed value. In guessing passwords or attempting
to break an encryption scheme, the adversary normally has many, to break an encryption scheme, the adversary normally has many,
perhaps unlimited, chances at guessing the correct value and should perhaps unlimited, chances at guessing the correct value because they
be assumed to be aided by a computer. can store the message they are trying to break and repeatedly attack
it. They should also be assumed to be aided by a computer.
For testing the "randomness" of numbers, Knuth suggests a variety of For testing the "randomness" of numbers, Knuth suggests a variety of
measures including statistical and spectral. These tests check measures including statistical and spectral. These tests check
things like autocorrelation between different parts of a "random" things like autocorrelation between different parts of a "random"
sequence or distribution of its values. They could be met by a sequence or distribution of its values. But they could be met by a
constant stored random sequence, such as the "random" sequence constant stored random sequence, such as the "random" sequence
printed in the CRC Standard Mathematical Tables [CRC]. printed in the CRC Standard Mathematical Tables [CRC].
A typical pseudo-random number generation technique, known as a A typical pseudo-random number generation technique, known as a
linear congruence pseudo-random number generator, is modular linear congruence pseudo-random number generator, is modular
arithmetic where the N+1th value is calculated from the Nth value by arithmetic where the value numbered N+1 is calculated from the value
numbered N by
V = ( V * a + b )(Mod c) V = ( V * a + b )(Mod c)
N+1 N N+1 N
The above technique has a strong relationship to linear shift The above technique has a strong relationship to linear shift
register pseudo-random number generators, which are well understood register pseudo-random number generators, which are well understood
cryptographically [SHIFT*]. In such generators bits are introduced cryptographically [SHIFT*]. In such generators bits are introduced
at one end of a shift register as the Exclusive Or (binary sum at one end of a shift register as the Exclusive Or (binary sum
without carry) of bits from selected fixed taps into the register. without carry) of bits from selected fixed taps into the register.
For example: For example:
skipping to change at page 12, line 28 skipping to change at page 12, line 28
4.4 The Fallacy of Selection from a Large Database 4.4 The Fallacy of Selection from a Large Database
Another strategy that can give a misleading appearance of Another strategy that can give a misleading appearance of
unpredictability is selection of a quantity randomly from a database unpredictability is selection of a quantity randomly from a database
and assume that its strength is related to the total number of bits and assume that its strength is related to the total number of bits
in the database. For example, typical USENET servers process many in the database. For example, typical USENET servers process many
megabytes of information per day. Assume a random quantity was megabytes of information per day. Assume a random quantity was
selected by fetching 32 bytes of data from a random starting point in selected by fetching 32 bytes of data from a random starting point in
this data. This does not yield 32*8 = 256 bits worth of this data. This does not yield 32*8 = 256 bits worth of
unguessability. Even after allowing that much of the data is human unguessability. Even after allowing that much of the data is human
language and probably has more like 2 or 3 bits of information per language and probably has no more than 2 or 3 bits of information per
byte, it doesn't yield 32*2.5 = 80 bits of unguessability. For an byte, it doesn't yield 32*2 = 64 bits of unguessability. For an
adversary with access to the same usenet database the unguessability adversary with access to the same usenet database the unguessability
rests only on the starting point of the selection. That is perhaps a rests only on the starting point of the selection. That is perhaps a
little over a couple of dozen bits of unguessability. little over a couple of dozen bits of unguessability.
The same argument applies to selecting sequences from the data on a The same argument applies to selecting sequences from the data on a
CD/DVD recording or any other large public database. If the CD/DVD recording or any other large public database. If the
adversary has access to the same database, this "selection from a adversary has access to the same database, this "selection from a
large volume of data" step buys very little. However, if a selection large volume of data" step buys very little. However, if a selection
can be made from data to which the adversary has no access, such as can be made from data to which the adversary has no access, such as
system buffers on an active multi-user system, it may be of help. system buffers on an active multi-user system, it may be of help.
5. Hardware for Randomness 5. Hardware for Randomness
Is there any hope for strong portable randomness in the future? Is there any hope for true strong portable randomness in the future?
There might be. All that's needed is a physical source of There might be. All that's needed is a physical source of
unpredictable numbers. unpredictable numbers.
A thermal noise or radioactive decay source and a fast, free-running A thermal noise (sometimes called Johnson noise in integrated
circuits) or radioactive decay source and a fast, free-running
oscillator would do the trick directly [GIFFORD]. This is a trivial oscillator would do the trick directly [GIFFORD]. This is a trivial
amount of hardware, and could easily be included as a standard part amount of hardware, and could easily be included as a standard part
of a computer system's architecture. Furthermore, any system with a of a computer system's architecture. Furthermore, any system with a
spinning disk or the like has an adequate source of randomness spinning disk or ring oscillator and a stable (crystal) time source
[DAVIS]. All that's needed is the common perception among computer or the like has an adequate source of randomness ([DAVIS] and Section
5.4). 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 AES, the key can be 128 The answer is 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 bits and, as we show in an example in Section 8, even the highest
security system is unlikely to require a keying material of much over security system is unlikely to require a keying material of much over
200 bits. If a series of keys are needed, they can be generated from 200 bits. If a series of keys are needed, they can be generated from
a strong random seed using a cryptographically strong sequence as a strong random seed using a cryptographically strong sequence as
explained in Section 6.3. A few hundred random bits generated once a explained in Section 6.3. A few hundred random bits generated at
day would be enough using such techniques. Even if the random bits start up or once a day would be enough using such techniques. Even
are generated as slowly as one per second and it is not possible to if the random bits are generated as slowly as one per second and it
overlap the generation process, it should be tolerable in high is not possible to overlap the generation process, it should be
security applications to wait 200 seconds occasionally. tolerable in high 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-
uniform it is to bound performance. Two simple techniques to de-skew uniform it is to bound performance. Simple techniques to de-skew the
the bit stream are given below and stronger techniques are mentioned bit stream are given below and stronger techniques are mentioned in
in Section 6.1.2 below. Section 6.1.2 below.
5.2.1 Using Stream Parity to De-Skew 5.2.1 Using Stream Parity to De-Skew
Consider taking a sufficiently long string of bits and map the string Consider taking a sufficiently long string of bits and map the string
to "zero" or "one". The mapping will not yield a perfectly uniform to "zero" or "one". The mapping will not yield a perfectly uniform
distribution, but it can be as close as desired. One mapping that 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 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 advantages that it is robust across all degrees of skew up to the
estimated maximum skew and is absolutely trivial to implement in estimated maximum skew and is absolutely trivial to implement in
hardware. hardware.
skipping to change at page 16, line 28 skipping to change at page 16, line 28
When real world data consists of strongly biased or correlated bits, When real world data consists of strongly biased or correlated bits,
it may still contain useful amounts of randomness. This randomness it may still contain useful amounts of randomness. This randomness
can be extracted through use of the discrete Fourier transform or its can be extracted through use of the discrete Fourier transform or its
optimized variant, the FFT. optimized variant, the FFT.
Using the Fourier transform of the data, strong correlations can be Using the Fourier transform of the data, strong correlations can be
discarded. If adequate data is processed and remaining correlations discarded. If adequate data is processed and remaining correlations
decay, spectral lines approaching statistical independence and decay, spectral lines approaching statistical independence and
normally distributed randomness can be produced [BRILLINGER]. normally distributed randomness can be produced [BRILLINGER].
5.2.4 Using Compression to De-Skew 5.2.4 Using S-Boxes to De-Skew
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 which would have the
effect of concentrating limited entropy in the inputs into the
output.
S-Boxes sometimes incorporate bent boolean functions which are
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". Repeated application or
cascades of such boxes can be used to de-skew. [SBOX*]
5.2.5 Using Compression to De-Skew
Reversible compression techniques also provide a crude method of de- Reversible compression techniques also provide a crude method of de-
skewing a skewed bit stream. This follows directly from the skewing a skewed bit stream. This follows directly from the
definition of reversible compression and the formula in Section 2 definition of reversible compression and the formula in Section 2
above for the amount of information in a sequence. Since the above for the amount of information in a sequence. Since the
compression is reversible, the same amount of information must be compression is reversible, the same amount of information must be
present in the shorter output than was present in the longer input. present in the shorter output than was present in the longer input.
By the Shannon information equation, this is only possible if, on By the Shannon information equation, this is only possible if, on
average, the probabilities of the different shorter sequences are average, the probabilities of the different shorter sequences are
more uniformly distributed than were the probabilities of the longer more uniformly distributed than were the probabilities of the longer
sequences. Thus the shorter sequences are de-skewed relative to the sequences. Thus the shorter sequences must be de-skewed relative to
input. the input.
However, many compression techniques add a somewhat predictable However, many compression techniques add a somewhat predictable
preface to their output stream and may insert such a sequence again preface to their output stream and may insert such a sequence again
periodically in their output or otherwise introduce subtle patterns periodically in their output or otherwise introduce subtle patterns
of their own. They should be considered only a rough technique of their own. They should be considered only a rough technique
compared with those described above or in Section 6.1.2. At a compared with those described above or in Section 6.1.2. At a
minimum, the beginning of the compressed sequence should be skipped minimum, the beginning of the compressed sequence should be skipped
and only later bits used for applications requiring random bits. and only later bits used for applications requiring random bits.
5.3 Existing Hardware Can Be Used For Randomness 5.3 Existing Hardware Can Be Used For Randomness
skipping to change at page 17, line 28 skipping to change at page 18, line 4
essentially thermal noise. essentially thermal noise.
For example, on a SPARCstation, one can read from the /dev/audio For example, on a SPARCstation, one can read from the /dev/audio
device with nothing plugged into the microphone jack. Such data is device with nothing plugged into the microphone jack. Such data is
essentially random noise although it should not be trusted without essentially random noise although it should not be trusted without
some checking in case of hardware failure. It will, in any case, some checking in case of hardware failure. It will, in any case,
need to be de-skewed as described elsewhere. need to be de-skewed as described elsewhere.
Combining this with compression to de-skew one can, in UNIXese, Combining this with compression to de-skew one can, in UNIXese,
generate a huge amount of medium quality random data by doing generate a huge amount of medium quality random data by doing
cat /dev/audio | compress - >random-bits-file cat /dev/audio | compress - >random-bits-file
5.3.2 Using Existing Disk Drives 5.3.2 Using Existing Disk Drives
Disk drives have small random fluctuations in their rotational speed Disk drives have small random fluctuations in their rotational speed
due to chaotic air turbulence [DAVIS]. By adding low level disk seek due to chaotic air turbulence [DAVIS]. By adding low level disk seek
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, such as FFT (see
(see section 5.2.3). Nevertheless experimentation has shown that, section 5.2.3). Nevertheless experimentation has shown that, with
with such processing, disk drives easily produce 100 bits a minute or such processing, most 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
unlikely. unlikely.
6. Recommended Non-Hardware Strategy 5.4 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
precise fixed frequency, say one determined by a stable crystal
oscialltor, some amount of entropy can be extracted due to slight
variations in the free-running osciallator.
Such bits will have to be heavily de-skewed as disk rotation timings
must be (Section 5.3.2). An engineering study would be needed to
determine the amount of entropy being produced depending on the
particular design. It may be possible to increase the rate of entropy
by xor'ing sampled values from a few ring osciallators with
relatively prime lengths or the like. In any case, this can be a
good, medium speed source whose cost is a trivial number of gates by
modern standards.
6. Recommended Software 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 happen to be fixed or easily
guessable. This may be advisable even with a good hardware source, guessable. This may be advisable even with a good hardware source,
as 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
skipping to change at page 20, line 13 skipping to change at page 21, line 13
produces 128 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 encryption functions non-linear function of all input bits. Other encryption functions
with this characteristic, such as [DES], can also be used by with this characteristic, such as [DES], can also be used by
considering 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 Standards hashing functions such as The US Government Secure Hash Standards
[SHA*] 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, SHA-1 produces input bits. The MD* series produce 128 bits of output, SHA-1 produces
160 bits, and SHA-256 and SHA-512 produce 256 and 512 bits 160 bits, and other SHA functions produce larger numbers of bits.
respectively.
Although the message digest functions are designed for variable Although the message digest functions are designed for variable
amounts of input, AES 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 128 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 128 bit data quantity and successive the inputs can be packed into a 128 bit data quantity and successive
AES 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 AES in Electronic Codebook Mode [DES successively encrypt using AES in Electronic Codebook Mode [DES
MODES]. If more than 128 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 AES 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
skipping to change at page 21, line 43 skipping to change at page 22, line 42
documented and implemented with hardware and software implementations documented and implemented with hardware and software implementations
available all over the world including source code available on the available all over the world including source code available on the
Internet. The SHA* family are younger algorithms but there is no Internet. The SHA* family are younger algorithms but there is no
particular reason to believe they are flawed. Both SHA* and MD5 were particular reason to believe they are flawed. Both SHA* and MD5 were
derived from the earlier MD4 algorithm. Some signs of weakness have derived from the earlier MD4 algorithm. Some signs of weakness have
been found in MD4 and MD5. They all have source code available [SHA*, been found in MD4 and MD5. They all have source code available [SHA*,
MD*]. MD*].
AES and SHA* 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,
as was DES. While this is the cause of much speculation and doubt, as was DES. While this has been the cause of much speculation and
investigation of DES over the years has indicated that NSA doubt, investigation of DES over the years has indicated that NSA
involvement in modifications to its design, which originated with involvement in modifications to its design, which originated with
IBM, was primarily to strengthen it. No concealed or special IBM, was primarily to strengthen it. No concealed or special
weakness has been found in DES. It is almost certain that the NSA weakness has been found in DES. It is almost certain that the NSA
modifications to MD4 to produce the SHA* similarly strengthened these modifications to MD4 to produce the SHA* similarly strengthened these
algorithms, possibly against threats not yet known in the public algorithms, possibly against threats not yet known in the public
cryptographic community. cryptographic community.
AES, DES, SHA*, MD4, and MD5 are royalty free for all purposes. AES, DES, SHA*, MD4, and MD5 are believed to be royalty free for all
Continued advances in crypography and computing power have cast some purposes. Continued advances in crypography and computing power have
doubts on MD4 and MD5 so their use is NOT RECOMMENDED. cast doubts on MD4 and MD5 so their use is generally not recommended.
Another advantage of the SHA* or similar hashing algorithms over Another advantage of the SHA* or similar hashing algorithms over
encryption algorithms in the past was that they are not subject to encryption algorithms in the past was that they are not subject to
the same regulations imposed by the US Government prohibiting the the same regulations imposed by the US Government prohibiting the
unlicensed export or import of encryption/decryption software and unlicensed export or import of encryption/decryption software and
hardware. hardware.
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, especially at randomness. However, on a small single user or embedded system,
start up, it might be possible for an adversary to assemble a similar especially at start up, it might be possible for an adversary to
configuration. This could give the adversary inputs to the mixing assemble a similar configuration. This could give the adversary
process that were sufficiently correlated to those used originally as inputs to the mixing process that were sufficiently correlated to
to make exhaustive search practical. those used originally as 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 at most a few bits of randomness
inter-keystroke interval is unique in the sequence up to that point if the inter-keystroke interval is unique in the sequence up to that
and a similar assumption if the key hit is unique but assuming that point and a similar assumption if the key hit is unique but assuming
no bits of randomness are present in the initial key value or if the that no bits of randomness are present in the initial key value or if
timing or key value duplicate previous values. The results of mixing the timing or key value duplicate previous values. The results of
these timings and characters typed could be further combined with mixing these timings and characters typed could be further combined
clock values and other inputs. with clock values and other inputs.
This strategy may make practical portable code to produce good random This strategy may make practical portable code to produce good random
numbers for security even if some of the inputs are very weak on some 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 of the target systems. However, it may still fail against a high
grade attack on small single user systems, especially if the grade attack on small single user or embedded systems, especially if
adversary has ever been able to observe the generation process in the the adversary has ever been able to observe the generation process in
past. A hardware based random source is still preferable. the past. A hardware based random source is still preferable.
6.3 Cryptographically Strong Sequences 6.3 Cryptographically Strong Sequences
In cases where a series of random quantities must be generated, an In cases where a series of random quantities must be generated, an
adversary may learn some values in the sequence. In general, they adversary may learn some values in the sequence. In general, they
should not be able to predict other values from the ones that they should not be able to predict other values from the ones that they
know. know.
The correct technique is to start with a strong random seed, take The correct technique is to start with a strong random seed, take
cryptographically strong steps from that seed [CRYPTO2, CRYPTO3], and cryptographically strong steps from that seed [CRYPTO2, CRYPTO3], and
do not reveal the complete state of the generator in the sequence do not reveal the complete state of the generator in the sequence
elements. If each value in the sequence can be calculated in a fixed elements. If each value in the sequence can be calculated in a fixed
way from the previous value, then when any value is compromised, all way from the previous value, then when any value is compromised, all
future values can be determined. This would be the case, for future values can be determined. This would be the case, for
example, if each value were a constant function of the previously example, if each value were a constant function of the previously
used values, even if the function were a very strong, non-invertible used values, even if the function were a very strong, non-invertible
message digest function. message digest function.
It should be noted that if your technique for generating a sequence (It should be noted that if your technique for generating a sequence
of key values is fast enough, it can trivially be used as the basis of key values is fast enough, it can trivially be used as the basis
for a confidentiality system. If two parties use the same sequence for a confidentiality system. If two parties use the same sequence
generating technique and start with the same seed material, they will generating technique and start with the same seed material, they will
generate identical sequences. These could, for example, be xor'ed at generate identical sequences. These could, for example, be xor'ed at
one end with data being send, encrypting it, and xor'ed with this one end with data being send, encrypting it, and xor'ed with this
data as received, decrypting it due to the reversible properties of data as received, decrypting it due to the reversible properties of
the xor operation. the xor operation.)
6.3.1 Traditional Strong Sequences 6.3.1 Traditional Strong Sequences
A traditional way to achieve a strong sequence has been to have the A traditional way to achieve a strong sequence has been to have the
values be produced by hashing the quantities produced by values be produced by hashing the quantities produced by
concatenating the seed with successive integers or the like and then concatenating the seed with successive integers or the like and then
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 was recommended by the US Government
in connection with DES [DES MODES] but should be avoided for reasons in connection with DES [DES MODES] but should be avoided for reasons
described below. described below.
+---------------+ +---------------+
| V | | V |
| | n | | | n |--+
+--+------------+ +--+------------+ |
| | +---------+ | | +---------+
| +---------> | | +-----+ | +---> | | +-----+
+--+ | Encrypt | <--- | Key | +--+ | Encrypt | <--- | Key |
| +-------- | | +-----+ | +-------- | | +-----+
| | +---------+ | | +---------+
V V V V
+------------+--+ +------------+--+
| V | | | V | |
| n+1 | | n+1 |
+---------------+ +---------------+
Note that if a shift of one is used, this is the same as the shift Note that if a shift of one is used, this is the same as the shift
skipping to change at page 26, line 5 skipping to change at page 26, line 41
i i
( ( 2 )(Mod (( p - 1 ) * ( q - 1 )) ) ) ( ( 2 )(Mod (( p - 1 ) * ( q - 1 )) ) )
s = ( s )(Mod n) s = ( s )(Mod n)
i 0 i 0
This means that in applications where many keys are generated in this This means that in applications where many keys are generated in this
fashion, it is not necessary to save them all. Each key can be fashion, it is not necessary to save them all. Each key can be
effectively indexed and recovered from that small index and the effectively indexed and recovered from that small index and the
initial s and n. initial s and n.
6.3.3 Entropy Pool Techniques
Many modern pseudo random number sources utilize the technique of
maintaining a "pool" of bits and providing operations for strongly
mixing input with some randomness into the pool and extracting psuedo
random bits from the pool. This is illustred in the figure below.
+--------+ +------+ +---------+
--->| Mix In |--->| POOL |--->| Extract |--->
| Bits | | | | Bits |
+--------+ +------+ +---------+
^ V
| |
+-----------+
Bits to be feed into the pool can be any of the various hardware,
environmental, or user input sources discussed above. It is also
common to save the state of the pool on shut down and restore it on
re-starting, if stable storage is available.
In fact, all of the [MD*] and [SHA*] message digest functions are
implemented by internally maintaining a pool substantially larger
than their ultimate output into which the bytes of the message are
mixed and from which the ultimate message digest is extracted. Thus
the figure above can be implemented by using parts of the message
digest code to strongly mix in any new bit supplied and to compute
output bits based on the pool. However, additional code is needed so
that any number of bits can be extracted and appropriate feedback
from the output process is mixed into the pool so as to produce a
strong pseudo-random output stream.
Care must be taken that enough entropy has been added to the pool to
support particular output uses desired. See Section 7.3 for for more
details on an example implementation and [RSA BULL1] for similar
suggestions.
7. Key Generation Standards and Examples 7. Key Generation Standards and Examples
Several public standards and widely deplyed examples are now in place Several public standards and widely deplyed examples are now in place
for the generation of keys without special hardware. Two standards for the generation of keys without special hardware. Two standards
are described below. Both use DES but any equally strong or stronger are described below. Both use DES but any equally strong or stronger
mixing function could be substituted. Then a few widely deployed mixing function could be substituted. Then a few widely deployed
examples are described. examples are described.
7.1 US DoD Recommendations for Password Generation 7.1 US DoD Recommendations for Password Generation
skipping to change at page 27, line 27 skipping to change at page 29, line 27
g should be used in calculating the next s. g should be used in calculating the next s.
7.3 The /dev/random Device under Linux 7.3 The /dev/random Device under Linux
The Linux operating system provides a Kernel resident random number The Linux operating system provides a Kernel resident random number
generator. This generator makes use of events captured by the Kernel generator. This generator makes use of events captured by the Kernel
during normal system operation. during normal system operation.
The generator consists of a random pool of bytes, by default 512 The generator consists of a random pool of bytes, by default 512
bytes (represented as 128, 4 byte integers). When an event occurs, bytes (represented as 128, 4 byte integers). When an event occurs,
such as a disk drive interrupt, the time of the event is xored into such as a disk drive interrupt, the time of the event is xor'ed into
the pool and the pool is stirred via a primitive polynomial of degree the pool and the pool is stirred via a primitive polynomial of degree
128. The pool itself is treated as a ring buffer, with new data 128. The pool itself is treated as a ring buffer, with new data
being xored (after stirring with the polynomial) across the entire being xor'ed (after stirring with the polynomial) across the entire
pool. pool.
Each call that adds entropy to the pool estimates the amount of Each call that adds entropy to the pool estimates the amount of
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
skipping to change at page 28, line 35 skipping to change at page 31, line 5
reasonable risk. reasonable risk.
To obtain random numbers under Linux, all an application needs to do To obtain random numbers under Linux, all an application needs to do
is open either /dev/random or /dev/urandom and read the desired is open either /dev/random or /dev/urandom and read the desired
number of bytes. number of bytes.
The Linux Random device was written by Theodore Ts'o. It is based The Linux Random device was written by Theodore Ts'o. It is based
loosely on the random number generator in PGP 2.X and PGP 3.0 (aka loosely on the random number generator in PGP 2.X and PGP 3.0 (aka
PGP 5.0). PGP 5.0).
7.4 additional example
(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 In addition [ORMAN] and [RSA BULL13] provide information on the
that should be used for exchanging symmetric keys. 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
skipping to change at page 30, line 19 skipping to change at page 32, line 19
encryption / decryption between two parties. Assume an adversary can encryption / decryption between two parties. Assume an adversary can
observe communications and knows the algorithm being used. Within observe communications and knows the algorithm being used. Within
the field of random possibilities, the adversary can try key values the field of random possibilities, the adversary can try key values
in hopes of finding the one in use. Assume further that brute force in hopes of finding the one in use. Assume further that brute force
trial of keys is the best the adversary can do. trial of keys is the best the adversary can do.
8.2.1 Effort per Key Trial 8.2.1 Effort per Key Trial
How much effort will it take to try each key? For very high security How much effort will it take to try each key? For very high security
applications it is best to assume a low value of effort. This applications it is best to assume a low value of effort. This
questions is considered in detail in Appendix A. It concludes that a question is considered in detail in Appendix A. It concludes that a
reasonable key length in 1995 for very high security is in the range reasonable key length in 1995 for very high security is in the range
of 75 to 90 bits and, since the cost of cryptography does not very of 75 to 90 bits and, since the cost of cryptography does not vary
much with they key size, recommends 90 bits. To update these much with they key size, recommends 90 bits. To update these
recommendations, just add 2/3 of a bit per year for Moore's law recommendations, just add 2/3 of a bit per year for Moore's law
[MOORE]. Thus, in the year 2001, this translates to a determination [MOORE]. Thus, in the year 2002, this translates to a determination
that a reasonable key length is in 78 to 93 bit range. that a reasonable key length is in 79 to 94 bit range.
8.2.2 Meet in the Middle Attacks 8.2.2 Meet in the Middle Attacks
If chosen or known plain text and the resulting encrypted text are If chosen or known plain text and the resulting encrypted text are
available, a "meet in the middle" attack is possible if the structure available, a "meet in the middle" attack is possible if the structure
of the encryption algorithm allows it. (In a known plain text of the encryption algorithm allows it. (In a known plain text
attack, the adversary knows all or part of the messages being attack, the adversary knows all or part of the messages being
encrypted, possibly some standard header or trailer fields. In a encrypted, possibly some standard header or trailer fields. In a
chosen plain text attack, the adversary can force some chosen plain chosen plain text attack, the adversary can force some chosen plain
text to be encrypted, possibly by "leaking" an exciting text that text to be encrypted, possibly by "leaking" an exciting text that
skipping to change at page 30, line 47 skipping to change at page 32, 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 the very strong key to a minimum of 176 bits amount of randomness in the very strong key to a minimum of 178 bits
is required for the year 2001 based on the Appendix A analysis. is required for the year 2002 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 deepthorough knowledge of the algorithm. Even if a basic without a deep knowledge of the algorithm. Even if a basic algorithm
algorithm is not subject to a meet in the middle attack, an attempt is not subject to a meet in the middle attack, an attempt to produce
to produce a stronger algorithm by applying the basic algorithm twice a stronger algorithm by applying the basic algorithm twice (or two
(or two different algorithms sequentially) with different keys may different algorithms sequentially) with different keys may gain less
gain less added security than would be expected. Such a composite added security than would be expected. Such a composite algorithm
algorithm would be subject to a meet in the middle attack. 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
spy on commercial traffic for economic advantage. spy on commercial traffic for economic advantage.
It should be noted that key length calculations such at those above It should be noted that key length calculations such at those above
are controversial and depend on various assumptions about the are controversial and depend on various assumptions about the
cryptographic algorithms in use. In some cases, a professional with cryptographic algorithms in use. In some cases, a professional with
a deep knowledge of code breaking techniques and of the strength of a deep knowledge of code breaking techniques and of the strength of
the algorithm in use could be satisfied with less than half of the the algorithm in use could be satisfied with less than half of the
176 bit key size derived above. 178 bit key size derived above.
9. Conclusion 9. Conclusion
Generation of unguessable "random" secret quantities for security use Generation of unguessable "random" secret quantities for security use
is an essential but difficult task. is an essential but difficult task.
We have shown that hardware techniques to produce such randomness Hardware techniques to produce such randomness would be relatively
would be relatively simple. In particular, the volume and quality simple. In particular, the volume and quality would not need to be
would not need to be high and existing computer hardware, such as high and existing computer hardware, such as disk drives, can be
disk drives, can be used. used.
Computational techniques are available to process low quality random Computational techniques are available to process low quality random
quantities from multiple sources or a larger quantity of such low quantities from multiple sources or a larger quantity of such low
quality input from one source and produce a smaller quantity of quality input from one source and produce a smaller quantity of
higher quality, less predictable key material. In the absence of higher quality keying material. In the absence of hardware sources
hardware sources of randomness, a variety of user and software of randomness, a variety of user and software sources can frequently,
sources can frequently be used instead with care; however, most with care, be used instead; however, most modern systems already have
modern systems already have hardware, such as disk drives or audio hardware, such as disk drives or audio input, that could be used to
input, that could be used to produce high quality randomness. produce high quality randomness.
Once a sufficient quantity of high quality seed key material (a few Once a sufficient quantity of high quality seed key material (a
hundred bits) is available, strong computational techniques are couple of hundred bits) is available, computational techniques are
available to produce cryptographically strong sequences of available to produce cryptographically strong sequences of
unpredicatable quantities from this seed material. unpredicatable quantities from this seed material.
10. Security Considerations 10. Security Considerations
The entirety of this document concerns techniques and recommendations The entirety of this document concerns techniques and recommendations
for generating unguessable "random" quantities for use as passwords, for generating unguessable "random" quantities for use as passwords,
cryptographic keys, initialiazation vectors, sequence numbers, and cryptographic keys, initialiazation vectors, sequence numbers, and
similar security uses. similar security uses.
skipping to change at page 34, line 14 skipping to change at page 36, line 14
significantly greater than that of weak encryption. Therefore, to significantly greater than that of weak encryption. Therefore, to
provide adequate protection against the most serious threats --- provide adequate protection against the most serious threats ---
well-funded commercial enterprises or government intelligence well-funded commercial enterprises or government intelligence
agencies --- keys used to protect data today should be at least 75 agencies --- keys used to protect data today should be at least 75
bits long. To protect information adequately for the next 20 years bits long. To protect information adequately for the next 20 years
in the face of expected advances in computing power, keys in newly- in the face of expected advances in computing power, keys in newly-
deployed systems should be at least 90 bits long. deployed systems should be at least 90 bits long.
A.1. Encryption Plays an Essential Role in Protecting A.1. Encryption Plays an Essential Role in Protecting
the Privacy of Electronic Information the Privacy of Electronic Information"
A.1.1 There is a need for information security A.1.1 There is a need for information security
As we write this paper in late 1995, the development of As we write this paper in late 1995, the development of
electronic commerce and the Global Information Infrastructure is at a electronic commerce and the Global Information Infrastructure is at a
critical juncture. The dirt paths of the middle ages only became critical juncture. The dirt paths of the middle ages only became
highways of business and culture after the security of travelers and highways of business and culture after the security of travelers and
the merchandise they carried could be assured. So too the the merchandise they carried could be assured. So too the
information superhighway will be an ill-traveled road unless information superhighway will be an ill-traveled road unless
information, the goods of the Information Age, can be moved, stored, information, the goods of the Information Age, can be moved, stored,
skipping to change at page 41, line 39 skipping to change at page 43, line 39
searching through the keys --- is entirely feasible against many searching through the keys --- is entirely feasible against many
widely used systems. Another is that the keylengths we discuss are widely used systems. Another is that the keylengths we discuss are
always minimal. As discussed earlier, prudent designs might use keys always minimal. As discussed earlier, prudent designs might use keys
twice or three times as long to provide a margin of safety. twice or three times as long to provide a margin of safety.
A.4.3 Other algorithms are similar A.4.3 Other algorithms are similar
The Analysis for Other Algorithms Is Roughly Comparable. The Analysis for Other Algorithms Is Roughly Comparable.
The above analysis has focused on the time and money required to The above analysis has focused on the time and money required to
find a key to decrypt information using the RC4 algorithm with a 40- find a key to decrypt information using the RC4 algorithm with a
bit key or the DES algorithm with its 56-bit key, but the results are 40-bit key or the DES algorithm with its 56-bit key, but the results
not peculiar to these ciphers. Although each algorithm has its own are not peculiar to these ciphers. Although each algorithm has its
particular characteristics, the effort required to find the keys of own particular characteristics, the effort required to find the keys
other ciphers is comparable. There may be some differences as the of other ciphers is comparable. There may be some differences as the
result of implementation procedures, but these do not materially result of implementation procedures, but these do not materially
affect the brute-force breakability of algorithms with roughly affect the brute-force breakability of algorithms with roughly
comparable key lengths. comparable key lengths.
Specifically, it has been suggested at times that differences in Specifically, it has been suggested at times that differences in
set-up procedures, such as the long key-setup process in RC4, result set-up procedures, such as the long key-setup process in RC4, result
in some algorithms having effectively longer keys than others. For in some algorithms having effectively longer keys than others. For
the purpose of our analysis, such factors appear to vary the the purpose of our analysis, such factors appear to vary the
effective key length by no more than about eight bits. effective key length by no more than about eight bits.
skipping to change at page 46, line 7 skipping to change at page 48, 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, [AES] - "Specification of theAdvanced Encryption Standard (AES)",
Department of Commerce, National Institute of Standards and United States of America, Department of Commerce, National Institute
Technology, Federal Information Processing Standard (FIPS) xxx. of Standards and Technology, Federal Information Processing Standard
197, November 2001.
[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 46, line 39 skipping to change at page 48, line 40
Carl H. Meyer & Stephen M. Matyas. Carl H. Meyer & Stephen M. Matyas.
[CRYPTO3] - "Applied Cryptography: Protocols, Algorithsm, and Source [CRYPTO3] - "Applied Cryptography: Protocols, Algorithsm, and Source
Code in C", Second Edition, John Wiley & Sons, 1996, Bruce Schneier. Code in C", Second Edition, John Wiley & Sons, 1996, Bruce Schneier.
[DAVIS] - "Cryptographic Randomness from Air Turbulence in Disk [DAVIS] - "Cryptographic Randomness from Air Turbulence in Disk
Drives", Advances in Cryptology - Crypto '94, Springer-Verlag Lecture Drives", Advances in Cryptology - Crypto '94, Springer-Verlag Lecture
Notes in Computer Science #839, 1984, Don Davis, Ross Ihaka, and Notes in Computer Science #839, 1984, Don Davis, Ross Ihaka, and
Philip Fenstermacher. Philip Fenstermacher.
[DES] - "Data Encryption Standard", United States of America, [DES] - "Data Encryption Standard", United States of America,
Department of Commerce, National Institute of Standards and Department of Commerce, National Institute of Standards and
Technology, Federal Information Processing Standard (FIPS) 46-1. Technology, Federal Information Processing Standard (FIPS) 46-3,
October 1999.
- "Data Encryption Algorithm", American National Standards Institute, - "Data Encryption Algorithm", American National Standards Institute,
ANSI X3.92-1981. ANSI X3.92-1981.
(See also FIPS 112, Password Usage, which includes FORTRAN code for (See also FIPS 112, Password Usage, which includes FORTRAN code for
performing DES.) performing DES.)
[DES MODES] - "DES Modes of Operation", United States of America, [DES MODES] - "DES Modes of Operation", United States of America,
Department of Commerce, National Institute of Standards and Department of Commerce, National Institute of Standards and
Technology, Federal Information Processing Standard (FIPS) 81. Technology, Federal Information Processing Standard (FIPS) 81,
December 1980.
- Data Encryption Algorithm - Modes of Operation, American National - Data Encryption Algorithm - Modes of Operation, American National
Standards Institute, ANSI X3.106-1983. Standards Institute, ANSI X3.106-1983.
[D-H] - "New Directions in Cryptography", IEEE Transactions on [D-H] - "New Directions in Cryptography", IEEE Transactions on
Information Technology, November, 1976, Whitfield Diffie and Martin Information Technology, November, 1976, Whitfield Diffie and Martin
E. Hellman. E. Hellman.
[DNSSEC] - RFC 2535, "Domain Name System Security Extensions", D. [DNSSEC] - RFC 2535, "Domain Name System Security Extensions", D.
Eastlake, March 1999. Eastlake, March 1999.
[DoD] - "Password Management Guideline", United States of America, [DoD] - "Password Management Guideline", United States of America,
Department of Defense, Computer Security Center, CSC-STD-002-85. Department of Defense, Computer Security Center, CSC-STD-002-85.
(See also FIPS 112, Password Usage, which incorporates CSC-STD-002-85 (See also FIPS 112, Password Usage, which incorporates CSC-STD-002-85
as one of its appendices.) as one of its appendices.)
[DSS] - "Digital Signature Standard (DSS)", United States of America,
Department of Commerce, National Institute of Standards and
Technoloy, Federal Information Processing Standard (FIPS) 186-2,
January 2000.
[GIFFORD] - "Natural Random Number", MIT/LCS/TM-371, September 1988, [GIFFORD] - "Natural Random Number", MIT/LCS/TM-371, September 1988,
David K. Gifford David K. Gifford
[IPSEC] - RFC 2401, "Security Architecture for the Internet [IPSEC] - RFC 2401, "Security Architecture for the Internet
Protocol", S. Kent, R. Atkinson, November 1998 Protocol", S. Kent, R. Atkinson, November 1998
[KNUTH] - "The Art of Computer Programming", Volume 2: Seminumerical [KNUTH] - "The Art of Computer Programming", Volume 2: Seminumerical
Algorithms, Chapter 3: Random Numbers. Addison Wesley Publishing Algorithms, Chapter 3: Random Numbers. Addison Wesley Publishing
Company, Second Edition 1982, Donald E. Knuth. Company, Second Edition 1982, Donald E. Knuth.
skipping to change at page 48, line 12 skipping to change at page 50, line 19
of this document. See "The New Hacker's Dictionary", Third Edition, of this document. See "The New Hacker's Dictionary", Third Edition,
MIT Press, ISBN 0-262-18178-9, Eric S. Raymondm 1996. MIT Press, ISBN 0-262-18178-9, Eric S. Raymondm 1996.
[ORMAN] - "Determining Strengths For Public Keys Used For Exchanging [ORMAN] - "Determining Strengths For Public Keys Used For Exchanging
Symmetric Keys", draft-orman-public-key-lengths-*.txt, Hilarie Orman, Symmetric Keys", draft-orman-public-key-lengths-*.txt, Hilarie Orman,
Paul Hoffman, work in progress. 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.
[RSA BULL1] - "Suggestions for Random Number Generation in Software",
RSA Laboratories Bulletin #1, January 1996.
[RSA BULL13] - "A Cost-Based Security Analysis of Symmetric and
Asymmetric Key Lengths", RSA Laboratories Bulletin #13, Robert
Silverman, April 2000 (revised November 2001).
[SBOX1] - "Practical s-box design", S. Mister, C. Adams, Selected
Areas in Cryptography, 1996.
[SBOX2] - "Perfect Non-linear S-boxes", K. Nyberg, Advances in
Cryptography - Eurocrypt '91 Proceedings, Springer-Verland, 1991.
[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.
[SHA-1] - "Secure Hash Standard", United States of American, National [SHA-1] - "Secure Hash Standard (SHA-1)", United States of American,
Institute of Science and Technology, Federal Information Processing National Institute of Science and Technology, Federal Information
Standard (FIPS) 180-1, April 1993. Processing Standard (FIPS) 180-1, April 1993.
- "US Secure Hash Algorithm 1 (SHA1)", D. Eastlake, P. Jones, draft- - RFC 3174, "US Secure Hash Algorithm 1 (SHA1)", D. Eastlake, P.
eastlake-sha1-01.txt, work in progress. Jones, September 2001.
[SHA-256] - [SHA-2] - "Secure Hash Standard", Draft (SHA-2156/384/512), Federal
Information Processing Standard 180-2, not yet issued.
[SHA-512] - [SSH] - draft-ietf-secsh-*, work in progress.
[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.
Authors Addresses Authors Addresses
Donald E. Eastlake 3rd Donald E. Eastlake 3rd
Motorola Motorola
155 Beaver Street 155 Beaver Street
Milford, MA 01757 USA Milford, MA 01757 USA
Telephone: +1 508-261-5434 (w) Telephone: +1 508-851-8280 (w)
+1 508-634-2066 (h) +1 508-634-2066 (h)
FAX: +1 508-261-4447 (w)
EMail: Donald.Eastlake@motorola.com EMail: Donald.Eastlake@motorola.com
Jeffrey I. Schiller Jeffrey I. Schiller
MIT Room E40-311 MIT Room E40-311
77 Massachusetts Avenue 77 Massachusetts Avenue
Cambridge, MA 02139-4307 USA Cambridge, MA 02139-4307 USA
Telephone: +1 617-253-0161 Telephone: +1 617-253-0161
E-mail: jis@mit.edu E-mail: jis@mit.edu
Steve Crocker Steve Crocker
Longitude Systems, Inc.
Suite 100
1319 Shepard Drive
Sterling, VA 20164 USA
Telephone: +1 703-433-0808 x206
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-02.txt. This is file draft-eastlake-randomness2-03.txt.
It expires October 2001. It expires January 2003.
 End of changes. 79 change blocks. 
196 lines changed or deleted 284 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/