< draft-eastlake-randomness2-04.txt   draft-eastlake-randomness2-05.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 February 2004 January 2003 Expires June 2004 December 2003
Randomness Requirements for Security Randomness Requirements for Security
---------- ------------ --- -------- ---------- ------------ --- --------
<draft-eastlake-randomness2-04.txt> <draft-eastlake-randomness2-05.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
distribute working documents as Internet Drafts. distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
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
skipping to change at page 2, line 43 skipping to change at page 2, line 43
(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 material 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:
Tony Hansen, Sandy Harris Tony Hansen, Sandy Harris
The following persons (in alpahbetic order) contributed to RFC 1750, The following persons (in alphabetic 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, and 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
skipping to change at page 3, line 43 skipping to change at page 3, line 43
5.2.5 Using Compression to De-Skew........................17 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..........................18 5.3.2 Using Existing Disk Drives..........................18
5.4 Ring Oscillator Sources...............................18 5.4 Ring Oscillator Sources...............................18
6. Recommended Software Strategy..........................19 6. Recommended Software Strategy..........................19
6.1 Mixing Functions......................................19 6.1 Mixing Functions......................................19
6.1.1 A Trivial Mixing Function...........................19 6.1.1 A Trivial Mixing Function...........................19
6.1.2 Stronger Mixing Functions...........................20 6.1.2 Stronger Mixing Functions...........................20
6.1.3 Diff-Hellman as a Mixing Function...................21 6.1.3 Diffie-Hellman as a Mixing Function.................21
6.1.4 Using a Mixing Function to Stretch Random Bits......22 6.1.4 Using a Mixing Function to Stretch Random Bits......22
6.1.5 Other Factors in Choosing a Mixing Function.........22 6.1.5 Other Factors in Choosing a Mixing Function.........22
6.2 Non-Hardware Sources of Randomness....................23 6.2 Non-Hardware Sources of Randomness....................23
6.3 Cryptographically Strong Sequences....................24 6.3 Cryptographically Strong Sequences....................24
6.3.1 Traditional Strong Sequences........................24 6.3.1 Traditional Strong Sequences........................24
6.3.2 The Blum Blum Shub Sequence Generator...............25 6.3.2 The Blum Blum Shub Sequence Generator...............25
6.3.3 Entropy Pool Techniques.............................26 6.3.3 Entropy Pool Techniques.............................26
7. Key Generation Standards and Examples..................28 7. Key Generation Standards and Examples..................28
7.1 US DoD Recommendations for Password Generation........28 7.1 US DoD Recommendations for Password Generation........28
7.2 X9.17 Key Generation..................................28 7.2 X9.17 Key Generation..................................28
7.3 The /dev/random Device under Linux....................29
More Table of Contents More Table of Contents
7.3 The /dev/random Device under Linux....................29
8. Examples of Randomness Required........................31 8. Examples of Randomness Required........................31
8.1 Password Generation..................................31 8.1 Password Generation..................................31
8.2 A Very High Security Cryptographic Key................32 8.2 A Very High Security Cryptographic Key................32
8.2.1 Effort per Key Trial................................32 8.2.1 Effort per Key Trial................................32
8.2.2 Meet in the Middle Attacks..........................32 8.2.2 Meet in the Middle Attacks..........................32
9. Conclusion.............................................34 9. Conclusion.............................................34
10. Security Considerations...............................34 10. Security Considerations...............................34
Intellectual Property Considerations......................34 Intellectual Property Considerations......................34
Appendix: Minimal Secure Key Lengths Study................36 Appendix: Minimal Secure Key Lengths Study................36
A.0 Abstract..............................................36 A.0 Abstract..............................................36
A.1. Encryption Plays an Essential Role in Protecting.....37 A.1. Encryption Plays an Essential Role in Protecting.....37
A.1.1 There is a need for information security............37 A.1.1 There is a need for information security............37
A.1.2 Encryption to protect confidentiality...............38 A.1.2 Encryption to protect confidentiality...............38
A.1.3 There are a variety of attackers....................39 A.1.3 There are a variety of attackers....................39
A.1.4 Strong encryption is not expensive..................40 A.1.4 Strong encryption is not expensive..................40
A.2. Brute-Forece is becoming easier......................40 A.2. Brute-Force is becoming easier.......................40
A.3. 40-Bit Key Lengths Offer Virtually No Protection.....42 A.3. 40-Bit Key Lengths Offer Virtually No Protection.....42
A.4. Even DES with 56-Bit Keys Is Increasingly Inadequate.43 A.4. Even DES with 56-Bit Keys Is Increasingly Inadequate.43
A.4.1 DES is no panacea today.............................43 A.4.1 DES is no panacea today.............................43
A.4.2 There are smarter avenues of attack than brute A.4.2 There are smarter avenues of attack than brute force44
force...............................................44
A.4.3 Other algorithms are similar........................44 A.4.3 Other algorithms are similar........................44
A.5. Appropriate Key Lengths for the Future --- A A.5. Appropriate Key Lengths for the Future --- A Proposal45
Proposal.............................................45
A.6 About the Authors.....................................47 A.6 About the Authors.....................................47
A.7 Acknowledgement.......................................48 A.7 Acknowledgement.......................................48
Informative References....................................49 Informative References....................................49
Authors Addresses.........................................53 Authors Addresses.........................................53
File Name and Expiration..................................53 File Name and Expiration..................................53
1. Introduction 1. Introduction
skipping to change at page 21, line 42 skipping to change at page 21, line 42
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 SHA-1 and taking the bottom information in it. Thus hashing it with SHA-1 and taking the bottom
5 bits of the result would yield 5 unbiased random bits as opposed to 5 bits of the result would yield 5 unbiased random bits as opposed to
the single bit given by calculating the parity of the string. the single bit given by calculating the parity of the string.
6.1.3 Diff-Hellman as a Mixing Function 6.1.3 Diffie-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
are uncorrelated. are uncorrelated.
skipping to change at page 30, line 22 skipping to change at page 30, line 22
There are two user exported interfaces. /dev/random returns bytes There are two user exported interfaces. /dev/random returns bytes
from the pool, but blocks when the estimated entropy drops to zero. from the pool, but blocks when the estimated entropy drops to zero.
As entropy is added to the pool from events, more data becomes As entropy is added to the pool from events, more data becomes
available via /dev/random. Random data obtained /dev/random is available via /dev/random. Random data obtained /dev/random is
suitable for key generation for long term keys. suitable for key generation for long term keys.
/dev/urandom works like /dev/random, however it provides data even /dev/urandom works like /dev/random, however it provides data even
when the entropy estimate for the random pool drops to zero. This when the entropy estimate for the random pool drops to zero. This
should be fine for session keys. The risk of continuing to take data should be fine for session keys. The risk of continuing to take data
even when the pools entropy estimate is small is that past output may even when the pool's entropy estimate is small is that past output
be computable from current output provided an attacker can reverse may be computable from current output provided an attacker can
SHA-1. Given that SHA-1 should not be invertible, this is a reverse SHA-1. Given that SHA-1 should not be invertible, this is a
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).
skipping to change at page 40, line 32 skipping to change at page 40, line 32
rarely any need to tailor the strength of cryptography to the rarely any need to tailor the strength of cryptography to the
sensitivity of the information being protected. Even if most of the sensitivity of the information being protected. Even if most of the
information in a system has neither privacy implications nor monetary information in a system has neither privacy implications nor monetary
value, there is no practical or economic reason to design computer value, there is no practical or economic reason to design computer
hardware or software to provide differing levels of encryption for hardware or software to provide differing levels of encryption for
different messages. It is simplest, most prudent, and thus different messages. It is simplest, most prudent, and thus
fundamentally most economical, to employ a uniformly high level of fundamentally most economical, to employ a uniformly high level of
encryption: the strongest encryption required for any information encryption: the strongest encryption required for any information
that might be stored or transmitted by a secure system. that might be stored or transmitted by a secure system.
A.2. Brute-Forece is becoming easier A.2. Brute-Force is becoming easier
Readily Available Technology Makes Brute-Force Decryption Attacks Readily Available Technology Makes Brute-Force Decryption Attacks
Faster and Cheaper. Faster and Cheaper.
The kind of hardware used to mount a brute-force attack against The kind of hardware used to mount a brute-force attack against
an encryption algorithm depends on the scale of the cryptanalytic an encryption algorithm depends on the scale of the cryptanalytic
operation and the total funds available to the attacking enterprise. operation and the total funds available to the attacking enterprise.
In the analysis that follows, we consider three general classes of In the analysis that follows, we consider three general classes of
technology that are likely to be employed by attackers with differing technology that are likely to be employed by attackers with differing
resources available to them. Not surprisingly, the cryptanalytic resources available to them. Not surprisingly, the cryptanalytic
skipping to change at page 44, line 39 skipping to change at page 44, 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 find a key to decrypt information using the RC4 algorithm with a 40-
40-bit key or the DES algorithm with its 56-bit key, but the results bit key or the DES algorithm with its 56-bit key, but the results are
are not peculiar to these ciphers. Although each algorithm has its not peculiar to these ciphers. Although each algorithm has its own
own particular characteristics, the effort required to find the keys particular characteristics, the effort required to find the keys of
of other ciphers is comparable. There may be some differences as the 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 49, line 7 skipping to change at page 49, 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.
Informative References Informative References
[AES] - "Specification of theAdvanced Encryption Standard (AES)", [AES] - "Specification of the Advanced Encryption Standard (AES)",
United States of America, Department of Commerce, National Institute United States of America, Department of Commerce, National Institute
of Standards and Technology, Federal Information Processing Standard of Standards and Technology, Federal Information Processing Standard
197, November 2001. 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.
skipping to change at page 53, line 12 skipping to change at page 53, line 12
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 Laboratories Motorola Laboratories
155 Beaver Street 155 Beaver Street
Milford, MA 01757 USA Milford, MA 01757 USA
Telephone: +1 508-851-8280 (w) Telephone: +1 508-786-7554 (w)
+1 508-634-2066 (h) +1 508-634-2066 (h)
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
EMail: steve@stevecrocker.com EMail: steve@stevecrocker.com
File Name and Expiration File Name and Expiration
This is file draft-eastlake-randomness2-04.txt. This is file draft-eastlake-randomness2-05.txt.
It expires February 2004. It expires June 2004.
 End of changes. 20 change blocks. 
28 lines changed or deleted 25 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/