See more Cryptographically secure pseudorandom number generator articles on AOD.

Powered by
TTSReader
Share this page on
Article provided by Wikipedia


( => ( => ( => Cryptographically secure pseudorandom number generator [pageid] => 182249 ) =>

A cryptographically secure pseudo-random number generator (CSPRNG) or cryptographic pseudo-random number generator (CPRNG)[1] is a "pseudo-random number generator (PRNG) with properties that make it suitable for use in "cryptography.

Many aspects of cryptography require "random numbers, for example:

The "quality" of the randomness required for these applications varies. For example, creating a "nonce in some "protocols needs only uniqueness. On the other hand, generation of a master "key requires a higher quality, such as more "entropy. And in the case of "one-time pads, the "information-theoretic guarantee of perfect secrecy only holds if the key material comes from a true random source with high entropy.

Ideally, the generation of random numbers in CSPRNGs uses entropy obtained from a high-quality source, generally the operating system's randomness API. However, unexpected correlations have been found in several such ostensibly independent processes. From an information-theoretic point of view, the amount of randomness, the entropy that can be generated, is equal to the entropy provided by the system. But sometimes, in practical situations, more random numbers are needed than there is entropy available. Also the processes to extract randomness from a running system are slow in actual practice. In such instances, a CSPRNG can sometimes be used. A CSPRNG can "stretch" the available entropy over more bits.

Contents

Requirements[edit]

The requirements of an ordinary PRNG are also satisfied by a cryptographically secure PRNG, but the reverse is not true. CSPRNG requirements fall into two groups: first, that they pass statistical randomness tests; and secondly, that they hold up well under serious attack, even when part of their initial or running state becomes available to an attacker.["citation needed]

Example: If the CSPRNG under consideration produces output by computing bits of "π in sequence, starting from some unknown point in the binary expansion, it may well satisfy the next-bit test and thus be statistically random, as π appears to be a random sequence. (This would be guaranteed if π is a "normal number, for example.) However, this algorithm is not cryptographically secure; an attacker who determines which bit of pi (i.e. the state of the algorithm) is currently in use will be able to calculate all preceding bits as well.

Most PRNGs are not suitable for use as CSPRNGs and will fail on both counts. First, while most PRNGs outputs appear random to assorted statistical tests, they do not resist determined reverse engineering. Specialized statistical tests may be found specially tuned to such a PRNG that shows the random numbers not to be truly random. Second, for most PRNGs, when their state has been revealed, all past random numbers can be retrodicted, allowing an attacker to read all past messages, as well as future ones.

CSPRNGs are designed explicitly to resist this type of "cryptanalysis.

Definitions[edit]

In the "asymptotic setting, a family of deterministic polynomial time computable functions for some polynomial p, is a pseudorandom number generator (PRG), if it stretches the length of its input ( for any k), and if its output is "computationally indistinguishable from true randomess, i.e. for any probabilistic polynomial time algorithm A, which outputs 1 or 0 as a distinguisher,

for some "negligible function .[4] (The notation means that x is chosen "uniformly at random from the set X.)

There is an equivalent characterization: For any function family , G is a PRG if and only if the next output bit of G cannot be predicted by a polynomial time algorithm.[5]

A forward-secure PRG with block length is a PRG , where the input string with length k is the current state at period i, and the output (, ) consists of the next state and the pseudorandom output block of period i, such that it withstands state compromise extensions in the following sense. If the initial state is chosen uniformly at random from , then for any i, the sequence must be computationally indistinguishable from , in which the are chosen uniformly at random from .[6]

Any PRG can be turned into a forward secure PRG with block length by splitting its output into the next state and the actual output. This is done by setting , in which and ; then G is a forward secure PRG with as the next state and as the pseudorandom output block of the current period.

Entropy extraction[edit]

Santha and Vazirani proved that several bit streams with weak randomness can be combined to produce a higher-quality quasi-random bit stream.[7] Even earlier, "John von Neumann proved that a "simple algorithm can remove a considerable amount of the bias in any bit stream[8] which should be applied to each bit stream before using any variation of the Santha–Vazirani design.

Designs[edit]

In the discussion below, CSPRNG designs are divided into three classes:

  1. those based on cryptographic primitives such as "ciphers and "cryptographic hashes,
  2. those based upon mathematical problems thought to be hard, and
  3. special-purpose designs.

The last often introduces additional entropy when available and, strictly speaking, are not "pure" pseudorandom number generators, as their output is not completely determined by their initial state. This addition can prevent attacks even if the initial state is compromised.

Designs based on cryptographic primitives[edit]

Number-theoretic designs[edit]

Special designs[edit]

There are a number of practical PRNGs that have been designed to be cryptographically secure, including

Obviously, the technique is easily generalized to any block cipher; "AES has been suggested (Young and Yung, op cit, sect 3.5.1).

Standards[edit]

Several CSPRNGs have been standardized. For example,

This withdrawn standard has four PRNGs. Two of them are uncontroversial and proven: CSPRNGs named Hash_DRBG[18] and HMAC_DRBG.[19]
The third PRNG in this standard, CTR_DRBG, is based on a "block cipher running in "counter mode. It has an uncontroversial design but has been proven to be weaker in terms of distinguishing attack, than the "security level of the underlying block cipher when the number of bits output from this PRNG is greater than two to the power of the underlying block cipher's block size in bits.[20]
When the maximum number of bits output from this PRNG is equal to the 2blocksize, the resulting output delivers the mathematically expected security level that the key size would be expected to generate, but the output is shown to not be indistinguishable from a true random number generator.[20] When the maximum number of bits output from this PRNG is less than it, the expected security level is delivered and the output appears to be indistinguishable from a true random number generator.[20]
It is noted in the next revision that claimed security strength for CTR_DRBG depends on limiting the total number of generate requests and the bits provided per generate request.
The fourth and final PRNG in this standard is named "Dual_EC_DRBG. It has been shown to not be cryptographically secure and is believed to have a "kleptographic NSA backdoor.[21]

A good reference is maintained by "NIST.

There are also standards for statistical testing of new CSPRNG designs:

NSA "kleptographic backdoor in the Dual_EC_DRBG PRNG[edit]

"The Guardian and "The New York Times have reported that the "National Security Agency (NSA) inserted a "backdoor into a "PRNG of "NIST SP 800-90A which allows the NSA to readily decrypt material that was encrypted with the aid of "Dual_EC_DRBG. Both papers report[22][23] that, as independent security experts long suspected,[24] the NSA has been introducing weaknesses into CSPRNG standard 800-90; this being confirmed for the first time by one of the top secret documents leaked to the Guardian by "Edward Snowden. The NSA worked covertly to get its own version of the NIST draft security standard approved for worldwide use in 2006. The leaked document states that "eventually, NSA became the sole editor." In spite of the known potential for a kleptographic backdoor and other known significant deficiencies with Dual_EC_DRBG, several companies such as "RSA Security continued using Dual_EC_DRBG until the backdoor was confirmed in 2013.[25] "RSA Security received a $10 million payment from the NSA to do so.[26]

Security flaws[edit]

DUHK attack[edit]

On October 23, 2017, " Matthew Green, a "cryptographer at "Johns Hopkins University released details[27] regarding an attack on WPA2 where hardware vendors use a hardcoded "seed key" for the ANSI X9.31 RNG algorithm in conjunction with the usage of the ANSI X9.31 Random Number Generator, "an attacker can brute-force encrypted data to discover the rest of the encryption parameters and deduce the master encryption key used to encrypt web sessions or VPN connections."[28]

References[edit]

  1. ^ "Huang, Andrew (2003). Hacking the Xbox: An Introduction to Reverse Engineering. No Starch Press Series. "No Starch Press. p. 111. "ISBN "9781593270292. Retrieved 2013-10-24. [...] the keystream generator [...] can be thought of as a cryptographic pseudo-random number generator (CPRNG). 
  2. ^ Katz, Jonathan; Lindell, Yehuda (2008). Introduction to Modern Cryptography. CRC press. p. 70. "ISBN "978-1584885511. 
  3. ^ "Andrew Chi-Chih Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982.
  4. ^ Goldreich, Oded (2001), Foundations of cryptography I: Basic Tools, Cambridge: Cambridge University Press, "ISBN "978-0-511-54689-1 , def 3.3.1.
  5. ^ Goldreich, Oded (2001), Foundations of cryptography I: Basic Tools, Cambridge: Cambridge University Press, "ISBN "978-0-511-54689-1 , Theorem 3.3.7.
  6. ^ Dodis, Yevgeniy, Lecture 5 Notes of Introduction to Cryptography (PDF), retrieved 3 January 2016 , def 4.
  7. ^ Miklos Santha, Umesh V. Vazirani (1984-10-24). "Generating quasi-random sequences from slightly-random sources" (PDF). Proceedings of the 25th IEEE Symposium on Foundations of Computer Science. "University of California. pp. 434–440. "ISBN "0-8186-0591-X. Retrieved 2006-11-29. 
  8. ^ "John von Neumann (1963-03-01). "Various techniques for use in connection with random digits". The Collected Works of John von Neumann. "Pergamon Press. pp. 768–770. "ISBN "0-08-009566-6. 
  9. ^ Adam Young, Moti Yung (2004-02-01). Malicious Cryptography: Exposing Cryptovirology. sect 3.2: "John Wiley & Sons. p. 416. "ISBN "978-0-7645-4975-5. 
  10. ^ CVS. CVS log of arc4random.c October 1, 2013
  11. ^ CVS. CVS log of arc4random.c November 16, 2014
  12. ^ Github. Github commit of random.c July 2, 2016
  13. ^ NIST. "A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications". NIST, Special Publication April 2010
  14. ^ A. Poorghanad, A. Sadr, A. Kashanipour" Generating High Quality Pseudo Random Number Using Evolutionary Methods", IEEE Congress on Computational Intelligence and Security, vol. 9, pp. 331-335 , May,2008 [1]
  15. ^ David Kleidermacher, Mike Kleidermacher. "Embedded Systems Security: Practical Methods for Safe and Secure Software and Systems Development". Elsevier, 2012. p. 256.
  16. ^ George Cox, Charles Dike, and DJ Johnston. "Intel’s Digital Random Number Generator (DRNG)". 2011.
  17. ^ Handbook of Applied Cryptography, "Alfred Menezes, "Paul van Oorschot, and "Scott Vanstone, CRC Press, 1996, Chapter 5 Pseudorandom Bits and Sequences (PDF)
  18. ^ Kan, Wilson (September 4, 2007). "Analysis of Underlying Assumptions in NIST DRBGs" (PDF). Retrieved November 19, 2016. 
  19. ^ Ye, Katherine Qinru (April 2016). "The Notorious PRG: Formal verification of the HMAC-DRBG pseudorandom number generator" (PDF). Retrieved November 19, 2016. 
  20. ^ a b c Campagna, Matthew J. (November 1, 2006). "Security Bounds for the NIST Codebook-based Deterministic Random Bit Generator" (PDF). Retrieved November 19, 2016. 
  21. ^ Perlroth, Nicole (September 10, 2013). "Government Announces Steps to Restore Confidence on Encryption Standards"Free access subject to limited trial, subscription normally required. The New York Times. Retrieved November 19, 2016. 
  22. ^ James Borger; Glenn Greenwald (6 September 2013). "Revealed: how US and UK spy agencies defeat internet privacy and security". The Guardian. The Guardian. Retrieved 7 September 2013. 
  23. ^ Nicole Perlroth (5 September 2013). "N.S.A. Able to Foil Basic Safeguards of Privacy on Web". The New York Times. Retrieved 7 September 2013. 
  24. ^ Bruce Schneier (15 November 2007). "Did NSA Put a Secret Backdoor in New Encryption Standard?". Wired. Retrieved 7 September 2013. 
  25. ^ Matthew Green. "RSA warns developers not to use RSA products". 
  26. ^ Joseph Menn (20 December 2013). "Exclusive: Secret contract tied NSA and security industry pioneer". Reuters. 
  27. ^ "Practical state recovery attacks against legacy RNG implementations" (PDF). duhkattack.com. 
  28. ^ "DUHK Crypto Attack Recovers Encryption Keys, Exposes VPN Connections". slashdot.org. Retrieved 25 October 2017. 

External links[edit]

) )