| < draft-eastlake-randomness2-09.txt | draft-eastlake-randomness2-10.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 April 2005 October 2004 | Expires July 2005 January 2005 | |||
| Randomness Requirements for Security | Randomness Requirements for Security | |||
| ---------- ------------ --- -------- | ---------- ------------ --- -------- | |||
| <draft-eastlake-randomness2-09.txt> | <draft-eastlake-randomness2-10.txt> | |||
| Status of This Document | Status of This Document | |||
| By submitting this Internet-Draft, I certify that any applicable | By submitting this Internet-Draft, I certify that any applicable | |||
| patent or other IPR claims of which I am aware have been disclosed, | patent or other IPR claims of which I am aware have been disclosed, | |||
| or will be disclosed, and any of which I become aware will be | or will be disclosed, and any of which I become aware will be | |||
| disclosed, in accordance with RFC 3668. | disclosed, in accordance with RFC 3668. | |||
| 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. | |||
| skipping to change at page 1, line 38 ¶ | skipping to change at page 1, line 38 ¶ | |||
| 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 a "work in progress." | material or to cite them other than a "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/1id-abstracts.html | http://www.ietf.org/1id-abstracts.html | |||
| 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 | |||
| Copyright (C) The Internet Society 2004. All Rights Reserved. | Copyright (C) The Internet Society 2005. All Rights Reserved. | |||
| Abstract | Abstract | |||
| Security systems are built on strong cryptographic algorithms that | Security systems are built on strong cryptographic algorithms that | |||
| foil pattern analysis attempts. However, the security of these | foil pattern analysis attempts. However, the security of these | |||
| systems is dependent on generating secret quantities for passwords, | systems is dependent on generating secret quantities for passwords, | |||
| cryptographic keys, and similar quantities. The use of pseudo-random | cryptographic keys, and similar quantities. The use of pseudo-random | |||
| processes to generate secret quantities can result in pseudo- | processes to generate secret quantities can result in pseudo- | |||
| security. The sophisticated attacker of these security systems may | security. The sophisticated attacker of these security systems may | |||
| find it easier to reproduce the environment that produced the secret | find it easier to reproduce the environment that produced the secret | |||
| quantities, searching the resulting small set of possibilities, than | quantities, searching the resulting small set of possibilities, than | |||
| to locate the quantities in the whole of the potential number space. | to locate the quantities in the whole of the potential 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 poor entropy sources or traditional pseudo-random | |||
| techniques for choosing such quantities. It recommends the use of | number generation techniques for generating such quantities. It | |||
| truly random hardware techniques and shows that the existing hardware | recommends the use of truly random hardware techniques and shows that | |||
| on many systems can be used for this purpose. It provides suggestions | the existing hardware on many systems can be used for this purpose. | |||
| to ameliorate the problem when a hardware solution is not available. | It provides suggestions to ameliorate the problem when a hardware | |||
| And it gives examples of how large such quantities need to be for | solution is not available. And it gives examples of how large such | |||
| some applications. | quantities need to be for some applications. | |||
| Acknowledgements | Acknowledgements | |||
| Special thanks to Paul Hoffman and John Kelsey for their extensive | Special thanks to Paul Hoffman and John Kelsey for their extensive | |||
| comments and to Peter Gutmann, who has permitted the incorporation of | comments and to Peter Gutmann, who has permitted the incorporation of | |||
| material from his paper "Software Generation of Practically Strong | material from his paper "Software Generation of Practically Strong | |||
| Random Numbers". | Random Numbers". | |||
| The following other persons (in alphabetic order) have also | The following other persons (in alphabetic order) have also | |||
| contributed substantially to this document: | contributed substantially to this document: | |||
| Daniel Brown, Don Davis, Peter Gutmann, Tony Hansen, Sandy | Steve Bellovin, Daniel Brown, Don Davis, Peter Gutmann, Tony | |||
| Harris, Paul Hoffman, Scott Hollenback, Russ Housley, Christian | Hansen, Sandy Harris, Paul Hoffman, Scott Hollenback, Russ | |||
| Huitema, John Kelsey, and Damir Rajnovic. | Housley, Christian Huitema, John Kelsey, Mats Naslund, and Damir | |||
| Rajnovic. | ||||
| The following persons (in alphabetic order) contributed to RFC 1750, | The following persons (in alphabetic order) contributed to RFC 1750, | |||
| the predecessor of this document: | the predecessor 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 | |||
| Abstract...................................................1 | Abstract...................................................1 | |||
| Acknowledgements...........................................2 | Acknowledgements...........................................2 | |||
| Table of Contents..........................................3 | Table of Contents..........................................3 | |||
| 1. Introduction............................................5 | 1. Introduction and Overview...............................5 | |||
| 2. General Requirements....................................6 | 2. General Requirements....................................6 | |||
| 3. Traditional Pseudo-Random Sequences.....................9 | 3. Entropy Sources.........................................9 | |||
| 3.1 Volume Required........................................9 | ||||
| 3.2 Existing Hardware Can Be Used For Randomness..........10 | ||||
| 3.2.1 Using Existing Sound/Video Input....................10 | ||||
| 3.2.2 Using Existing Disk Drives..........................10 | ||||
| 3.3 Ring Oscillator Sources...............................11 | ||||
| 3.4 Problems with Clocks and Serial Numbers...............12 | ||||
| 3.5 Timing and Value of External Events...................13 | ||||
| 3.6 Non-Hardware Sources of Randomness....................14 | ||||
| 4. Unpredictability.......................................11 | 4. De-skewing.............................................15 | |||
| 4.1 Problems with Clocks and Serial Numbers...............11 | 4.1 Using Stream Parity to De-Skew........................15 | |||
| 4.2 Timing and Value of External Events...................12 | 4.2 Using Transition Mappings to De-Skew..................16 | |||
| 4.3 The Fallacy of Complex Manipulation...................12 | 4.3 Using FFT to De-Skew..................................17 | |||
| 4.4 The Fallacy of Selection from a Large Database........13 | 4.4 Using Compression to De-Skew..........................18 | |||
| 5. Hardware for Randomness................................15 | 5. Mixing.................................................19 | |||
| 5.1 Volume Required.......................................15 | 5.1 A Trivial Mixing Function.............................19 | |||
| 5.2 Sensitivity to Skew...................................15 | 5.2 Stronger Mixing Functions.............................20 | |||
| 5.2.1 Using Stream Parity to De-Skew......................16 | 5.3 Using S-Boxes for Mixing..............................22 | |||
| 5.2.2 Using Transition Mappings to De-Skew................17 | 5.4 Diffie-Hellman as a Mixing Function...................22 | |||
| 5.2.3 Using FFT to De-Skew................................18 | 5.5 Using a Mixing Function to Stretch Random Bits........23 | |||
| 5.2.4 Using Compression to De-Skew........................18 | 5.6 Other Factors in Choosing a Mixing Function...........23 | |||
| 5.3 Existing Hardware Can Be Used For Randomness..........19 | ||||
| 5.3.1 Using Existing Sound/Video Input....................19 | ||||
| 5.3.2 Using Existing Disk Drives..........................19 | ||||
| 5.4 Ring Oscillator Sources...............................20 | ||||
| 6. Recommended Software Strategy..........................22 | 6. Pseudo Random Number Generators........................25 | |||
| 6.1 Mixing Functions......................................22 | 6.1 Some Bad Ideas........................................25 | |||
| 6.1.1 A Trivial Mixing Function...........................22 | 6.1.1 The Fallacy of Complex Manipulation.................25 | |||
| 6.1.2 Stronger Mixing Functions...........................23 | 6.1.2 The Fallacy of Selection from a Large Database......26 | |||
| 6.1.3 Using S-Boxes for Mixing............................25 | 6.1.3. Traditional Pseudo-Random Sequences................26 | |||
| 6.1.4 Diffie-Hellman as a Mixing Function.................25 | 6.2 Cryptographically Strong Sequences....................28 | |||
| 6.1.5 Using a Mixing Function to Stretch Random Bits......25 | 6.2.1 OFB and CTR Sequences...............................29 | |||
| 6.1.6 Other Factors in Choosing a Mixing Function.........26 | 6.2.2 The Blum Blum Shub Sequence Generator...............30 | |||
| 6.2 Non-Hardware Sources of Randomness....................27 | 6.3 Entropy Pool Techniques...............................31 | |||
| 6.3 Cryptographically Strong Sequences....................28 | ||||
| 6.3.1 OFB and CTR Sequences...............................28 | ||||
| 6.3.2 The Blum Blum Shub Sequence Generator...............29 | ||||
| 6.3.3 Entropy Pool Techniques.............................30 | ||||
| 7. Key Generation Examples and Standards..................32 | 7. Randomness Generation Examples and Standards...........33 | |||
| 7.1 US DoD Recommendations for Password Generation........32 | 7.1 Complete Randomness Generators........................33 | |||
| 7.2 X9.17 Key Generation..................................32 | 7.1.1 US DoD Recommendations for Password Generation......33 | |||
| 7.3 DSS Pseudo-Random Number Generation...................33 | 7.1.2 The /dev/random Device..............................34 | |||
| 7.4 X9.82 Pseudo-Random Number Generation.................34 | 7.1.3 Windows CryptGenRandom..............................35 | |||
| 7.5 The /dev/random Device................................34 | 7.2 Generators Assuming a Source of Entropy...............36 | |||
| 7.6 Windows CryptGenRandom................................36 | 7.2.1 X9.82 Pseudo-Random Number Generation...............36 | |||
| 7,2.1.1 Notation..........................................36 | ||||
| 7.1.2.2 Initializing the Generator........................37 | ||||
| 7.1.2.5 Generating Random Bits............................37 | ||||
| 7.2.2 X9.17 Key Generation................................37 | ||||
| 7.2.3 DSS Pseudo-Random Number Generation.................38 | ||||
| 8. Examples of Randomness Required........................37 | 8. Examples of Randomness Required........................40 | |||
| 8.1 Password Generation..................................37 | 8.1 Password Generation..................................40 | |||
| 8.2 A Very High Security Cryptographic Key................38 | 8.2 A Very High Security Cryptographic Key................41 | |||
| 8.2.1 Effort per Key Trial................................38 | 8.2.1 Effort per Key Trial................................41 | |||
| 8.2.2 Meet in the Middle Attacks..........................39 | 8.2.2 Meet in the Middle Attacks..........................42 | |||
| 8.2.3 Other Considerations................................40 | 8.2.3 Other Considerations................................43 | |||
| 9. Conclusion.............................................41 | 9. Conclusion.............................................44 | |||
| 10. Security Considerations...............................42 | 10. Security Considerations...............................45 | |||
| 11. Copyright and Disclaimer..............................42 | 11. Copyright and Disclaimer..............................45 | |||
| 12. Appendix A: Changes from RFC 1750.....................43 | 12. Appendix A: Changes from RFC 1750.....................46 | |||
| 14. Informative References................................44 | 13. Informative References................................47 | |||
| Author's Addresses........................................48 | Author's Addresses........................................52 | |||
| File Name and Expiration..................................48 | File Name and Expiration..................................52 | |||
| 1. Introduction | 1. Introduction and Overview | |||
| 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 SSH, 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 [SSH, IPSEC, | maturing and becoming a part of the network landscape [SSH, IPSEC, | |||
| MAIL*, TLS, DNSSEC]. By comparison, when the previous version of this | MAIL*, TLS, DNSSEC]. By comparison, when the previous version of this | |||
| document [RFC 1750] was issued in 1994, about the only Internet | document [RFC 1750] was issued in 1994, about the only Internet | |||
| cryptographic security specification in the IETF was the Privacy | cryptographic security specification in the IETF was the Privacy | |||
| skipping to change at page 6, line 22 ¶ | skipping to change at page 6, line 22 ¶ | |||
| strings or phrases composed on ordinary words. But this only affects | strings or phrases composed on ordinary words. But this only affects | |||
| the format of the password information, not the requirement that the | the format of the password information, 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 based | including confidentiality and authentication. Such services are based | |||
| on quantities, traditionally called "keys", that are unknown to and | on quantities, traditionally called "keys", that are unknown to and | |||
| unguessable by an adversary. | unguessable by an adversary. | |||
| Generally speaking, the above two examples also illustrate two | There are even TCP/IP protocol uses for randomness in picking initial | |||
| different types of random quantities that may be wanted. In the case | sequence numbers [RFC 1948]. | |||
| of human usable passwords, the only important characteristic is that | ||||
| it be unguessable; it is not important that they may be composed of | Generally speaking, the above examples also illustrate two different | |||
| ASCII characters, for example, so the top bit of every byte is zero. | types of random quantities that may be wanted. In the case of human | |||
| On the other hand, for fixed length keys and the like, you normally | usable passwords, the only important characteristic is that it be | |||
| unguessable; it is not important that they may be composed of ASCII | ||||
| characters, for example, so the top bit of every byte is zero. On the | ||||
| other hand, for fixed length keys and the like, you normally want | ||||
| quantities that are indistinguishable from truly random, that is, all | quantities that are indistinguishable from truly random, that is, all | |||
| bits will pass statistical randomness tests. | bits will pass statistical randomness tests. | |||
| 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 or an algorithm like the US Advanced Encryption Standard | time pads or an algorithm like the US Advanced Encryption Standard | |||
| [AES], the parties who wish to communicate confidentially and/or with | [AES], the parties who wish to communicate confidentially and/or with | |||
| authentication must all know the same secret key. In other cases, | authentication must all know the same secret key. In other cases, | |||
| using what are called asymmetric or "public key" cryptographic | using what are called asymmetric or "public key" cryptographic | |||
| techniques, keys come in pairs. One key of the pair is private and | techniques, keys come in pairs. One key of the pair is private and | |||
| must be kept secret by one party, the other is public and can be | must be kept secret by one party, the other is public and can be | |||
| skipping to change at page 6, line 52 ¶ | skipping to change at page 7, line 4 ¶ | |||
| 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, | |||
| random quantities are required only when a new key pair is generated; | random quantities are required only when a new key pair is generated; | |||
| thereafter any number of messages can be signed without a further | thereafter any number of messages can be signed without a further | |||
| need for randomness. The public key Digital Signature Algorithm | need for randomness. The public key Digital Signature Algorithm | |||
| devised by the US National Institute of Standards and Technology | devised by the US National Institute of Standards and Technology | |||
| (NIST) requires good random numbers for each signature [DSS]. And | (NIST) requires good random numbers for each signature [DSS]. And | |||
| encrypting with a one time pad, in principle the strongest possible | encrypting with a one time pad, in principle the strongest possible | |||
| encryption technique, requires a volume of randomness equal to all | encryption technique, requires a volume of randomness equal to all | |||
| the messages to be processed. [SCHNEIER, FERGUSON, KAUFMAN] | the messages to be processed. [SCHNEIER, FERGUSON, KAUFMAN] | |||
| 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 key | "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 | 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 an 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-information = \ - p * log ( p ) | Bits-of-information = \ - p * log ( p ) | |||
| / i 2 i | / i 2 i | |||
| / | / | |||
| ----- | ----- | |||
| skipping to change at page 7, line 46 ¶ | skipping to change at page 7, line 48 ¶ | |||
| number generator that is seeded with an 8 bit seed, then an adversary | number generator that is seeded with an 8 bit seed, then an adversary | |||
| needs to search through only 256 keys (by running the pseudo-random | needs to search through only 256 keys (by running the pseudo-random | |||
| number generator with every possible seed), not the 2^128 keys that | number generator with every possible seed), not the 2^128 keys that | |||
| may at first appear to be the case. Only 8 bits of "information" are | may at first appear to be the case. Only 8 bits of "information" are | |||
| in these 128 bit keys. | in these 128 bit keys. | |||
| While the above analysis is correct on average, it can be misleading | While the above analysis is correct on average, it can be misleading | |||
| in some cases for cryptographic analysis where what is really | in some cases for cryptographic analysis where what is really | |||
| important is the work factor for an adversary. For example, assume | important is the work factor for an adversary. For example, assume | |||
| that there was a pseudo-random number generator generating 128 bit | that there was a pseudo-random number generator generating 128 bit | |||
| keys, as in the previous paragraph, but that it generated 0 half of | keys, as in the previous paragraph, but that it generated 0 half of | |||
| the time and a random selection from the remaining 2**128 - 1 values | the time and a random selection from the remaining 2**128 - 1 values | |||
| the rest of the time. The Shannon equation above says that there are | the rest of the time. The Shannon equation above says that there are | |||
| 64 bits of information in one of these key values but an adversary, | 64 bits of information in one of these key values but an adversary, | |||
| by simply trying the values 0, can break the security of half of the | by simply trying the values 0, can break the security of half of the | |||
| uses, albeit a random half. Thus for cryptographic purposes, it is | uses, albeit a random half. Thus for cryptographic purposes, it is | |||
| also useful to look at other measures, such as min-entropy, defined | also useful to look at other measures, such as min-entropy, defined | |||
| as | as | |||
| Min-entropy = - log ( maximum ( p ) ) | Min-entropy = - log ( maximum ( p ) ) | |||
| i | i | |||
| where i is as above. Using this equation, we get 1 bit of min- | where i is as above. Using this equation, we get 1 bit of min- | |||
| entropy for our new hypothetical distribution as opposed to 64 bits | entropy for our new hypothetical distribution as opposed to 64 bits | |||
| of classical Shannon entropy. | of classical Shannon entropy. | |||
| A continuous spectrum of entropies, sometimes called Renyi entropy, | A continuous spectrum of entropies, sometimes called Renyi entropy, | |||
| have been defined, specified by a parameter r. When r = 1, it is | have been defined, specified by a parameter r. When r = 1, it is | |||
| Shannon entropy, and with r = infinity, it is min-entropy. When r = | Shannon entropy, and with r = infinity, it is min-entropy. When r = | |||
| 0, it is just log (n) where n is the number of non-zero | 0, it is just log (n) where n is the number of non-zero | |||
| probabilities. Renyi entropy is a non-increasing function of r, so | probabilities. Renyi entropy is a non-increasing function of r, so | |||
| min-entropy is always the most conservative measure of entropy and | min-entropy is always the most conservative measure of entropy and | |||
| usually the best to use for cryptographic evaluation. [LUBY] | usually the best to use for cryptographic evaluation. [LUBY] | |||
| 3. Traditional Pseudo-Random Sequences | Statistically tested randomness in the traditional sense is NOT the | |||
| same as the unpredictability required for security use. | ||||
| This section talks about traditional sources of deterministic of | For example, use of a widely available constant sequence, such as | |||
| "pseudo-random" numbers. These typically start with a "seed" quantity | that from the CRC tables, is very weak against an adversary. Once | |||
| and use numeric or logical operations to produce a sequence of | they learn of or guess it, they can easily break all security, future | |||
| values. Note that none of the techniques discussed in this section is | and past, based on the sequence. [CRC] As another example, using AES | |||
| suitable for cryptographic use. They are presented for general | to encrypt successive integers such as 1, 2, 3 ... will also produce | |||
| information. | output that has excellent statistical randomness properties but is | |||
| also predictable. On the other hand, taking successive rolls of a | ||||
| six-sided die and encoding the resulting values in ASCII would | ||||
| produce statistically poor output with a substantial unpredictable | ||||
| component. So you should keep in mind that passing or failing | ||||
| statistical tests doesn't tell you that something is unpredictable | ||||
| or predictable. | ||||
| [KNUTH] has a classic exposition on pseudo-random numbers. | 3. Entropy Sources | |||
| Applications he mentions are simulation of natural phenomena, | ||||
| sampling, numerical analysis, testing computer programs, decision | ||||
| making, and games. None of these have the same characteristics as the | ||||
| sort of security uses we are talking about. Only in the last two | ||||
| could there be an adversary trying to find the random quantity. | ||||
| However, in these cases, the adversary normally has only a single | ||||
| chance to use a guessed value. In guessing passwords or attempting to | ||||
| break an encryption scheme, the adversary normally has many, perhaps | ||||
| unlimited, chances at guessing the correct value. They can store the | ||||
| message they are trying to break and repeatedly attack it. They are | ||||
| also be assumed to be aided by a computer. | ||||
| For testing the "randomness" of numbers, Knuth suggests a variety of | Entropy sources tend to be very implementation dependent. Once one | |||
| measures including statistical and spectral. These tests check things | has gathered sufficient entropy it can be used as the seed to produce | |||
| like autocorrelation between different parts of a "random" sequence | the required amount of cryptographically strong pseudo-randomness, as | |||
| or distribution of its values. But they could be met by a constant | described in Sections 6 and 7, after being de-skewed and/or mixed if | |||
| stored random sequence, such as the "random" sequence printed in the | necessary as described in Sections 4 and 5. | |||
| CRC Standard Mathematical Tables [CRC]. Despite meeting all the tests | ||||
| suggested by Knuth, that sequence is unsuitable for cryptographic use | ||||
| as adversaries must be assumed to have copies of all common published | ||||
| "random" sequences and will able to spot the source and predict | ||||
| future values. | ||||
| A typical pseudo-random number generation technique, known as a | Is there any hope for true strong portable randomness in the future? | |||
| linear congruence pseudo-random number generator, is modular | There might be. All that's needed is a physical source of | |||
| arithmetic where the value numbered N+1 is calculated from the value | unpredictable numbers. | |||
| numbered N by | ||||
| V = ( V * a + b )(Mod c) | A thermal noise (sometimes called Johnson noise in integrated | |||
| N+1 N | circuits) or radioactive decay source and a fast, free-running | |||
| oscillator would do the trick directly [GIFFORD]. This is a trivial | ||||
| amount of hardware, and could easily be included as a standard part | ||||
| of a computer system's architecture. Most audio (or video) input | ||||
| devices are useable [TURBID]. Furthermore, any system with a | ||||
| spinning disk or ring oscillator and a stable (crystal) time source | ||||
| or the like has an adequate source of randomness ([DAVIS] and Section | ||||
| 3.3). All that's needed is the common perception among computer | ||||
| vendors that this small additional hardware and the software to | ||||
| access it is necessary and useful. | ||||
| The above technique has a strong relationship to linear shift | ANSI X9 is currently developing a standard which includes a part | |||
| register pseudo-random number generators, which are well understood | devoted to entropy sources. See [X9.82 - Part 2]. | |||
| cryptographically [SHIFT*]. In such generators bits are introduced at | ||||
| one end of a shift register as the Exclusive Or (binary sum without | ||||
| carry) of bits from selected fixed taps into the register. For | ||||
| example: | ||||
| +----+ +----+ +----+ +----+ | 3.1 Volume Required | |||
| | B | <-- | B | <-- | B | <-- . . . . . . <-- | B | <-+ | ||||
| | 0 | | 1 | | 2 | | n | | | ||||
| +----+ +----+ +----+ +----+ | | ||||
| | | | | | ||||
| | | V +-----+ | ||||
| | V +----------------> | | | ||||
| V +-----------------------------> | XOR | | ||||
| +---------------------------------------------------> | | | ||||
| +-----+ | ||||
| V = ( ( V * 2 ) + B .xor. B ... )(Mod 2^n) | How much unpredictability is needed? Is it possible to quantify the | |||
| N+1 N 0 2 | requirement in, say, number of random bits per second? | |||
| The goodness of traditional pseudo-random number generator algorithms | The answer is not very much is needed. For AES, the key can be 128 | |||
| is measured by statistical tests on such sequences. Carefully chosen | bits and, as we show in an example in Section 8, even the highest | |||
| values a, b, c, and initial V or the placement of shift register tap | security system is unlikely to require strong keying material of much | |||
| in the above simple processes can produce excellent statistics. | over 200 bits. If a series of keys are needed, they can be generated | |||
| from a strong random seed (starting value) using a cryptographically | ||||
| strong sequence as explained in Section 6.2. A few hundred random | ||||
| bits generated at start up or once a day would be enough using such | ||||
| techniques. Even if the random bits are generated as slowly as one | ||||
| per second and it is not possible to overlap the generation process, | ||||
| it should be tolerable in most high security applications to wait 200 | ||||
| seconds occasionally. | ||||
| These sequences may be adequate in simulations (Monte Carlo | These numbers are trivial to achieve. It could be done by a person | |||
| experiments) as long as the sequence is orthogonal to the structure | repeatedly tossing a coin. Almost any hardware based process is | |||
| of the space being explored. Even there, subtle patterns may cause | likely to be much faster. | |||
| problems. However, such sequences are clearly bad for use in security | ||||
| applications. They are fully predictable if the initial state is | ||||
| known. Depending on the form of the pseudo-random number generator, | ||||
| the sequence may be determinable from observation of a short portion | ||||
| of the sequence [SCHNEIER, STERN]. For example, with the generators | ||||
| above, one can determine V(n+1) given knowledge of V(n). In fact, it | ||||
| has been shown that with these techniques, even if only one bit of | ||||
| the pseudo-random values are released, the seed can be determined | ||||
| from short sequences. | ||||
| Not only have linear congruent generators been broken, but techniques | 3.2 Existing Hardware Can Be Used For Randomness | |||
| are now known for breaking all polynomial congruent generators. | ||||
| [KRAWCZYK] | ||||
| 4. Unpredictability | As described below, many computers come with hardware that can, with | |||
| care, be used to generate truly random quantities. | ||||
| Statistically tested randomness in the traditional sense described in | 3.2.1 Using Existing Sound/Video Input | |||
| section 3 is NOT the same as the unpredictability required for | ||||
| security use. | ||||
| For example, use of a widely available constant sequence, such as | Many computers are built with inputs that digitize some real world | |||
| that from the CRC tables, is very weak against an adversary. Once | analog source, such as sound from a microphone or video input from a | |||
| they learn of or guess it, they can easily break all security, future | camera. Under appropriate circumstances, such input can provide | |||
| and past, based on the sequence. [CRC] Yet the statistical properties | reasonably high quality random bits. The "input" from a sound | |||
| of these tables are good. So you should keep in mind that passing | digitizer with no source plugged in or a camera with the lens cap on, | |||
| statistical tests doesn't tell you that something is unpredictable. | if the system has enough gain to detect anything, is essentially | |||
| thermal noise. This method is extremely hardware and implementation | ||||
| dependent. | ||||
| The following sections describe the limitations of some randomness | For example, on some UNIX based systems, one can read from the | |||
| generation techniques and sources. Much better sources are described | /dev/audio device with nothing plugged into the microphone jack or | |||
| in Section 5. | the microphone receiving only low level background noise. Such data | |||
| is essentially random noise although it should not be trusted without | ||||
| some checking in case of hardware failure. It will, in any case, | ||||
| need to be de-skewed as described elsewhere. | ||||
| 4.1 Problems with Clocks and Serial Numbers | Combining this with compression to de-skew (see Section 4) one can, | |||
| in UNIXese, generate a huge amount of medium quality random data by | ||||
| doing | ||||
| cat /dev/audio | compress - >random-bits-file | ||||
| A detailed examination of this type of randomness source appears in | ||||
| [TURBID]. | ||||
| 3.2.2 Using Existing Disk Drives | ||||
| Disk drives have small random fluctuations in their rotational speed | ||||
| due to chaotic air turbulence [DAVIS, Jakobsson]. By adding low | ||||
| level disk seek time instrumentation to a system, a series of | ||||
| measurements can be obtained that include this randomness. Such data | ||||
| is usually highly correlated so that significant processing is | ||||
| needed, such as described in 5.2 below. Nevertheless experimentation | ||||
| a decade ago showed that, with such processing, even slow disk drives | ||||
| on the slower computers of that day could easily produce 100 bits a | ||||
| minute or more of excellent random data. | ||||
| Every increase in processor speed, which increases the resolution | ||||
| with which disk motion can be timed, or increase in the rate of disk | ||||
| seeks, increases the rate of random bit generation possible with this | ||||
| technique. At the time of this paper and using modern hardware, a | ||||
| more typical rate of random bit production would be in excess of | ||||
| 10,000 bits a second. This technique is used in many operating system | ||||
| library random number generators. | ||||
| Note: the inclusion of cache memories in disk controllers has little | ||||
| effect on this technique if very short seek times, which represent | ||||
| cache hits, are simply ignored. | ||||
| 3.3 Ring Oscillator Sources | ||||
| If an integrated circuit is being designed or field programmed, an | ||||
| odd number of gates can be connected in series to produce a free- | ||||
| running ring oscillator. By sampling a point in the ring at a fixed | ||||
| frequency, say one determined by a stable crystal oscillator, some | ||||
| amount of entropy can be extracted due to variations in the free- | ||||
| running oscillator timing. It is possible to increase the rate of | ||||
| entropy by xor'ing sampled values from a few ring oscillators with | ||||
| relatively prime lengths. It is sometimes recommended that an odd | ||||
| number of rings be used so that, even if the rings somehow become | ||||
| synchronously locked to each other, there will still be sampled bit | ||||
| transitions. Another possibility source to sample is the output of a | ||||
| noisy diode. | ||||
| Sampled bits from such sources will have to be heavily de-skewed, as | ||||
| disk rotation timings must be (see Section 4). An engineering study | ||||
| would be needed to determine the amount of entropy being produced | ||||
| depending on the particular design. In any case, these can be good | ||||
| sources whose cost is a trivial amount of hardware by modern | ||||
| standards. | ||||
| As an example, IEEE 802.11i suggests that the circuit below be | ||||
| considered, with due attention in the design to isolation of the | ||||
| rings from each other and from clocked circuits to avoid undesired | ||||
| synchronization, etc., and extensive post processing. [IEEE 802.11i] | ||||
| |\ |\ |\ | ||||
| +-->| >0-->| >0-- 19 total --| >0--+-------+ | ||||
| | |/ |/ |/ | | | ||||
| | | | | ||||
| +----------------------------------+ V | ||||
| +-----+ | ||||
| |\ |\ |\ | | output | ||||
| +-->| >0-->| >0-- 23 total --| >0--+--->| XOR |------> | ||||
| | |/ |/ |/ | | | | ||||
| | | +-----+ | ||||
| +----------------------------------+ ^ ^ | ||||
| | | | ||||
| |\ |\ |\ | | | ||||
| +-->| >0-->| >0-- 29 total --| >0--+------+ | | ||||
| | |/ |/ |/ | | | ||||
| | | | | ||||
| +----------------------------------+ | | ||||
| | | ||||
| other randomness if available--------------+ | ||||
| 3.4 Problems with Clocks and Serial Numbers | ||||
| Computer clocks, or similar operating system or hardware values, | Computer clocks, or similar operating system or hardware values, | |||
| provide significantly fewer real bits of unpredictability than might | provide significantly fewer real bits of unpredictability than might | |||
| appear from their specifications. | appear from their specifications. | |||
| Tests have been done on clocks on numerous systems and it was found | Tests have been done on clocks on numerous systems and it was found | |||
| that their behavior can vary widely and in unexpected ways. One | that their behavior can vary widely and in unexpected ways. One | |||
| version of an operating system running on one set of hardware may | version of an operating system running on one set of hardware may | |||
| actually provide, say, microsecond resolution in a clock while a | actually provide, say, microsecond resolution in a clock while a | |||
| different configuration of the "same" system may always provide the | different configuration of the "same" system may always provide the | |||
| skipping to change at page 11, line 45 ¶ | skipping to change at page 12, line 47 ¶ | |||
| identical values even if enough time has passed that the value | identical values even if enough time has passed that the value | |||
| "should" change based on the nominal clock resolution. There are also | "should" change based on the nominal clock resolution. There are also | |||
| cases where frequently reading a clock can produce artificial | cases where frequently reading a clock can produce artificial | |||
| sequential values because of extra code that checks for the clock | sequential values because of extra code that checks for the clock | |||
| being unchanged between two reads and increases it by one! Designing | being unchanged between two reads and increases it by one! Designing | |||
| portable application code to generate unpredictable numbers based on | portable application code to generate unpredictable numbers based on | |||
| such system clocks is particularly challenging because the system | such system clocks is particularly challenging because the system | |||
| designer does not always know the properties of the system clocks | designer does not always know the properties of the system clocks | |||
| that the code will execute on. | that the code will execute on. | |||
| Use of hardware serial numbers such as an Ethernet addresses may also | Use of hardware serial numbers such as an Ethernet MAC addresses may | |||
| provide fewer bits of uniqueness than one would guess. Such | also provide fewer bits of uniqueness than one would guess. Such | |||
| quantities are usually heavily structured and subfields may have only | quantities are usually heavily structured and subfields may have only | |||
| a limited range of possible values or values easily guessable based | a limited range of possible values or values easily guessable based | |||
| on approximate date of manufacture or other data. For example, it is | on approximate date of manufacture or other data. For example, it is | |||
| likely that a company that manufactures both computers and Ethernet | likely that a company that manufactures both computers and Ethernet | |||
| adapters will, at least internally, use its own adapters, which | adapters will, at least internally, use its own adapters, which | |||
| significantly limits the range of built-in addresses. | significantly limits the range of built-in addresses. | |||
| Problems such as those described above related to clocks and serial | Problems such as those described above related to clocks and serial | |||
| numbers make code to produce unpredictable quantities difficult if | numbers make code to produce unpredictable quantities difficult if | |||
| the code is to be ported across a variety of computer platforms and | the code is to be ported across a variety of computer platforms and | |||
| systems. | systems. | |||
| 4.2 Timing and Value of External Events | 3.5 Timing and Value of External Events | |||
| It is possible to measure the timing and content of mouse movement, | It is possible to measure the timing and content of mouse movement, | |||
| key strokes, and similar user events. This is a reasonable source of | key strokes, and similar user events. This is a reasonable source of | |||
| unguessable data with some qualifications. On some machines, inputs | unguessable data with some qualifications. On some machines, inputs | |||
| such as key strokes are buffered. Even though the user's inter- | such as key strokes are buffered. Even though the user's inter- | |||
| keystroke timing may have sufficient variation and unpredictability, | keystroke timing may have sufficient variation and unpredictability, | |||
| there might not be an easy way to access that variation. Another | there might not be an easy way to access that variation. Another | |||
| problem is that no standard method exists to sample timing details. | problem is that no standard method exists to sample timing details. | |||
| This makes it hard to build standard software intended for | This makes it hard to build standard software intended for | |||
| distribution to a large range of machines based on this technique. | distribution to a large range of machines based on this technique. | |||
| skipping to change at page 12, line 46 ¶ | skipping to change at page 14, line 5 ¶ | |||
| how much such data is subject to adversarial manipulation and to how | how much such data is subject to adversarial manipulation and to how | |||
| much entropy it can actually provide. | much entropy it can actually provide. | |||
| The above techniques are quite powerful against any attackers having | The above techniques are quite powerful against any attackers having | |||
| no access to the quantities being measured. For example, they would | no access to the quantities being measured. For example, they would | |||
| be powerful against offline attackers who had no access to your | be powerful against offline attackers who had no access to your | |||
| environment and were trying to crack your random seed after the fact. | environment and were trying to crack your random seed after the fact. | |||
| In all cases, the more accurately you can measure the timing or value | In all cases, the more accurately you can measure the timing or value | |||
| of an external sensor, the more rapidly you can generate bits. | of an external sensor, the more rapidly you can generate bits. | |||
| 4.3 The Fallacy of Complex Manipulation | 3.6 Non-Hardware Sources of Randomness | |||
| One strategy which may give a misleading appearance of | ||||
| unpredictability is to take a very complex algorithm (or an excellent | ||||
| traditional pseudo-random number generator with good statistical | ||||
| properties) and calculate a cryptographic key by starting with | ||||
| limited data such as the computer system clock value as the seed. An | ||||
| adversary who knew roughly when the generator was started would have | ||||
| a relatively small number of seed values to test as they would know | ||||
| likely values of the system clock. Large numbers of pseudo-random | ||||
| bits could be generated but the search space an adversary would need | ||||
| to check could be quite small. | ||||
| Thus very strong and/or complex manipulation of data will not help if | ||||
| the adversary can learn what the manipulation is and there is not | ||||
| enough unpredictability in the starting seed value. They can usually | ||||
| use the limited number of results stemming from a limited number of | ||||
| seed values to defeat security. | ||||
| Another serious strategy error is to assume that a very complex | ||||
| pseudo-random number generation algorithm will produce strong random | ||||
| numbers when there has been no theory behind or analysis of the | ||||
| algorithm. There is a excellent example of this fallacy right near | ||||
| the beginning of Chapter 3 in [KNUTH] where the author describes a | ||||
| complex algorithm. It was intended that the machine language program | ||||
| corresponding to the algorithm would be so complicated that a person | ||||
| trying to read the code without comments wouldn't know what the | ||||
| program was doing. Unfortunately, actual use of this algorithm showed | ||||
| that it almost immediately converged to a single repeated value in | ||||
| one case and a small cycle of values in another case. | ||||
| Not only does complex manipulation not help you if you have a limited | ||||
| range of seeds but blindly chosen complex manipulation can destroy | ||||
| the randomness in a good seed! | ||||
| 4.4 The Fallacy of Selection from a Large Database | ||||
| Another strategy that can give a misleading appearance of | ||||
| unpredictability is selection of a quantity randomly from a database | ||||
| and assume that its strength is related to the total number of bits | ||||
| in the database. For example, typical USENET servers process many | ||||
| megabytes of information per day [USENET]. Assume a random quantity | ||||
| was 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 | ||||
| unguessability. Even after allowing that much of the data is human | ||||
| language and probably has no more than 2 or 3 bits of information per | ||||
| byte, it doesn't yield 32*2 = 64 bits of unguessability. For an | ||||
| adversary with access to the same usenet database the unguessability | ||||
| rests only on the starting point of the selection. That is perhaps a | ||||
| little over a couple of dozen bits of unguessability. | ||||
| The same argument applies to selecting sequences from the data on a | ||||
| publicly available CD/DVD recording or any other large public | ||||
| database. If the adversary has access to the same database, this | ||||
| "selection from a large volume of data" step buys little. However, | ||||
| if a selection 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. | ||||
| 5. Hardware for Randomness | ||||
| Is there any hope for true strong portable randomness in the future? | ||||
| There might be. All that's needed is a physical source of | ||||
| unpredictable numbers. | ||||
| 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 | ||||
| amount of hardware, and could easily be included as a standard part | ||||
| of a computer system's architecture. Most audio (or video) input | ||||
| devices are useable [TURBID]. Furthermore, any system with a | ||||
| spinning disk or ring oscillator and a stable (crystal) time source | ||||
| or the like has an adequate source of randomness ([DAVIS] and Section | ||||
| 5.4). All that's needed is the common perception among computer | ||||
| vendors that this small additional hardware and the software to | ||||
| access it is necessary and useful. | ||||
| 5.1 Volume Required | The best source of input entropy would be a hardware randomness such | |||
| as ring oscillators, disk drive timing, thermal noise, or radioactive | ||||
| decay. However, if that is not available, there are other | ||||
| possibilities. These include system clocks, system or input/output | ||||
| buffers, user/system/hardware/network serial numbers and/or addresses | ||||
| and timing, and user input. Unfortunately, each of these sources can | ||||
| produce very limited or predictable values under some circumstances. | ||||
| How much unpredictability is needed? Is it possible to quantify the | Some of the sources listed above would be quite strong on multi-user | |||
| requirement in, say, number of random bits per second? | systems where, in essence, each user of the system is a source of | |||
| randomness. However, on a small single user or embedded system, | ||||
| especially at start up, it might be possible for an adversary to | ||||
| assemble a similar configuration. This could give the adversary | ||||
| inputs to the mixing process that were sufficiently correlated to | ||||
| those used originally as to make exhaustive search practical. | ||||
| The answer is not very much is needed. For AES, the key can be 128 | The use of multiple random inputs with a strong mixing function is | |||
| bits and, as we show in an example in Section 8, even the highest | recommended and can overcome weakness in any particular input. The | |||
| security system is unlikely to require strong keying material of much | timing and content of requested "random" user keystrokes can yield | |||
| over 200 bits. If a series of keys are needed, they can be generated | hundreds of random bits but conservative assumptions need to be made. | |||
| from a strong random seed (starting value) using a cryptographically | For example, assuming at most a few bits of randomness if the inter- | |||
| strong sequence as explained in Section 6.3. A few hundred random | keystroke interval is unique in the sequence up to that point and a | |||
| bits generated at start up or once a day would be enough using such | similar assumption if the key hit is unique but assuming that no bits | |||
| techniques. Even if the random bits are generated as slowly as one | of randomness are present in the initial key value or if the timing | |||
| per second and it is not possible to overlap the generation process, | or key value duplicate previous values. The results of mixing these | |||
| it should be tolerable in most high security applications to wait 200 | timings and characters typed could be further combined with clock | |||
| seconds occasionally. | values and other inputs. | |||
| These numbers are trivial to achieve. It could be done by a person | This strategy may make practical portable code to produce good random | |||
| repeatedly tossing a coin. Almost any hardware based process is | numbers for security even if some of the inputs are very weak on some | |||
| likely to be much faster. | of the target systems. However, it may still fail against a high | |||
| grade attack on small, single user or embedded systems, especially if | ||||
| the adversary has ever been able to observe the generation process in | ||||
| the past. A hardware based random source is still preferable. | ||||
| 5.2 Sensitivity to Skew | 4. De-skewing | |||
| 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 | quantities gathered for the entropy to produce the random numbers? | |||
| uniform. All that is needed is a conservative estimate of how non- | The good news is the distribution need not be uniform. All that is | |||
| uniform it is to bound performance. Simple techniques to de-skew the | needed is a conservative estimate of how non-uniform it is to bound | |||
| bit stream are given below and stronger cryptographic techniques are | performance. Simple techniques to de-skew a bit stream are given | |||
| described in Section 6.1.2 below. | below and stronger cryptographic techniques are described in Section | |||
| 5.2 below. | ||||
| 5.2.1 Using Stream Parity to De-Skew | 4.1 Using Stream Parity to De-Skew | |||
| As a simple but not particularly practical example, consider taking a | As a simple but not particularly practical example, consider taking a | |||
| sufficiently long string of bits and map the string to "zero" or | sufficiently long string of bits and map the string to "zero" or | |||
| "one". The mapping will not yield a perfectly uniform distribution, | "one". The mapping will not yield a perfectly uniform distribution, | |||
| but it can be as close as desired. One mapping that serves the | but it can be as close as desired. One mapping that serves the | |||
| purpose is to take the parity of the string. This has the advantages | purpose is to take the parity of the string. This has the advantages | |||
| that it is robust across all degrees of skew up to the estimated | that it is robust across all degrees of skew up to the estimated | |||
| maximum skew and is absolutely trivial to implement in hardware. | maximum skew and is absolutely trivial to implement in hardware. | |||
| The following analysis gives the number of bits that must be sampled: | The following analysis gives the number of bits that must be sampled: | |||
| Suppose the ratio of ones to zeros is ( 0.5 + e ) to ( 0.5 - e ), | Suppose the ratio of ones to zeros is ( 0.5 + E ) to ( 0.5 - E ), | |||
| where e is between 0 and 0.5 and is a measure of the "eccentricity" | where E is between 0 and 0.5 and is a measure of the "eccentricity" | |||
| of the distribution. Consider the distribution of the parity function | of the distribution. Consider the distribution of the parity function | |||
| of N bit samples. The probabilities that the parity will be one or | of N bit samples. The probabilities that the parity will be one or | |||
| zero will be the sum of the odd or even terms in the binomial | zero will be the sum of the odd or even terms in the binomial | |||
| expansion of (p + q)^N, where p = 0.5 + e, the probability of a one, | expansion of (p + q)^N, where p = 0.5 + E, the probability of a one, | |||
| and q = 0.5 - e, the probability of a zero. | and q = 0.5 - E, the probability of a zero. | |||
| These sums can be computed easily as | These sums can be computed easily as | |||
| N N | N N | |||
| 1/2 * ( ( p + q ) + ( p - q ) ) | 1/2 * ( ( p + q ) + ( p - q ) ) | |||
| and | and | |||
| N N | N N | |||
| 1/2 * ( ( p + q ) - ( p - q ) ). | 1/2 * ( ( p + q ) - ( p - q ) ). | |||
| (Which one corresponds to the probability the parity will be 1 | (Which one corresponds to the probability the parity will be 1 | |||
| depends on whether N is odd or even.) | depends on whether N is odd or even.) | |||
| Since p + q = 1 and p - q = 2e, these expressions reduce to | Since p + q = 1 and p - q = 2e, these expressions reduce to | |||
| N | N | |||
| 1/2 * [1 + (2e) ] | 1/2 * [1 + (2E) ] | |||
| and | and | |||
| N | N | |||
| 1/2 * [1 - (2e) ]. | 1/2 * [1 - (2E) ]. | |||
| Neither of these will ever be exactly 0.5 unless e is zero, but we | Neither of these will ever be exactly 0.5 unless E is zero, but we | |||
| can bring them arbitrarily close to 0.5. If we want the probabilities | can bring them arbitrarily close to 0.5. If we want the probabilities | |||
| to be within some delta d of 0.5, i.e. then | to be within some delta d of 0.5, i.e. then | |||
| N | N | |||
| ( 0.5 + ( 0.5 * (2e) ) ) < 0.5 + d. | ( 0.5 + ( 0.5 * (2E) ) ) < 0.5 + d. | |||
| Solving for N yields N > log(2d)/log(2e). (Note that 2e is less than | Solving for N yields N > log(2d)/log(2E). (Note that 2E is less than | |||
| 1, so its log is negative. Division by a negative number reverses the | 1, so its log is negative. Division by a negative number reverses the | |||
| sense of an inequality.) | sense of an inequality.) | |||
| The following table gives the length of the string which must be | The following table gives the length of the string which must be | |||
| sampled for various degrees of skew in order to come within 0.001 of | sampled for various degrees of skew in order to come within 0.001 of | |||
| a 50/50 distribution. | a 50/50 distribution. | |||
| +---------+--------+-------+ | +---------+--------+-------+ | |||
| | Prob(1) | e | N | | | Prob(1) | E | N | | |||
| +---------+--------+-------+ | +---------+--------+-------+ | |||
| | 0.5 | 0.00 | 1 | | | 0.5 | 0.00 | 1 | | |||
| | 0.6 | 0.10 | 4 | | | 0.6 | 0.10 | 4 | | |||
| | 0.7 | 0.20 | 7 | | | 0.7 | 0.20 | 7 | | |||
| | 0.8 | 0.30 | 13 | | | 0.8 | 0.30 | 13 | | |||
| | 0.9 | 0.40 | 28 | | | 0.9 | 0.40 | 28 | | |||
| | 0.95 | 0.45 | 59 | | | 0.95 | 0.45 | 59 | | |||
| | 0.99 | 0.49 | 308 | | | 0.99 | 0.49 | 308 | | |||
| +---------+--------+-------+ | +---------+--------+-------+ | |||
| The last entry shows that even if the distribution is skewed 99% in | The last entry shows that even if the distribution is skewed 99% in | |||
| favor of ones, the parity of a string of 308 samples will be within | favor of ones, the parity of a string of 308 samples will be within | |||
| 0.001 of a 50/50 distribution. But, as we shall see in section 6.1.2, | 0.001 of a 50/50 distribution. But, as we shall see in section 6.1.2, | |||
| there are much stronger techniques that extract more of the available | there are much stronger techniques that extract more of the available | |||
| entropy. | entropy. | |||
| 5.2.2 Using Transition Mappings to De-Skew | 4.2 Using Transition Mappings to De-Skew | |||
| Another technique, originally due to von Neumann [VON NEUMANN], is to | Another technique, originally due to von Neumann [VON NEUMANN], is to | |||
| examine a bit stream as a sequence of non-overlapping pairs. You | examine a bit stream as a sequence of non-overlapping pairs. You | |||
| could then discard any 00 or 11 pairs found, interpret 01 as a 0 and | could then discard any 00 or 11 pairs found, interpret 01 as a 0 and | |||
| 10 as a 1. Assume the probability of a 1 is 0.5+e and the probability | 10 as a 1. Assume the probability of a 1 is 0.5+E and the probability | |||
| of a 0 is 0.5-e where e is the eccentricity of the source and | of a 0 is 0.5-E where E is the eccentricity of the source and | |||
| described in the previous section. Then the probability of each pair | described in the previous section. Then the probability of each pair | |||
| is as follows: | is as follows: | |||
| +------+-----------------------------------------+ | +------+-----------------------------------------+ | |||
| | pair | probability | | | pair | probability | | |||
| +------+-----------------------------------------+ | +------+-----------------------------------------+ | |||
| | 00 | (0.5 - e)^2 = 0.25 - e + e^2 | | | 00 | (0.5 - E)^2 = 0.25 - E + E^2 | | |||
| | 01 | (0.5 - e)*(0.5 + e) = 0.25 - e^2 | | | 01 | (0.5 - E)*(0.5 + E) = 0.25 - E^2 | | |||
| | 10 | (0.5 + e)*(0.5 - e) = 0.25 - e^2 | | | 10 | (0.5 + E)*(0.5 - E) = 0.25 - E^2 | | |||
| | 11 | (0.5 + e)^2 = 0.25 + e + e^2 | | | 11 | (0.5 + E)^2 = 0.25 + E + E^2 | | |||
| +------+-----------------------------------------+ | +------+-----------------------------------------+ | |||
| This technique will completely eliminate any bias but at the expense | This technique will completely eliminate any bias but at the expense | |||
| of taking an indeterminate number of input bits for any particular | of taking an indeterminate number of input bits for any particular | |||
| desired number of output bits. The probability of any particular pair | desired number of output bits. The probability of any particular pair | |||
| being discarded is 0.5 + 2e^2 so the expected number of input bits to | being discarded is 0.5 + 2E^2 so the expected number of input bits to | |||
| produce X output bits is X/(0.25 - e^2). | produce X output bits is X/(0.25 - E^2). | |||
| This technique assumes that the bits are from a stream where each bit | This technique assumes that the bits are from a stream where each bit | |||
| has the same probability of being a 0 or 1 as any other bit in the | has the same probability of being a 0 or 1 as any other bit in the | |||
| stream and that bits are not correlated, i.e., that the bits are | stream and that bits are not correlated, i.e., that the bits are | |||
| identical independent distributions. If alternate bits were from two | identical independent distributions. If alternate bits were from two | |||
| correlated sources, for example, the above analysis breaks down. | correlated sources, for example, the above analysis breaks down. | |||
| The above technique also provides another illustration of how a | The above technique also provides another illustration of how a | |||
| simple statistical analysis can mislead if one is not always on the | simple statistical analysis can mislead if one is not always on the | |||
| lookout for patterns that could be exploited by an adversary. If the | lookout for patterns that could be exploited by an adversary. If the | |||
| algorithm were mis-read slightly so that overlapping successive bits | algorithm were mis-read slightly so that overlapping successive bits | |||
| pairs were used instead of non-overlapping pairs, the statistical | pairs were used instead of non-overlapping pairs, the statistical | |||
| analysis given is the same; however, instead of providing an unbiased | analysis given is the same; however, instead of providing an unbiased | |||
| uncorrelated series of random 1s and 0s, it instead produces a | uncorrelated series of random 1s and 0s, it instead produces a | |||
| totally predictable sequence of exactly alternating 1s and 0s. | totally predictable sequence of exactly alternating 1s and 0s. | |||
| 5.2.3 Using FFT to De-Skew | 4.3 Using FFT to De-Skew | |||
| When real world data consists of strongly biased or correlated bits, | When real world data consists of strongly correlated bits, it may | |||
| it may still contain useful amounts of randomness. This randomness | still contain useful amounts of entropy. This entropy can be | |||
| can be extracted through use of various transforms, the most powerful | extracted through use of various transforms, the most powerful of | |||
| of which are described in section 6.1.2 below. | which are described in section 5.2 below. | |||
| Using the Fourier transform of the data or its optimized variant, the | Using the Fourier transform of the data or its optimized variant, the | |||
| FFT, is an technique interesting primarily for theoretical reasons. | FFT, is an technique interesting primarily for theoretical reasons. | |||
| It can be show that this will discard strong correlations. If | It can be show that this will discard strong correlations. If | |||
| adequate data is processed and remaining correlations decay, spectral | adequate data is processed and remaining correlations decay, spectral | |||
| lines approaching statistical independence and normally distributed | lines approaching statistical independence and normally distributed | |||
| randomness can be produced [BRILLINGER]. | randomness can be produced [BRILLINGER]. | |||
| 5.2.4 Using Compression to De-Skew | 4.4 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. Therefore the shorter sequences must be de-skewed relative | sequences. Therefore the shorter sequences must be de-skewed relative | |||
| to the input. | to 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 in Section 6.1.2. At a minimum, the | compared with those described in Section 5.2. At a minimum, the | |||
| beginning of the compressed sequence should be skipped and only later | beginning of the compressed sequence should be skipped and only later | |||
| bits used for applications requiring roughly random bits. | bits used for applications requiring roughly random bits. | |||
| 5.3 Existing Hardware Can Be Used For Randomness | 5. Mixing | |||
| As described below, many computers come with hardware that can, with | ||||
| care, be used to generate truly random quantities. | ||||
| 5.3.1 Using Existing Sound/Video Input | ||||
| Many computers are built with inputs that digitize some real world | ||||
| analog source, such as sound from a microphone or video input from a | ||||
| camera. Under appropriate circumstances, such input can provide | ||||
| reasonably high quality random bits. The "input" from a sound | ||||
| digitizer with no source plugged in or a camera with the lens cap on, | ||||
| if the system has enough gain to detect anything, is essentially | ||||
| thermal noise. This method is extremely hardware and implementation | ||||
| dependent. | ||||
| For example, on some UNIX based systems, one can read from the | ||||
| /dev/audio device with nothing plugged into the microphone jack or | ||||
| the microphone receiving only low level background noise. Such data | ||||
| is essentially random noise although it should not be trusted without | ||||
| some checking in case of hardware failure. It will, in any case, need | ||||
| to be de-skewed as described elsewhere. | ||||
| Combining this with compression to de-skew one can, in UNIXese, | ||||
| generate a huge amount of medium quality random data by doing | ||||
| cat /dev/audio | compress - >random-bits-file | ||||
| A detailed examination of this type of randomness source appears in | ||||
| [TURBID]. | ||||
| 5.3.2 Using Existing Disk Drives | ||||
| Disk drives have small random fluctuations in their rotational speed | ||||
| due to chaotic air turbulence [DAVIS, Jakobsson]. By adding low | ||||
| level disk seek time instrumentation to a system, a series of | ||||
| measurements can be obtained that include this randomness. Such data | ||||
| is usually highly correlated so that significant processing is | ||||
| needed, such as described in 6.1.2 below. Nevertheless | ||||
| experimentation a decade ago showed that, with such processing, even | ||||
| slow disk drives on the slower computers of that day could easily | ||||
| produce 100 bits a minute or more of excellent random data. | ||||
| Every increase in processor speed, which increases the resolution | ||||
| with which disk motion can be timed, or increase in the rate of disk | ||||
| seeks, increases the rate of random bit generation possible with this | ||||
| technique. At the time of this paper and using modern hardware, a | ||||
| more typical rate of random bit production would be in excess of | ||||
| 10,000 bits a second. This technique is used in many operating system | ||||
| library random number generators. | ||||
| Note: the inclusion of cache memories in disk controllers has little | ||||
| effect on this technique if very short seek times, which represent | ||||
| cache hits, are simply ignored. | ||||
| 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 fixed | ||||
| frequency, say one determined by a stable crystal oscillator, some | ||||
| amount of entropy can be extracted due to variations in the free- | ||||
| running oscillator timing. It is possible to increase the rate of | ||||
| entropy by xor'ing sampled values from a few ring oscillators with | ||||
| relatively prime lengths. It is sometimes recommended that an odd | ||||
| number of rings be used so that, even if the rings somehow become | ||||
| synchronously locked to each other, there will still be sampled bit | ||||
| transitions. Another possibility source to sample is the output of a | ||||
| noisy diode. | ||||
| Sampled bits from such sources will have to be heavily de-skewed, as | ||||
| disk rotation timings must be (Section 5.3.2). An engineering study | ||||
| would be needed to determine the amount of entropy being produced | ||||
| depending on the particular design. In any case, these can be good | ||||
| sources whose cost is a trivial amount of hardware by modern | ||||
| standards. | ||||
| As an example, IEEE 802.11i suggests that the circuit below be | ||||
| considered, with due attention in the design to isolation of the | ||||
| rings from each other and from clocked circuits to avoid undesired | ||||
| synchronization, etc., and extensive post processing. [IEEE 802.11i] | ||||
| |\ |\ |\ | ||||
| +-->| >0-->| >0-- 19 total --| >0--+-------+ | ||||
| | |/ |/ |/ | | | ||||
| | | | | ||||
| +----------------------------------+ V | ||||
| +-----+ | ||||
| |\ |\ |\ | | output | ||||
| +-->| >0-->| >0-- 23 total --| >0--+--->| XOR |------> | ||||
| | |/ |/ |/ | | | | ||||
| | | +-----+ | ||||
| +----------------------------------+ ^ ^ | ||||
| | | | ||||
| |\ |\ |\ | | | ||||
| +-->| >0-->| >0-- 29 total --| >0--+------+ | | ||||
| | |/ |/ |/ | | | ||||
| | | | | ||||
| +----------------------------------+ | | ||||
| | | ||||
| other randomness if available--------------+ | ||||
| 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 strong reliable | |||
| source? It is to obtain random input from a number of uncorrelated | hardware entropy source? It is to obtain input from a number of | |||
| sources and to mix them with a strong mixing function. Such a | uncorrelated sources and to mix them with a strong mixing function. | |||
| function will preserve the randomness present in any of the sources | Such a function will preserve the entropy present in any of the | |||
| even if other quantities being combined happen to be fixed or easily | sources even if other quantities being combined happen to be fixed or | |||
| guessable. This may be advisable even with a good hardware source, as | easily guessable (low entropy). This may be advisable even with a | |||
| hardware can also fail, though this should be weighed against any | good hardware source, as hardware can also fail, though this should | |||
| increase in the chance of overall failure due to added software | be weighed against any increase in the chance of overall failure due | |||
| complexity. | to added software complexity. | |||
| 6.1 Mixing Functions | Once you have used good sources, such as some of those listed in | |||
| Section 3, and mixed them as described in this section, you have a | ||||
| strong seed. This can then be used to produce large quantities of | ||||
| cryptographically strong material as described in Sections 6 and 7. | ||||
| A strong mixing function is one which combines inputs and produces an | A strong mixing function is one which combines inputs and produces an | |||
| output where each output bit is a different complex non-linear | output where each output bit is a different complex non-linear | |||
| function of all the input bits. On average, changing any input bit | function of all the input bits. On average, changing any input bit | |||
| will change about half the output bits. But because the relationship | will change about half the output bits. But because the relationship | |||
| is complex and non-linear, no particular output bit is guaranteed to | is complex and non-linear, no particular output bit is guaranteed to | |||
| change when any particular input bit is changed. | change when any particular input bit is changed. | |||
| Consider the problem of converting a stream of bits that is skewed | Consider the problem of converting a stream of bits that is skewed | |||
| towards 0 or 1 or which has a somewhat predictable pattern to a | towards 0 or 1 or which has a somewhat predictable pattern to a | |||
| shorter stream which is more random, as discussed in Section 5.2 | shorter stream which is more random, as discussed in Section 4 above. | |||
| above. This is simply another case where a strong mixing function is | This is simply another case where a strong mixing function is | |||
| desired, mixing the input bits to produce a smaller number of output | desired, mixing the input bits to produce a smaller number of output | |||
| bits. The technique given in Section 5.2.1 of using the parity of a | bits. The technique given in Section 4.1 of using the parity of a | |||
| number of bits is simply the result of successively Exclusive Or'ing | number of bits is simply the result of successively Exclusive Or'ing | |||
| them which is examined as a trivial mixing function immediately | them which is examined as a trivial mixing function immediately | |||
| below. Use of stronger mixing functions to extract more of the | below. Use of stronger mixing functions to extract more of the | |||
| randomness in a stream of skewed bits is examined in Section 6.1.2. | randomness in a stream of skewed bits is examined in Section 5.2. See | |||
| also [NASLUND]. | ||||
| 6.1.1 A Trivial Mixing Function | 5.1 A Trivial Mixing Function | |||
| A trivial example for single bit inputs described only for expository | A trivial example for single bit inputs described only for expository | |||
| purposes is the Exclusive Or function, which is equivalent to | purposes is the Exclusive Or function, which is equivalent to | |||
| addition without carry, as show in the table below. This is a | addition without carry, as show in the table below. This is a | |||
| degenerate case in which the one output bit always changes for a | degenerate case in which the one output bit always changes for a | |||
| change in either input bit. But, despite its simplicity, it provides | change in either input bit. But, despite its simplicity, it provides | |||
| a useful illustration. | a useful illustration. | |||
| +-----------+-----------+----------+ | +-----------+-----------+----------+ | |||
| | input 1 | input 2 | output | | | input 1 | input 2 | output | | |||
| +-----------+-----------+----------+ | +-----------+-----------+----------+ | |||
| | 0 | 0 | 0 | | | 0 | 0 | 0 | | |||
| | 0 | 1 | 1 | | | 0 | 1 | 1 | | |||
| | 1 | 0 | 1 | | | 1 | 0 | 1 | | |||
| | 1 | 1 | 0 | | | 1 | 1 | 0 | | |||
| +-----------+-----------+----------+ | +-----------+-----------+----------+ | |||
| If inputs 1 and 2 are uncorrelated and combined in this fashion then | If inputs 1 and 2 are uncorrelated and combined in this fashion then | |||
| the output will be an even better (less skewed) random bit than the | the output will be an even better (less skewed) random bit than the | |||
| inputs. If we assume an "eccentricity" e as defined in Section 5.2 | inputs. If we assume an "eccentricity" E as defined in Section 5.2 | |||
| above, then the output eccentricity relates to the input eccentricity | above, then the output eccentricity relates to the input eccentricity | |||
| as follows: | as follows: | |||
| e = 2 * e * e | E = 2 * E * E | |||
| output input 1 input 2 | output input 1 input 2 | |||
| Since e is never greater than 1/2, the eccentricity is always | Since E is never greater than 1/2, the eccentricity is always | |||
| improved except in the case where at least one input is a totally | improved except in the case where at least one input is a totally | |||
| skewed constant. This is illustrated in the following table where the | skewed constant. This is illustrated in the following table where the | |||
| top and left side values are the two input eccentricities and the | top and left side values are the two input eccentricities and the | |||
| entries are the output eccentricity: | entries are the output eccentricity: | |||
| +--------+--------+--------+--------+--------+--------+--------+ | +--------+--------+--------+--------+--------+--------+--------+ | |||
| | e | 0.00 | 0.10 | 0.20 | 0.30 | 0.40 | 0.50 | | | E | 0.00 | 0.10 | 0.20 | 0.30 | 0.40 | 0.50 | | |||
| +--------+--------+--------+--------+--------+--------+--------+ | +--------+--------+--------+--------+--------+--------+--------+ | |||
| | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | | | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | | |||
| | 0.10 | 0.00 | 0.02 | 0.04 | 0.06 | 0.08 | 0.10 | | | 0.10 | 0.00 | 0.02 | 0.04 | 0.06 | 0.08 | 0.10 | | |||
| | 0.20 | 0.00 | 0.04 | 0.08 | 0.12 | 0.16 | 0.20 | | | 0.20 | 0.00 | 0.04 | 0.08 | 0.12 | 0.16 | 0.20 | | |||
| | 0.30 | 0.00 | 0.06 | 0.12 | 0.18 | 0.24 | 0.30 | | | 0.30 | 0.00 | 0.06 | 0.12 | 0.18 | 0.24 | 0.30 | | |||
| | 0.40 | 0.00 | 0.08 | 0.16 | 0.24 | 0.32 | 0.40 | | | 0.40 | 0.00 | 0.08 | 0.16 | 0.24 | 0.32 | 0.40 | | |||
| | 0.50 | 0.00 | 0.10 | 0.20 | 0.30 | 0.40 | 0.50 | | | 0.50 | 0.00 | 0.10 | 0.20 | 0.30 | 0.40 | 0.50 | | |||
| +--------+--------+--------+--------+--------+--------+--------+ | +--------+--------+--------+--------+--------+--------+--------+ | |||
| However, keep in mind that the above calculations assume that the | However, keep in mind that the above calculations assume that the | |||
| inputs are not correlated. If the inputs were, say, the parity of the | inputs are not correlated. If the inputs were, say, the parity of the | |||
| number of minutes from midnight on two clocks accurate to a few | number of minutes from midnight on two clocks accurate to a few | |||
| seconds, then each might appear random if sampled at random intervals | seconds, then each might appear random if sampled at random intervals | |||
| much longer than a minute. Yet if they were both sampled and combined | much longer than a minute. Yet if they were both sampled and combined | |||
| with xor, the result would be zero most of the time. | with xor, the result would be zero most of the time. | |||
| 6.1.2 Stronger Mixing Functions | 5.2 Stronger Mixing Functions | |||
| The US Government Advanced Encryption Standard [AES] is an example of | The US Government Advanced Encryption Standard [AES] is an example of | |||
| a strong mixing function for multiple bit quantities. It takes up to | a strong mixing function for multiple bit quantities. It takes up to | |||
| 384 bits of input (128 bits of "data" and 256 bits of "key") and | 384 bits of input (128 bits of "data" and 256 bits of "key") and | |||
| produces 128 bits of output each of which is dependent on a complex | 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 | |||
| skipping to change at page 24, line 40 ¶ | skipping to change at page 21, line 40 ¶ | |||
| the 1st part of the output, then encrypt B with C and then A for more | the 1st part of the output, then encrypt B with C and then A for more | |||
| output and, if necessary, encrypt C with A and then B for yet more | output and, if necessary, encrypt C with A and then B for yet more | |||
| output. Still more output can be produced by reversing the order of | output. Still more output can be produced by reversing the order of | |||
| the keys given above to stretch things. The same can be done with the | the keys given above to stretch things. The same can be done with the | |||
| hash functions by hashing various subsets of the input data or | hash functions by hashing various subsets of the input data or | |||
| different copies of the input data with different prefixes and/or | different copies of the input data with different prefixes and/or | |||
| suffixes to produce multiple outputs. | suffixes to produce multiple outputs. | |||
| 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 4.1 above reduced this to | |||
| to one bit with only a 1/1000 deviance from being equally likely a | one bit with only a 1/1000 deviance from being equally likely a zero | |||
| zero or one. But, applying the equation for information given in | or one. But, applying the equation for information given in Section | |||
| Section 2, this 308 bit skewed sequence has over 5 bits of | 2, this 308 bit skewed sequence has over 5 bits of information in it. | |||
| information in it. Thus hashing it with SHA-1 and taking the bottom 5 | Thus hashing it with SHA-1 and taking the bottom 5 bits of the result | |||
| bits of the result would yield 5 unbiased random bits as opposed to | would yield 5 unbiased random bits as opposed to the single bit given | |||
| the single bit given by calculating the parity of the string. | by calculating the parity of the string. Alternatively, for some | |||
| Alternatively, for some applications, you could use the entire hash | applications, you could use the entire hash output to retain almost | |||
| output to retain almost all of the entropy. | all of the 5+ bits of entropy in a 160 bit quantity. | |||
| 6.1.3 Using S-Boxes for Mixing | 5.3 Using S-Boxes for Mixing | |||
| Many modern block encryption functions, including DES and AES, | Many modern block encryption functions, including DES and AES, | |||
| incorporate modules known as S-Boxes (substitution boxes). These | incorporate modules known as S-Boxes (substitution boxes). These | |||
| produce a smaller number of outputs from a larger number of inputs | produce a smaller number of outputs from a larger number of inputs | |||
| through a complex non-linear mixing function which would have the | through a complex non-linear mixing function which would have the | |||
| effect of concentrating limited entropy in the inputs into the | effect of concentrating limited entropy in the inputs into the | |||
| output. | output. | |||
| S-Boxes sometimes incorporate bent Boolean functions (functions of an | S-Boxes sometimes incorporate bent Boolean functions (functions of an | |||
| even number of bits producing one output bit with maximum non- | even number of bits producing one output bit with maximum non- | |||
| linearity). Looking at the output for all input pairs differing in | linearity). Looking at the output for all input pairs differing in | |||
| any particular bit position, exactly half the outputs are different. | 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 | 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 | that any linear combination of these functions is also a bent | |||
| function is called a "perfect S-Box". | function is called a "perfect S-Box". | |||
| S-boxes and various repeated application or cascades of such boxes | S-boxes and various repeated application or cascades of such boxes | |||
| can be used for mixing. [SBOX*] | can be used for mixing. [SBOX*] | |||
| 6.1.4 Diffie-Hellman as a Mixing Function | 5.4 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 the | secret is a mixture of initial quantities generated by each of the | |||
| parties [D-H]. | parties [D-H]. | |||
| If these initial quantities are random and uncorrelated, then the | If these initial quantities are random and uncorrelated, then the | |||
| shared secret combines that randomness, but, of course, can not | shared secret combines their entropy, but, of course, can not produce | |||
| produce more randomness than the size of the shared secret generated. | more randomness than the size of the shared secret generated. | |||
| While this is true if the Diffie-Hellman computation is performed | While this is true if the Diffie-Hellman computation is performed | |||
| privately, if an adversary can observe either of the public keys and | privately, an adversary that can observe either of the public keys | |||
| knows the modulus being used, they need only search through the space | and knows the modulus being used need only search through the space | |||
| of the other secret key in order to be able to calculate the shared | of the other secret key in order to be able to calculate the shared | |||
| secret [D-H]. So, conservatively, it would be best to consider public | secret [D-H]. So, conservatively, it would be best to consider public | |||
| Diffie-Hellman to produce a quantity whose guessability corresponds | Diffie-Hellman to produce a quantity whose guessability corresponds | |||
| to the worst of the two inputs. | to the worst of the two inputs. Because of this and the fact that | |||
| Diffie-Hellman is computationally intensive, its use as a mixing | ||||
| function is not recommended. | ||||
| 6.1.5 Using a Mixing Function to Stretch Random Bits | 5.5 Using a Mixing Function to Stretch Random Bits | |||
| While it is not necessary for a mixing function to produce the same | While it is not necessary for a mixing function to produce the same | |||
| or fewer bits than its inputs, mixing bits cannot "stretch" the | or fewer bits than its inputs, mixing bits cannot "stretch" the | |||
| amount of random unpredictability present in the inputs. Thus four | amount of random unpredictability present in the inputs. Thus four | |||
| inputs of 32 bits each where there is 12 bits worth of | inputs of 32 bits each where there is 12 bits worth of | |||
| unpredictability (such as 4,096 equally probable values) in each | unpredictability (such as 4,096 equally probable values) in each | |||
| input cannot produce more than 48 bits worth of unpredictable output. | input cannot produce more than 48 bits worth of unpredictable output. | |||
| The output can be expanded to hundreds or thousands of bits by, for | The output can be expanded to hundreds or thousands of bits by, for | |||
| example, mixing with successive integers, but the clever adversary's | example, mixing with successive integers, but the clever adversary's | |||
| search space is still 2^48 possibilities. Furthermore, mixing to | search space is still 2^48 possibilities. Furthermore, mixing to | |||
| fewer bits than are input will tend to strengthen the randomness of | fewer bits than are input will tend to strengthen the randomness of | |||
| the output. | the output. | |||
| The last table in Section 6.1.1 shows that mixing a random bit with a | The last table in Section 5.1 shows that mixing a random bit with a | |||
| constant bit with Exclusive Or will produce a random bit. While this | constant bit with Exclusive Or will produce a random bit. While this | |||
| is true, it does not provide a way to "stretch" one random bit into | is true, it does not provide a way to "stretch" one random bit into | |||
| more than one. If, for example, a random bit is mixed with a 0 and | more than one. If, for example, a random bit is mixed with a 0 and | |||
| then with a 1, this produces a two bit sequence but it will always be | then with a 1, this produces a two bit sequence but it will always be | |||
| either 01 or 10. Since there are only two possible values, there is | either 01 or 10. Since there are only two possible values, there is | |||
| still only the one bit of original randomness. | still only the one bit of original randomness. | |||
| 6.1.6 Other Factors in Choosing a Mixing Function | 5.6 Other Factors in Choosing a Mixing Function | |||
| For local use, AES has the advantages that it has been widely tested | For local use, AES has the advantages that it has been widely tested | |||
| for flaws, is reasonably efficient in software, and is widely | for flaws, is reasonably efficient in software, and is widely | |||
| documented and implemented with hardware and software implementations | documented and implemented with hardware and software implementations | |||
| available all over the world including open source code. The SHA* | available all over the world including open source code. The SHA* | |||
| family have had a little less study and tend to require more CPU | family have had a little less study and tend to require more CPU | |||
| cycles than AES but there is no reason to believe they are flawed. | cycles than AES but there is no reason to believe they are flawed. | |||
| Both SHA* and MD5 were derived from the earlier MD4 algorithm. They | Both SHA* and MD5 were derived from the earlier MD4 algorithm. They | |||
| all have source code available [SHA*, MD*]. Some signs of weakness | all have source code available [SHA*, MD*]. Some signs of weakness | |||
| have been found in MD4 and MD5. In particular, MD4 has only three | have been found in MD4 and MD5. In particular, MD4 has only three | |||
| rounds and there are several independent breaks of the first two or | rounds and there are several independent breaks of the first two or | |||
| last two rounds. And some collisions have been found in MD5 output. | last two rounds. And some collisions have been found in MD5 output. | |||
| AES was selected by a robust, public, and international process. It | AES was selected by a robust, public, and international process. It | |||
| and SHA* have been vouched for by the US National Security Agency | and SHA* have been vouched for by the US National Security Agency | |||
| (NSA) on the basis of criteria that mostly remain secret, as was DES. | (NSA) on the basis of criteria that mostly remain secret, as was DES. | |||
| While this has been the cause of much speculation and doubt, | While this has been the cause of much speculation and doubt, | |||
| investigation of DES over the years has indicated that NSA | 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 weakness | IBM, was primarily to strengthen it. There has been no announcement | |||
| has been found in DES. It is likely that the NSA modifications to MD4 | of a concealed or special weakness being found in DES. It is likely | |||
| to produce the SHA algorithms similarly strengthened these | that the NSA modifications to MD4 to produce the SHA algorithms | |||
| algorithms, possibly against threats not yet known in the public | similarly strengthened these algorithms, possibly against threats not | |||
| cryptographic community. | yet known in the public cryptographic community. | |||
| Where input lengths are unpredictable, hash algorithms are a little | Where input lengths are unpredictable, hash algorithms are more | |||
| more convenient to use than block encryption algorithms since they | convenient to use than block encryption algorithms since they are | |||
| are generally designed to accept variable length inputs. Block | generally designed to accept variable length inputs. Block encryption | |||
| encryption algorithms generally require an additional padding | algorithms generally require an additional padding algorithm to | |||
| algorithm to accommodate inputs that are not an even multiple of the | accommodate inputs that are not an even multiple of the block size. | |||
| block size. | ||||
| As of the time of this document, the authors know of no patent claims | As of the time of this document, the authors know of no patent claims | |||
| to the basic AES, DES, SHA*, MD4, and MD5 algorithms other than | to the basic AES, DES, SHA*, MD4, and MD5 algorithms other than | |||
| patents for which an irrevocable royalty free license has been | patents for which an irrevocable royalty free license has been | |||
| granted to the world. There may, of course, be basic patents of which | granted to the world. There may, of course, be essential patents of | |||
| the authors are unaware or patents on implementations or uses or | which the authors are unaware or patents on implementations or uses | |||
| other relevant patents issued or to be issued. | or other relevant patents issued or to be issued. | |||
| 6.2 Non-Hardware Sources of Randomness | 6. Pseudo Random Number Generators | |||
| The best source of input for mixing would be a hardware randomness | When you have a seed with sufficient entropy, from input as described | |||
| such as ring oscillators, disk drive timing, thermal noise, or | in Section 3 possibly de-skewed and mixed as described in Sections 4 | |||
| radioactive decay. However, if that is not available, there are other | and 5, you can algorithmically extend that seed to produce a large | |||
| possibilities. These include system clocks, system or input/output | quantity of cryptographically strong random quantities. Such | |||
| buffers, user/system/hardware/network serial numbers and/or addresses | algorithms are platform independent and can operate in the same | |||
| and timing, and user input. Unfortunately, each of these sources can | fashion on any computer. To be secure their input and internal | |||
| produce very limited or predictable values under some circumstances. | workings must be protected from adversarial observation. | |||
| Some of the sources listed above would be quite strong on multi-user | The design of such pseudo random number generation algorithms, like | |||
| systems where, in essence, each user of the system is a source of | the design of symmetric encryption algorithms, is not a task for | |||
| randomness. However, on a small single user or embedded system, | amateurs. Section 6.1 below lists a number of bad ideas which failed | |||
| especially at start up, it might be possible for an adversary to | algorithms have used. If you are interested in what works, you can | |||
| assemble a similar configuration. This could give the adversary | skip 6.1 and just read the remainder of this section and Section 7 | |||
| inputs to the mixing process that were sufficiently correlated to | below which describes and gives references for some standard pseudo | |||
| those used originally as to make exhaustive search practical. | random number generation algorithms. See Section 7 and [X9.82 - Part | |||
| 3]. | ||||
| The use of multiple random inputs with a strong mixing function is | 6.1 Some Bad Ideas | |||
| recommended and can overcome weakness in any particular input. The | ||||
| timing and content of requested "random" user keystrokes can yield | ||||
| hundreds of random bits but conservative assumptions need to be made. | ||||
| For example, assuming at most a few bits of randomness if the inter- | ||||
| keystroke interval is unique in the sequence up to that point and a | ||||
| similar assumption if the key hit is unique but assuming that no bits | ||||
| of randomness are present in the initial key value or if the timing | ||||
| or key value duplicate previous values. The results of mixing these | ||||
| timings and characters typed could be further combined with clock | ||||
| values and other inputs. | ||||
| This strategy may make practical portable code to produce good random | The subsections below describe a number of idea which might seem | |||
| numbers for security even if some of the inputs are very weak on some | reasonable but which lead to insecure pseudo random number | |||
| of the target systems. However, it may still fail against a high | generation. | |||
| grade attack on small, single user or embedded systems, especially if | ||||
| the adversary has ever been able to observe the generation process in | ||||
| the past. A hardware based random source is still preferable. | ||||
| 6.3 Cryptographically Strong Sequences | 6.1.1 The Fallacy of Complex Manipulation | |||
| One strategy which may give a misleading appearance of | ||||
| unpredictability is to take a very complex algorithm (or an excellent | ||||
| traditional pseudo-random number generator with good statistical | ||||
| properties) and calculate a cryptographic key by starting with | ||||
| limited data such as the computer system clock value as the seed. An | ||||
| adversary who knew roughly when the generator was started would have | ||||
| a relatively small number of seed values to test as they would know | ||||
| likely values of the system clock. Large numbers of pseudo-random | ||||
| bits could be generated but the search space an adversary would need | ||||
| to check could be quite small. | ||||
| Thus very strong and/or complex manipulation of data will not help if | ||||
| the adversary can learn what the manipulation is and there is not | ||||
| enough entropy in the starting seed value. They can usually use the | ||||
| limited number of results stemming from a limited number of seed | ||||
| values to defeat security. | ||||
| Another serious strategy error is to assume that a very complex | ||||
| pseudo-random number generation algorithm will produce strong random | ||||
| numbers when there has been no theory behind or analysis of the | ||||
| algorithm. There is a excellent example of this fallacy right near | ||||
| the beginning of Chapter 3 in [KNUTH] where the author describes a | ||||
| complex algorithm. It was intended that the machine language program | ||||
| corresponding to the algorithm would be so complicated that a person | ||||
| trying to read the code without comments wouldn't know what the | ||||
| program was doing. Unfortunately, actual use of this algorithm showed | ||||
| that it almost immediately converged to a single repeated value in | ||||
| one case and a small cycle of values in another case. | ||||
| Not only does complex manipulation not help you if you have a limited | ||||
| range of seeds but blindly chosen complex manipulation can destroy | ||||
| the entropy in a good seed! | ||||
| 6.1.2 The Fallacy of Selection from a Large Database | ||||
| Another strategy that can give a misleading appearance of | ||||
| unpredictability is selection of a quantity randomly from a database | ||||
| and assume that its strength is related to the total number of bits | ||||
| in the database. For example, typical USENET servers process many | ||||
| megabytes of information per day [USENET]. Assume a random quantity | ||||
| was 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 | ||||
| unguessability. Even after allowing that much of the data is human | ||||
| language and probably has no more than 2 or 3 bits of information per | ||||
| byte, it doesn't yield 32*2 = 64 bits of unguessability. For an | ||||
| adversary with access to the same Usenet database the unguessability | ||||
| rests only on the starting point of the selection. That is perhaps a | ||||
| little over a couple of dozen bits of unguessability. | ||||
| The same argument applies to selecting sequences from the data on a | ||||
| publicly available CD/DVD recording or any other large public | ||||
| database. If the adversary has access to the same database, this | ||||
| "selection from a large volume of data" step buys little. However, | ||||
| if a selection 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. | ||||
| 6.1.3. Traditional Pseudo-Random Sequences | ||||
| This section talks about traditional sources of deterministic of | ||||
| "pseudo-random" numbers. These typically start with a "seed" quantity | ||||
| and use simple numeric or logical operations to produce a sequence of | ||||
| values. Note that none of the techniques discussed in this section is | ||||
| suitable for cryptographic use. They are presented for general | ||||
| information. | ||||
| [KNUTH] has a classic exposition on pseudo-random numbers. | ||||
| Applications he mentions are simulation of natural phenomena, | ||||
| sampling, numerical analysis, testing computer programs, decision | ||||
| making, and games. None of these have the same characteristics as the | ||||
| sort of security uses we are talking about. Only in the last two | ||||
| could there be an adversary trying to find the random quantity. | ||||
| However, in these cases, the adversary normally has only a single | ||||
| chance to use a guessed value. In guessing passwords or attempting to | ||||
| break an encryption scheme, the adversary normally has many, perhaps | ||||
| unlimited, chances at guessing the correct value. Sometimes they can | ||||
| store the message they are trying to break and repeatedly attack it. | ||||
| They are also be assumed to be aided by a computer. | ||||
| For testing the "randomness" of numbers, Knuth suggests a variety of | ||||
| measures including statistical and spectral. These tests check things | ||||
| like autocorrelation between different parts of a "random" sequence | ||||
| or distribution of its values. But they could be met by a constant | ||||
| stored random sequence, such as the "random" sequence printed in the | ||||
| CRC Standard Mathematical Tables [CRC]. Despite meeting all the tests | ||||
| suggested by Knuth, that sequence is unsuitable for cryptographic use | ||||
| as adversaries must be assumed to have copies of all common published | ||||
| "random" sequences and will able to spot the source and predict | ||||
| future values. | ||||
| A typical pseudo-random number generation technique, known as a | ||||
| linear congruence pseudo-random number generator, is modular | ||||
| arithmetic where the value numbered N+1 is calculated from the value | ||||
| numbered N by | ||||
| V = ( V * a + b )(Mod c) | ||||
| N+1 N | ||||
| The above technique has a strong relationship to linear shift | ||||
| register pseudo-random number generators, which are well understood | ||||
| cryptographically [SHIFT*]. In such generators bits are introduced at | ||||
| one end of a shift register as the Exclusive Or (binary sum without | ||||
| carry) of bits from selected fixed taps into the register. For | ||||
| example: | ||||
| +----+ +----+ +----+ +----+ | ||||
| | B | <-- | B | <-- | B | <-- . . . . . . <-- | B | <-+ | ||||
| | 0 | | 1 | | 2 | | n | | | ||||
| +----+ +----+ +----+ +----+ | | ||||
| | | | | | ||||
| | | V +-----+ | ||||
| | V +----------------> | | | ||||
| V +-----------------------------> | XOR | | ||||
| +---------------------------------------------------> | | | ||||
| +-----+ | ||||
| V = ( ( V * 2 ) + B .xor. B ... )(Mod 2^n) | ||||
| N+1 N 0 2 | ||||
| The goodness of traditional pseudo-random number generator algorithms | ||||
| is measured by statistical tests on such sequences. Carefully chosen | ||||
| values a, b, c, and initial V or the placement of shift register tap | ||||
| in the above simple processes can produce excellent statistics. | ||||
| These sequences may be adequate in simulations (Monte Carlo | ||||
| experiments) as long as the sequence is orthogonal to the structure | ||||
| of the space being explored. Even there, subtle patterns may cause | ||||
| problems. However, such sequences are clearly bad for use in security | ||||
| applications. They are fully predictable if the initial state is | ||||
| known. Depending on the form of the pseudo-random number generator, | ||||
| the sequence may be determinable from observation of a short portion | ||||
| of the sequence [SCHNEIER, STERN]. For example, with the generators | ||||
| above, one can determine V(n+1) given knowledge of V(n). In fact, it | ||||
| has been shown that with these techniques, even if only one bit of | ||||
| the pseudo-random values are released, the seed can be determined | ||||
| from short sequences. | ||||
| Not only have linear congruent generators been broken, but techniques | ||||
| are now known for breaking all polynomial congruent generators. | ||||
| [KRAWCZYK] | ||||
| 6.2 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 [FERGUSON, SCHNEIER], | cryptographically strong steps from that seed [FERGUSON, SCHNEIER], | |||
| and do not reveal the complete state of the generator in the sequence | and 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 | |||
| skipping to change at page 28, line 32 ¶ | skipping to change at page 29, line 20 ¶ | |||
| (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. This is commonly referred to as a simple stream | the xor operation. This is commonly referred to as a simple stream | |||
| cipher.) | cipher.) | |||
| 6.3.1 OFB and CTR Sequences | 6.2.1 OFB and CTR Sequences | |||
| One way to achieve a strong sequence is to have the values be | One way to achieve a strong sequence is to have the values be | |||
| produced by taking a seed value and hashing the quantities produced | produced by taking a seed value and hashing the quantities produced | |||
| by concatenating the seed with successive integers or the like and | by concatenating the seed with successive integers or the like and | |||
| then mask the values obtained so as to limit the amount of generator | then mask the values obtained so as to limit the amount of generator | |||
| state available to the adversary. | state 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 successive integers as in | random key and seed value to encrypt successive integers as in | |||
| counter (CTR) mode encryption. Alternatively, you can feedback all of | counter (CTR) mode encryption. Alternatively, you can feedback all of | |||
| the output encrypted value into the value to be encrypted for the | the output value from encryption into the value to be encrypted for | |||
| next iteration. This is a particular example of output feedback mode | the next iteration. This is a particular example of output feedback | |||
| (OFB). [MODES] | mode (OFB). [MODES] | |||
| An example is shown below where shifting and masking are used to | An example is shown below where shifting and masking are used to | |||
| combine part of the output feedback with part of the old input. This | combine part of the output feedback with part of the old input. This | |||
| type of partial feedback should be avoided for reasons described | type of partial feedback should be avoided for reasons described | |||
| below. | below. | |||
| +---------------+ | +---------------+ | |||
| | V | | | V | | |||
| | | n |--+ | | | n |--+ | |||
| +--+------------+ | | +--+------------+ | | |||
| skipping to change at page 29, line 44 ¶ | skipping to change at page 30, line 44 ¶ | |||
| To predict values of a sequence from others when the sequence was | To predict values of a sequence from others when the sequence was | |||
| generated by these techniques is equivalent to breaking the | generated by these techniques is equivalent to breaking the | |||
| cryptosystem or inverting the "non-invertible" hashing involved with | cryptosystem or inverting the "non-invertible" hashing involved with | |||
| only partial information available. The less information revealed | only partial information available. The less information revealed | |||
| each iteration, the harder it will be for an adversary to predict the | each iteration, the harder it will be for an adversary to predict the | |||
| sequence. Thus it is best to use only one bit from each value. It has | sequence. Thus it is best to use only one bit from each value. It has | |||
| been shown that in some cases this makes it impossible to break a | been shown that in some cases this makes it impossible to break a | |||
| system even when the cryptographic system is invertible and can be | system even when the cryptographic system is invertible and can be | |||
| broken if all of each generated value was revealed. | broken if all of each generated value was revealed. | |||
| 6.3.2 The Blum Blum Shub Sequence Generator | 6.2.2 The Blum Blum Shub Sequence Generator | |||
| Currently the generator which has the strongest public proof of | Currently the generator which has the strongest public proof of | |||
| strength is called the Blum Blum Shub generator after its inventors | strength is called the Blum Blum Shub generator after its inventors | |||
| [BBS]. It is also very simple and is based on quadratic residues. | [BBS]. It is also very simple and is based on quadratic residues. | |||
| Its only disadvantage is that it is computationally intensive | Its only disadvantage is that it is computationally intensive | |||
| compared with the traditional techniques give in 6.3.1 above. This is | compared with the traditional techniques give in 6.1.3 above. This is | |||
| not a major draw back if it is used for moderately infrequent | not a major draw back if it is used for moderately infrequent | |||
| purposes, such as generating session keys. | purposes, such as generating session keys. | |||
| Simply choose two large prime numbers, say p and q, which both have | Simply choose two large prime numbers, say p and q, which both have | |||
| the property that you get a remainder of 3 if you divide them by 4. | the property that you get a remainder of 3 if you divide them by 4. | |||
| Let n = p * q. Then you choose a random number x relatively prime to | Let n = p * q. Then you choose a random number x relatively prime to | |||
| n. The initial seed for the generator and the method for calculating | n. The initial seed for the generator and the method for calculating | |||
| subsequent values are then | subsequent values are then | |||
| 2 | 2 | |||
| skipping to change at page 30, line 41 ¶ | skipping to change at page 31, 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 | 6.3 Entropy Pool Techniques | |||
| Many modern pseudo-random number sources utilize the technique of | Many modern pseudo-random number sources, such as those describe in | |||
| maintaining a "pool" of bits and providing operations for strongly | Sections 7.1.2 and 7.1.3, utilize the technique of maintaining a | |||
| mixing input with some randomness into the pool and extracting pseudo | "pool" of bits and providing operations for strongly mixing input | |||
| random bits from the pool. This is illustrated in the figure below. | with some randomness into the pool and extracting pseudo random bits | |||
| from the pool. This is illustrated in the figure below. | ||||
| +--------+ +------+ +---------+ | +--------+ +------+ +---------+ | |||
| --->| Mix In |--->| POOL |--->| Extract |---> | --->| Mix In |--->| POOL |--->| Extract |---> | |||
| | Bits | | | | Bits | | | Bits | | | | Bits | | |||
| +--------+ +------+ +---------+ | +--------+ +------+ +---------+ | |||
| ^ V | ^ V | |||
| | | | | | | |||
| +-----------+ | +-----------+ | |||
| Bits to be feed into the pool can be any of the various hardware, | Bits to be feed into the pool can be any of the various hardware, | |||
| environmental, or user input sources discussed above. It is also | environmental, or user input sources discussed above. It is also | |||
| common to save the state of the pool on system shut down and restore | common to save the state of the pool on system shut down and restore | |||
| it on re-starting, if stable storage is available. | it on re-starting, if stable storage is available. | |||
| Care must be taken that enough entropy has been added to the pool to | Care must be taken that enough entropy has been added to the pool to | |||
| support particular output uses desired. See Section 7.5 for more | support particular output uses desired. See [RSA BULL1] for similar | |||
| details on an example implementation and [RSA BULL1] for similar | ||||
| suggestions. | suggestions. | |||
| 7. Key Generation Examples and Standards | 7. Randomness Generation Examples and Standards | |||
| Several public standards and widely deployed examples are now in | Several public standards and widely deployed examples are now in | |||
| place for the generation of keys without special hardware. Three | place for the generation of keys or other cryptographically random | |||
| standards are described below. The two older standards use DES, with | quantities. Some, in section 7.1 below, include an entropy source. | |||
| its 64-bit block and key size limit, but any equally strong or | Others, described in section 7.2, provide the pseudo-random number | |||
| stronger mixing function could be substituted [DES]. The third is a | strong sequence generator but assume the input of a random seed or | |||
| more modern and stronger standard based on SHA-1 [SHA*]. Lastly the | input from a source of entropy. | |||
| widely deployed modern UNIX random number generators are described. | ||||
| 7.1 US DoD Recommendations for Password Generation | 7.1 Complete Randomness Generators | |||
| Three standards are described below. The two older standards use | ||||
| DES, with its 64-bit block and key size limit, but any equally strong | ||||
| or stronger mixing function could be substituted [DES]. The third is | ||||
| a more modern and stronger standard based on SHA-1 [SHA*]. Lastly | ||||
| the widely deployed modern UNIX and Windows random number generators | ||||
| are described. | ||||
| 7.1.1 US DoD Recommendations for Password Generation | ||||
| The United States Department of Defense has specific recommendations | The United States Department of Defense has specific recommendations | |||
| for password generation [DoD]. They suggest using the US Data | for password generation [DoD]. They suggest using the US Data | |||
| Encryption Standard [DES] in Output Feedback Mode [MODES] as follows: | Encryption Standard [DES] in Output Feedback Mode [MODES] as follows: | |||
| use an initialization vector determined from | use an initialization vector determined from | |||
| the system clock, | the system clock, | |||
| system ID, | system ID, | |||
| user ID, and | user ID, and | |||
| date and time; | date and time; | |||
| use a key determined from | use a key determined from | |||
| system interrupt registers, | system interrupt registers, | |||
| system status registers, and | system status registers, and | |||
| system counters; and, | system counters; and, | |||
| as plain text, use an external randomly generated 64 bit | as plain text, use an external randomly generated 64 bit | |||
| quantity such as 8 characters typed in by a system | quantity such as the ASCII bytes for 8 characters typed in by a | |||
| administrator. | system administrator. | |||
| The password can then be calculated from the 64 bit "cipher text" | The password can then be calculated from the 64 bit "cipher text" | |||
| generated by DES in 64-bit Output Feedback Mode. As many bits as are | generated by DES in 64-bit Output Feedback Mode. As many bits as are | |||
| needed can be taken from these 64 bits and expanded into a | needed can be taken from these 64 bits and expanded into a | |||
| pronounceable word, phrase, or other format if a human being needs to | pronounceable word, phrase, or other format if a human being needs to | |||
| remember the password. | remember the password. | |||
| 7.2 X9.17 Key Generation | 7.1.2 The /dev/random Device | |||
| The American National Standards Institute has specified a method for | ||||
| generating a sequence of keys as follows [X9.17]: | ||||
| s is the initial 64 bit seed | ||||
| 0 | ||||
| g is the sequence of generated 64 bit key quantities | ||||
| n | ||||
| k is a random key reserved for generating this key sequence | ||||
| t is the time at which a key is generated to as fine a resolution | ||||
| as is available (up to 64 bits). | ||||
| DES ( K, Q ) is the DES encryption of quantity Q with key K | ||||
| g = DES ( k, DES ( k, t ) .xor. s ) | ||||
| n n | ||||
| s = DES ( k, DES ( k, t ) .xor. g ) | ||||
| n+1 n | ||||
| If g sub n is to be used as a DES key, then every eighth bit should | ||||
| be adjusted for parity for that use but the entire 64 bit unmodified | ||||
| g should be used in calculating the next s. | ||||
| 7.3 DSS Pseudo-Random Number Generation | ||||
| Appendix 3 of the NIST Digital Signature Standard [DSS] provides a | ||||
| method of producing a sequence of pseudo-random 160 bit quantities | ||||
| for use as private keys or the like. This has been modified by Change | ||||
| Notice 1 [DSS CN1] to produce the following algorithm for generating | ||||
| general purpose pseudorandom numbers: | ||||
| t = 0x 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0 | ||||
| XKEY = initial seed | ||||
| 0 | ||||
| For j = 0 to ... | ||||
| XVAL = ( XKEY + optional user input ) (Mod 2^512) | ||||
| j | ||||
| X = G( t, XVAL ) | ||||
| j | ||||
| XKEY = ( 1 + XKEY + X ) (Mod 2^512) | ||||
| j+1 j j | ||||
| The quantities X thus produced are the pseudo-random sequence of 160 | ||||
| bit values. Two functions can be used for "G" above. Each produces | ||||
| a 160-bit value and takes two arguments, the first argument a 160-bit | ||||
| value and the second a 512 bit value. | ||||
| The first is based on SHA-1 and works by setting the 5 linking | ||||
| variables, denoted H with subscripts in the SHA-1 specification, to | ||||
| the first argument divided into fifths. Then steps (a) through (e) of | ||||
| section 7 of the NIST SHA-1 specification are run over the second | ||||
| argument as if it were a 512-bit data block. The values of the | ||||
| linking variable after those steps are then concatenated to produce | ||||
| the output of G. [SHA*] | ||||
| As an alternative second method, NIST also defined an alternate G | ||||
| function based on multiple applications of the DES encryption | ||||
| function [DSS]. | ||||
| 7.4 X9.82 Pseudo-Random Number Generation | ||||
| The National Institute for Standards and Technology (NIST) and the | ||||
| American National Standards Institutes (ANSI) X9F1 committee are in | ||||
| the final stages of creating a standard for random number generation | ||||
| covering both true randomness generators and pseudo-random number | ||||
| generators. It includes a number of pseudo-random number generators | ||||
| for use with AES and other block ciphers. It also includes random | ||||
| number generators based on hash functions and the arithmetic of | ||||
| elliptic curves [X9.82]. | ||||
| 7.5 The /dev/random Device | ||||
| Several versions of the UNIX operating system provides a kernel- | Several versions of the UNIX operating system provide a kernel- | |||
| resident random number generator. In some cases, these generators | resident random number generator. In some cases, these generators | |||
| makes use of events captured by the Kernel during normal system | make use of events captured by the Kernel during normal system | |||
| operation. | operation. | |||
| For example, on some versions of Linux, the generator consists of a | For example, on some versions of Linux, the generator consists of a | |||
| random pool of 512 bytes represented as 128 words of 4-bytes each. | random pool of 512 bytes represented as 128 words of 4-bytes each. | |||
| When an event occurs, such as a disk drive interrupt, the time of the | When an event occurs, 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 | event is XORed into the pool and the pool is stirred via a primitive | |||
| polynomial of degree 128. The pool itself is treated as a ring | polynomial of degree 128. The pool itself is treated as a ring | |||
| buffer, with new data being XORed (after stirring with the | buffer, with new data being XORed (after stirring with the | |||
| polynomial) across the entire pool. | polynomial) across the entire 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 as listed below. | Input events come from several sources as listed below. | |||
| Unfortunately, for server machines without human operators, the first | Unfortunately, for server machines without human operators, the first | |||
| and third are not available and entropy may be added very slowly in | and third are not available and entropy may be added slowly in that | |||
| that case. | case. | |||
| 1. Keyboard interrupts. The time of the interrupt as well as the scan | 1. Keyboard interrupts. The time of the interrupt as well as the scan | |||
| code are added to the pool. This in effect adds entropy from the | code are added to the pool. This in effect adds entropy from the | |||
| human operator by measuring inter-keystroke arrival times. | human operator by measuring inter-keystroke arrival times. | |||
| 2. Disk completion and other interrupts. A system being used by a | 2. Disk completion and other interrupts. A system being used by a | |||
| person will likely have a hard to predict pattern of disk | person will likely have a hard to predict pattern of disk | |||
| accesses. (But not all disk drivers support capturing this timing | accesses. (But not all disk drivers support capturing this timing | |||
| information with sufficient accuracy to be useful.) | information with sufficient accuracy to be useful.) | |||
| 3. Mouse motion. The timing as well as mouse position is added in. | 3. Mouse motion. The timing as well as mouse position is added in. | |||
| When random bytes are required, the pool is hashed with SHA-1 [SHA*] | When random bytes are required, the pool is hashed with SHA-1 [SHA*] | |||
| to yield the returned bytes of randomness. If more bytes are required | to yield the returned bytes of randomness. If more bytes are required | |||
| than the output of SHA-1 (20 bytes), then the hashed output is | than the output of SHA-1 (20 bytes), then the hashed output is | |||
| stirred back into the pool and a new hash performed to obtain the | stirred back into the pool and a new hash performed to obtain the | |||
| next 20 bytes. As bytes are removed from the pool, the estimate of | next 20 bytes. As bytes are removed from the pool, the estimate of | |||
| entropy is similarly decremented. | entropy is similarly decremented. | |||
| To ensure a reasonable random pool upon system startup, the standard | To ensure a reasonable random pool upon system startup, the standard | |||
| startup scripts (and shutdown scripts) save the pool to a disk file | startup and shutdown scripts save the pool to a disk file at shutdown | |||
| at shutdown and read this file at system startup. | and read this file at system startup. | |||
| 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 from such a | available via /dev/random. Random data obtained from such a | |||
| /dev/random device is suitable for key generation for long term keys, | /dev/random device is suitable for key generation for long term keys, | |||
| if enough random bits are in the pool or are added in a reasonable | if enough random bits are in the pool or are added in a reasonable | |||
| amount of time. | amount of time. | |||
| /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 may | when the entropy estimate for the random pool drops to zero. This may | |||
| be adequate for session keys or for other key generation tasks where | be adequate for session keys or for other key generation tasks where | |||
| blocking while waiting for more random bits is not acceptable. The | blocking while waiting for more random bits is not acceptable. The | |||
| risk of continuing to take data even when the pool's entropy estimate | risk of continuing to take data even when the pool's entropy | |||
| is small in that past output may be computable from current output | estimate is small in that past output may be computable from current | |||
| provided an attacker can reverse SHA-1. Given that SHA-1 is designed | output provided an attacker can reverse SHA-1. Given that SHA-1 is | |||
| to be non-invertible, this is a reasonable risk. | designed to be non-invertible, this is a reasonable risk. | |||
| To obtain random numbers under Linux, Solaris, or other UNIX systems | To obtain random numbers under Linux, Solaris, or other UNIX systems | |||
| equipped with code as described above, all an application needs to do | equipped with code as described above, 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 was based | (The Linux Random device was written by Theodore Ts'o. It was 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.6 Windows CryptGenRandom | 7.1.3 Windows CryptGenRandom | |||
| Microsoft's recommendation to users of the widely deployed Windows | Microsoft's recommendation to users of the widely deployed Windows | |||
| operating system is generally to use the CryptGenRandom pseudo-random | operating system is generally to use the CryptGenRandom pseudo-random | |||
| number generation call with the CryptAPI cryptographic service | number generation call with the CryptAPI cryptographic service | |||
| provider. This takes a handle to a cryptographic service provider | provider. This takes a handle to a cryptographic service provider | |||
| library, a pointer to a buffer by which the caller can provide | library, a pointer to a buffer by which the caller can provide | |||
| entropy and into which the generated pseudo-randomness is returned, | entropy and into which the generated pseudo-randomness is returned, | |||
| and an indication of how many octets of randomness are desired. | and an indication of how many octets of randomness are desired. | |||
| The Windows CryptAPI cryptographic service provider stores a seed | The Windows CryptAPI cryptographic service provider stores a seed | |||
| skipping to change at page 37, line 5 ¶ | skipping to change at page 36, line 5 ¶ | |||
| hashed user environment block. This data is all feed to SHA-1 and the | hashed user environment block. This data is all feed to SHA-1 and the | |||
| output used to seed an RC4 key stream. That key stream is used to | output used to seed an RC4 key stream. That key stream is used to | |||
| produce the pseudo-random data requested and to update the user's | produce the pseudo-random data requested and to update the user's | |||
| seed state variable. | seed state variable. | |||
| Users of Windows ".NET" will probably find it easier to use the | Users of Windows ".NET" will probably find it easier to use the | |||
| RNGCryptoServiceProvider.GetBytes method interface. | RNGCryptoServiceProvider.GetBytes method interface. | |||
| For further information, see [WSC]. | For further information, see [WSC]. | |||
| 7.2 Generators Assuming a Source of Entropy | ||||
| The pseudo-random number generators described in the following three | ||||
| sections all assume that a seed value with sufficient entropy is | ||||
| provided to them. They then generate a strong sequence (see Section | ||||
| 6.2) from that seed. | ||||
| 7.2.1 X9.82 Pseudo-Random Number Generation | ||||
| The ANSI X9F1 committee is in the final stages of creating a standard | ||||
| for random number generation covering both true randomness generators | ||||
| and pseudo-random number generators. It includes a number of pseudo- | ||||
| random number generators based on hash functions one of which will | ||||
| probably be based on HMAC SHA hash constructs [HMAC]. The draft | ||||
| version of this generated is as described below omitting a number of | ||||
| optional features [X9.82]. | ||||
| In the description in the subsections below, the HMAC hash construct | ||||
| is simply referred to as HMAC but, of course, in an particular use, a | ||||
| particular standard SHA function must be selected. Generally | ||||
| speaking, if the strength of the pseudo-random values to be generated | ||||
| is to be N bits, the SHA function chosen must be one generating N or | ||||
| more bits of output and a source of at least N bits of input entropy | ||||
| will be required. The same hash function must be used throughout an | ||||
| instantiation of this generator. | ||||
| 7,2.1.1 Notation | ||||
| In the following sections the notation give below is used: | ||||
| hash_length is the output size of the underlying hash function in | ||||
| use. | ||||
| input_entropy is the input bit string that provides entropy to the | ||||
| generator. | ||||
| K is a bit string of size hash_length that is part of the state of | ||||
| the generator and is updated at least once each time random | ||||
| bits are generated. | ||||
| V is a bit string of size hash_length and is part of the state of | ||||
| the generator which is updated each time hash_length bits of | ||||
| output are generated. | ||||
| | represents concatenation | ||||
| 7.1.2.2 Initializing the Generator | ||||
| Set V to all zero bytes except that the low order bit of each byte is | ||||
| set to one. | ||||
| Set K to all zero bytes. | ||||
| K = HMAC ( K, V | 0x00 | input_entropy ) | ||||
| V = HMAC ( K, V ) | ||||
| K = HMAC ( K, V | 0x01 | input_entropy ) | ||||
| V = HMAC ( K, V ) | ||||
| Note: all SHA algorithms produce an integral number of bytes of the | ||||
| length of K and V will be an integral number of bytes. | ||||
| 7.1.2.5 Generating Random Bits | ||||
| When output is called for simply set | ||||
| V = HMAC ( K, V ) | ||||
| and use leading bits from V. If more bits are needed than the length | ||||
| of V, set "temp" to a null bit string and then repeatedly perform | ||||
| V = HMAC ( K, V ) | ||||
| temp = temp | V | ||||
| stopping as soon a temp is equal to or longer than the number of | ||||
| random bits called for and use the called for number of leading bits | ||||
| from temp. The definition of the algorithm prohibits calling from | ||||
| more than 2**35 bits. | ||||
| 7.2.2 X9.17 Key Generation | ||||
| The American National Standards Institute has specified a method for | ||||
| generating a sequence of keys as follows [X9.17]: | ||||
| s is the initial 64 bit seed | ||||
| 0 | ||||
| g is the sequence of generated 64 bit key quantities | ||||
| n | ||||
| k is a random key reserved for generating this key sequence | ||||
| t is the time at which a key is generated to as fine a resolution | ||||
| as is available (up to 64 bits). | ||||
| DES ( K, Q ) is the DES encryption of quantity Q with key K | ||||
| g = DES ( k, DES ( k, t ) .xor. s ) | ||||
| n n | ||||
| s = DES ( k, DES ( k, t ) .xor. g ) | ||||
| n+1 n | ||||
| If g sub n is to be used as a DES key, then every eighth bit should | ||||
| be adjusted for parity for that use but the entire 64 bit unmodified | ||||
| g should be used in calculating the next s. | ||||
| 7.2.3 DSS Pseudo-Random Number Generation | ||||
| Appendix 3 of the NIST Digital Signature Standard [DSS] provides a | ||||
| method of producing a sequence of pseudo-random 160 bit quantities | ||||
| for use as private keys or the like. This has been modified by Change | ||||
| Notice 1 [DSS CN1] to produce the following algorithm for generating | ||||
| general purpose pseudorandom numbers: | ||||
| t = 0x 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0 | ||||
| XKEY = initial seed | ||||
| 0 | ||||
| For j = 0 to ... | ||||
| XVAL = ( XKEY + optional user input ) (Mod 2^512) | ||||
| j | ||||
| X = G( t, XVAL ) | ||||
| j | ||||
| XKEY = ( 1 + XKEY + X ) (Mod 2^512) | ||||
| j+1 j j | ||||
| The quantities X thus produced are the pseudo-random sequence of 160 | ||||
| bit values. Two functions can be used for "G" above. Each produces | ||||
| a 160-bit value and takes two arguments, the first argument a 160-bit | ||||
| value and the second a 512 bit value. | ||||
| The first is based on SHA-1 and works by setting the 5 linking | ||||
| variables, denoted H with subscripts in the SHA-1 specification, to | ||||
| the first argument divided into fifths. Then steps (a) through (e) of | ||||
| section 7 of the NIST SHA-1 specification are run over the second | ||||
| argument as if it were a 512-bit data block. The values of the | ||||
| linking variable after those steps are then concatenated to produce | ||||
| the output of G. [SHA*] | ||||
| As an alternative second method, NIST also defined an alternate G | ||||
| function based on multiple applications of the DES encryption | ||||
| function [DSS]. | ||||
| 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 passwords | randomness for security. The first is for moderate security passwords | |||
| while the second assumes a need for a very high security | while the second assumes a need for a very high security | |||
| cryptographic key. | cryptographic key. | |||
| In addition [ORMAN] and [RSA BULL13] provide information on the | In addition [ORMAN] and [RSA BULL13] provide information on the | |||
| public key lengths that should be used for exchanging symmetric keys. | public key lengths that should be used for exchanging symmetric keys. | |||
| skipping to change at page 38, line 49 ¶ | skipping to change at page 41, line 49 ¶ | |||
| could break the key in 2 weeks (on average they need try only half | could break the key in 2 weeks (on average they need try only half | |||
| the keys). | the keys). | |||
| These questions are considered in detail in "Minimal Key Lengths for | These questions are considered in detail in "Minimal Key Lengths for | |||
| Symmetric Ciphers to Provide Adequate Commercial Security: A Report | Symmetric Ciphers to Provide Adequate Commercial Security: A Report | |||
| by an Ad Hoc Group of Cryptographers and Computer Scientists" | by an Ad Hoc Group of Cryptographers and Computer Scientists" | |||
| [KeyStudy] which was sponsored by the Business Software Alliance. It | [KeyStudy] which was sponsored by the Business Software Alliance. It | |||
| concluded that a reasonable key length in 1995 for very high security | concluded that a reasonable key length in 1995 for very high security | |||
| is in the range of 75 to 90 bits and, since the cost of cryptography | is in the range of 75 to 90 bits and, since the cost of cryptography | |||
| does not vary much with they key size, recommends 90 bits. To update | does not vary 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 | these recommendations, just add 2/3 of a bit per year for Moore's | |||
| law [MOORE]. Thus, in the year 2004, this translates to a | ||||
| [MOORE]. Thus, in the year 2004, this translates to a determination | determination that a reasonable key length is in the 81 to 96 bit | |||
| that a reasonable key length is in the 81 to 96 bit range. In fact, | range. In fact, today, it is increasingly common to use keys longer | |||
| today, it is increasingly common to use keys longer than 96 bits, | than 96 bits, such as 128-bit (or longer) keys with AES and keys with | |||
| such as 128-bit (or longer) keys with AES and keys with effective | effective lengths of 112-bits using triple-DES. | |||
| lengths of 112-bits using triple-DES. | ||||
| 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 attack, | of the encryption algorithm allows it. (In a known plain text attack, | |||
| the adversary knows all or part of the messages being encrypted, | the adversary knows all or part of the messages being encrypted, | |||
| possibly some standard header or trailer fields. In a chosen plain | possibly some standard header or trailer fields. In a chosen plain | |||
| text attack, the adversary can force some chosen plain text to be | text attack, the adversary can force some chosen plain text to be | |||
| encrypted, possibly by "leaking" an exciting text that would then be | encrypted, possibly by "leaking" an exciting text that would then be | |||
| skipping to change at page 41, line 10 ¶ | skipping to change at page 44, line 10 ¶ | |||
| bit key size derived above. | bit key size derived above. | |||
| For further examples of conservative design principles see | For further examples of conservative design principles see | |||
| [FERGUSON]. | [FERGUSON]. | |||
| 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. | |||
| Hardware techniques to produce such randomness would be relatively | Hardware techniques to produce the needed entropy would be relatively | |||
| simple. In particular, the volume and quality would not need to be | simple. In particular, the volume and quality would not need to be | |||
| high and existing computer hardware, such as audio input or disk | high and existing computer hardware, such as audio input or disk | |||
| drives, can be used. | drives, can be used. | |||
| Widely available computational techniques are available to process | Widely available computational techniques are available to process | |||
| low quality random quantities from multiple sources or a larger | low quality random quantities from multiple sources or a larger | |||
| quantity of such low quality input from one source and produce a | quantity of such low quality input from one source and produce a | |||
| smaller quantity of higher quality keying material. In the absence of | smaller quantity of higher quality keying material. In the absence of | |||
| hardware sources of randomness, a variety of user and software | hardware sources of randomness, a variety of user and software | |||
| sources can frequently, with care, be used instead; however, most | sources can frequently, with care, be used instead; however, most | |||
| skipping to change at page 42, line 14 ¶ | skipping to change at page 45, line 14 ¶ | |||
| 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, initialization vectors, sequence numbers, and | cryptographic keys, initialization vectors, sequence numbers, and | |||
| similar security uses. | similar security uses. | |||
| 11. Copyright and Disclaimer | 11. Copyright and Disclaimer | |||
| Copyright (C) The Internet Society 2004. This document is subject to | Copyright (C) The Internet Society 2005. This document is subject to | |||
| the rights, licenses and restrictions contained in BCP 78 and except | the rights, licenses and restrictions contained in BCP 78 and except | |||
| as set forth therein, the authors retain all their rights. | as set forth therein, the authors retain all their rights. | |||
| This document and the information contained herein are provided on an | This document and the information contained herein are provided on an | |||
| "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS | "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS | |||
| OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET | OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET | |||
| ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, | ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, | |||
| INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE | INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE | |||
| INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED | INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED | |||
| WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. | WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. | |||
| 12. Appendix A: Changes from RFC 1750 | 12. Appendix A: Changes from RFC 1750 | |||
| 1. Additional acknowledgements have been added. | 1. Additional acknowledgements have been added. | |||
| 2. Insertion of section 5.2.4 on de-skewing with S-boxes. | 2. Insertion of section 5.3 on mixing with S-boxes. | |||
| 3. Addition of section 5.4 on Ring Oscillator randomness sources. | 3. Addition of section 3.3 on Ring Oscillator randomness sources. | |||
| 4. AES and the members of the SHA series producing more than 160 | 4. AES and the members of the SHA series producing more than 160 | |||
| bits have been added. Use of AES has been emphasized and the use | bits have been added. Use of AES has been emphasized and the use | |||
| of DES de-emphasized. | of DES de-emphasized. | |||
| 5. Addition of section 6.3.3 on entropy pool techniques. | 5. Addition of section 6.3 on entropy pool techniques. | |||
| 6. Addition of section 7.3 on the pseudo-random number generation | 6. Addition of section 7.2.3 on the pseudo-random number generation | |||
| techniques given in FIPS 186-2 (with Change Notice 1), 7.4 on | techniques given in FIPS 186-2 (with Change Notice 1), 7.2.1 on | |||
| those given in X9.82, section 7.5 on the random number generation | those given in X9.82, section 7.1.2 on the random number | |||
| techniques of the /dev/random device in Linux and other UNIX | generation techniques of the /dev/random device in Linux and | |||
| systems, and section 7.6 on random number generation techniques | other UNIX systems, and section 7.1.3 on random number generation | |||
| in the Windows operating system. | techniques in the Windows operating system. | |||
| 7. Addition of references to the "Minimal Key Lengths for Symmetric | 7. Addition of references to the "Minimal Key Lengths for Symmetric | |||
| Ciphers to Provide Adequate Commercial Security" study published | Ciphers to Provide Adequate Commercial Security" study published | |||
| in January 1996 [KeyStudy]. | in January 1996 [KeyStudy] and to [RFC 1948]. | |||
| 8. Added caveats to using Diffie-Hellman as a mixing function. | 8. Added caveats to using Diffie-Hellman as a mixing function and, | |||
| because of those caveats and its computationally intensive | ||||
| nature, recommend against its use. | ||||
| 9. Addition of references to the [TURBID] paper and system. | 9. Addition of references to the X9.82 effort and the [TURBID] and | |||
| [NASLUND] papers. | ||||
| 10. Addition of discussion of min-entropy and Renyi entropy and | 10. Addition of discussion of min-entropy and Renyi entropy and | |||
| references to the [LUBY] book. | references to the [LUBY] book. | |||
| 11. Minor wording changes and reference updates. | 11. Major restructuring, minor wording changes, and a variety of | |||
| reference updates. | ||||
| 14. Informative References | 13. Informative References | |||
| [AES] - "Specification of the Advanced Encryption Standard (AES)", | [AES] - "Specification of the Advanced Encryption Standard (AES)", | |||
| United States of America, US National Institute of Standards and | United States of America, US National Institute of Standards and | |||
| Technology, FIPS 197, November 2001. | Technology, FIPS 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. | |||
| [CRC] - "C.R.C. Standard Mathematical Tables", Chemical Rubber | [CRC] - "C.R.C. Standard Mathematical Tables", Chemical Rubber | |||
| Publishing Company. | Publishing Company. | |||
| [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 | |||
| Notes in Computer Science #839, 1984, Don Davis, Ross Ihaka, and | Lecture Notes in Computer Science #839, 1984, Don Davis, Ross Ihaka, | |||
| Philip Fenstermacher. | and Philip Fenstermacher. | |||
| [DES] - "Data Encryption Standard", US National Institute of | [DES] - "Data Encryption Standard", US National Institute of | |||
| Standards and Technology, FIPS 46-3, October 1999. | Standards and Technology, FIPS 46-3, October 1999. | |||
| - "Data Encryption Algorithm", American National Standards | - "Data Encryption Algorithm", American National Standards | |||
| Institute, ANSI X3.92-1981. | Institute, ANSI X3.92-1981. | |||
| (See also FIPS 112, Password Usage, which includes FORTRAN | (See also FIPS 112, Password Usage, which includes FORTRAN | |||
| code for performing DES.) | code for performing DES.) | |||
| [D-H] - RFC 2631, "Diffie-Hellman Key Agreement Method", Eric | [D-H] - RFC 2631, "Diffie-Hellman Key Agreement Method", Eric | |||
| Rescrola, June 1999. | Rescrola, June 1999. | |||
| skipping to change at page 46, line 10 ¶ | skipping to change at page 49, line 10 ¶ | |||
| [MAIL PEM 3] - RFC 1423, "Privacy Enhancement for Internet | [MAIL PEM 3] - RFC 1423, "Privacy Enhancement for Internet | |||
| Electronic Mail: Part III: Algorithms, Modes, and Identifiers", D. | Electronic Mail: Part III: Algorithms, Modes, and Identifiers", D. | |||
| Balenson, 02/10/1993. | Balenson, 02/10/1993. | |||
| [MAIL PEM 4] - RFC 1424, "Privacy Enhancement for Internet | [MAIL PEM 4] - RFC 1424, "Privacy Enhancement for Internet | |||
| Electronic Mail: Part IV: Key Certification and Related Services", B. | Electronic Mail: Part IV: Key Certification and Related Services", B. | |||
| Kaliski, 02/10/1993. | Kaliski, 02/10/1993. | |||
| [MAIL PGP] | [MAIL PGP] | |||
| - RFC 2440, "OpenPGP Message Format", J. Callas, L. | - RFC 2440, "OpenPGP Message Format", J. Callas, L. | |||
| Donnerhacke, H. Finney, R. Thayer", November 1998. | Donnerhacke, H. Finney, R. Thayer, November 1998. | |||
| - RFC 3156, "MIME Security with OpenPGP" M. Elkins, D. Del | - RFC 3156, "MIME Security with OpenPGP" M. Elkins, D. Del | |||
| Torto, R. Levien, T. Roessler, August 2001. | Torto, R. Levien, T. Roessler, August 2001. | |||
| [MAIL S/MIME] - RFCs 2632 through 2634: | [MAIL S/MIME] - RFCs 2632 through 2634: | |||
| - RFC 2632, "S/MIME Version 3 Certificate Handling", B. | - RFC 2632, "S/MIME Version 3 Certificate Handling", B. | |||
| Ramsdell, Ed., June 1999. | Ramsdell, Ed., June 1999. | |||
| - RFC 2633, "S/MIME Version 3 Message Specification", B. | - RFC 2633, "S/MIME Version 3 Message Specification", B. | |||
| Ramsdell, Ed., June 1999. | Ramsdell, Ed., June 1999. | |||
| - RFC 2634, "Enhanced Security Services for S/MIME" P. | - RFC 2634, "Enhanced Security Services for S/MIME" P. | |||
| Hoffman, Ed., June 1999. | Hoffman, Ed., June 1999. | |||
| skipping to change at page 46, line 40 ¶ | skipping to change at page 49, line 40 ¶ | |||
| - "Data Encryption Algorithm - Modes of Operation", American | - "Data Encryption Algorithm - Modes of Operation", American | |||
| National Standards Institute, ANSI X3.106-1983. | National Standards Institute, ANSI X3.106-1983. | |||
| [MOORE] - Moore's Law: the exponential increase in the logic density | [MOORE] - Moore's Law: the exponential increase in the logic density | |||
| of silicon circuits. Originally formulated by Gordon Moore in 1964 as | of silicon circuits. Originally formulated by Gordon Moore in 1964 as | |||
| a doubling every year starting in 1962, in the late 1970s the rate | a doubling every year starting in 1962, in the late 1970s the rate | |||
| fell to a doubling every 18 months and has remained there through the | fell to a doubling every 18 months and has remained there through the | |||
| date of this document. See "The New Hacker's Dictionary", Third | date of this document. See "The New Hacker's Dictionary", Third | |||
| Edition, MIT Press, ISBN 0-262-18178-9, Eric S. Raymond, 1996. | Edition, MIT Press, ISBN 0-262-18178-9, Eric S. Raymond, 1996. | |||
| [NASLUND] - "Extraction of Optimally Unbiased Bits from a Biased | ||||
| Source", M. Naslund and A. Russell, IEEE Transactions on Information | ||||
| Theory. 46(3), May 2000. | ||||
| <http://www.engr.uconn.edu/~acr/Papers/biasIEEEjour.ps> | ||||
| [ORMAN] - "Determining Strengths For Public Keys Used For Exchanging | [ORMAN] - "Determining Strengths For Public Keys Used For Exchanging | |||
| Symmetric Keys", RFC 3766, Hilarie Orman, Paul Hoffman, April 2004. | Symmetric Keys", RFC 3766, Hilarie Orman, Paul Hoffman, April 2004. | |||
| [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. | |||
| [RFC 1948] - "Defending Against Sequence Number Attacks", S. | ||||
| Bellovin, May 1986. | ||||
| [RSA BULL1] - "Suggestions for Random Number Generation in Software", | [RSA BULL1] - "Suggestions for Random Number Generation in Software", | |||
| RSA Laboratories Bulletin #1, January 1996. | RSA Laboratories Bulletin #1, January 1996. | |||
| [RSA BULL13] - "A Cost-Based Security Analysis of Symmetric and | [RSA BULL13] - "A Cost-Based Security Analysis of Symmetric and | |||
| Asymmetric Key Lengths", RSA Laboratories Bulletin #13, Robert | Asymmetric Key Lengths", RSA Laboratories Bulletin #13, Robert | |||
| Silverman, April 2000 (revised November 2001). | Silverman, April 2000 (revised November 2001). | |||
| [SBOX1] - "Practical s-box design", S. Mister, C. Adams, Selected | [SBOX1] - "Practical s-box design", S. Mister, C. Adams, Selected | |||
| Areas in Cryptography, 1996. | Areas in Cryptography, 1996. | |||
| skipping to change at page 47, line 44 ¶ | skipping to change at page 50, line 52 ¶ | |||
| [TURBID] - "High Entropy Symbol Generator", John S. Denker, | [TURBID] - "High Entropy Symbol Generator", John S. Denker, | |||
| <http://www.av8n.com/turbid/paper/turbid.htm>, 2003. | <http://www.av8n.com/turbid/paper/turbid.htm>, 2003. | |||
| [USENET] - RFC 977, "Network News Transfer Protocol", B. Kantor, P. | [USENET] - RFC 977, "Network News Transfer Protocol", B. Kantor, P. | |||
| Lapsley, February 1986. | Lapsley, February 1986. | |||
| - RFC 2980, "Common NNTP Extensions", S. Barber, October | - RFC 2980, "Common NNTP Extensions", S. Barber, October | |||
| 2000. | 2000. | |||
| [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, | |||
| J. von Neumann. | 1963, J. von Neumann. | |||
| [WSC] - "Writing Secure Code, Second Edition", Michael Howard, David. | [WSC] - "Writing Secure Code, Second Edition", Michael Howard, David. | |||
| C. LeBlanc, Microsoft Press, ISBN 0735617228, December 2002. | C. LeBlanc, Microsoft Press, ISBN 0735617228, December 2002. | |||
| [X9.17] - "American National Standard for Financial Institution Key | [X9.17] - "American National Standard for Financial Institution Key | |||
| Management (Wholesale)", American Bankers Association, 1985. | Management (Wholesale)", American Bankers Association, 1985. | |||
| [X9.82] - "Random Number Generation", American National Standards | [X9.82] - "Random Number Generation", American National Standards | |||
| Institute, ANSI X9F1, work in progress. | Institute, ANSI X9F1, work in progress. | |||
| Part 1 - Overview and General Principles. | ||||
| Part 2 - Non-Deterministic Random Bit Generators | ||||
| Part 3 - Deterministic Random Bit Generators | ||||
| Author's Addresses | Author's 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-786-7554 (w) | Telephone: +1 508-786-7554 (w) | |||
| +1 508-634-2066 (h) | +1 508-634-2066 (h) | |||
| skipping to change at page 48, line 30 ¶ | skipping to change at page 52, line 30 ¶ | |||
| 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-09.txt. | This is file draft-eastlake-randomness2-10.txt. | |||
| It expires April 2005. | It expires July 2005. | |||
| End of changes. 137 change blocks. | ||||
| 624 lines changed or deleted | 765 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/ | ||||