Talk:Cryptographically secure pseudorandom number generator

From Wikipedia, the free encyclopedia
Jump to: navigation, search
          This article is of interest to the following WikiProjects:
WikiProject Cryptography / Computer science  (Rated Start-class, Top-importance)
WikiProject icon This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the quality scale.
 Top  This article has been rated as Top-importance on the importance scale.
Taskforce icon
This article is supported by WikiProject Computer science (marked as Top-importance).
WikiProject Computer science (Rated Start-class, High-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 High  This article has been rated as High-importance on the project's importance scale.
WikiProject Computing (Rated Start-class)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.

One-time pads and CSPRNG[edit]

in One-time pad it is stated,

If the key is generated by a deterministic program then it is not actually random and should not be used in a one-time pad cipher. If so used, the method is called a stream cipher;...

which, i beliefe, is true!


Many aspects of cryptography require random numbers, for example:

   * One-time pads

as stated in this article is false.

Stream cipher might be the right here! --sig

Thanks for keeping an eye out for this sort of error. Certainly it is true that one-time pads is one of the applications in cryptography which require random numbers. However, I don't think the article is suggesting that a CSPRNG should be used for that application, but rather starting with a discourse about the use of randomness within cryptography in general. In fact, it explicitly says, "in the case of one-time pads, the information theoretic guarantees only hold if the random stream is obtained from a true random source.". — Matt 15:12, 13 Oct 2004 (UTC)

Special Types[edit]

I'm not sure if Hotbits counts as a "special type" or not - but if so it should be mentioned. It uses the unpredictability of radioactive decay to generate actual random numbers. I don't know if it can be said to be specifically designed for cryptography. Certainly, from a security perspective, you'd need the actual device in your secure network, and not access the numbers over the web. - Vedexent (talk) - 16:26, 18 November 2006 (UTC)

  • No, because it isn't pseudorandom; it is genuinely random. Of course, it may still fail to be cryptographically secure; true random number generators often fail the next bit test. Also, they generally aren't reproducible, which makes them useless for many applications. Ben Standeven 04:43, 3 February 2007 (UTC)

I am concerned to see that /dev/random is listed as if it were a Cryptographically secure pseudorandom number generator. The Billion bit test has found multiple uniformity flaws in a number of /dev/random implementations.[1] In fact, I have never found a /dev/random implementation that did not suffer from at least 1 uniformity flaw, except those /dev/random implementations that bypassed the standard /dev/random driver code and directly accessed a Cryptographically sound hardware source.

The sited page lists observed flaws in the FreeBSD 5.2.1, Solaris 8 patch 108528-18, Linux 2.4.21-20, OS X 10.3.5 implementations of /dev/random. Not listed are a number of more recent tests under RedHat Linux, OS X, FreeBSD, and others. Should /dev/random be listed among the Cryptographically secure pseudorandom number generators given this consistent track record of uniformity flaws? chongo (talk) 03:38, 3 July 2009 (UTC)

Longest page name[edit]

Does anyone know if this page has the longest article name in Wikipedia? (Not counting articles like lists, categories, etc.) — SheeEttin {T/C} 19:20, 1 June 2007 (UTC)

Definitely not. This title is a mere 54 characters long; I've came across this one which has 78 characters: Tarquin Fin-tim-lin-bin-whin-bim-lim-bus-stop-F'tang-F'tang-Olé-Biscuitbarrel. :) -- intgr #%@! 12:33, 2 June 2007 (UTC)

Does counter + block cipher satisfy the requirements given in the article?[edit]

From the article:

Every CSPRNG should withstand 'state compromise extensions'. In the event that part or all of its state has been revealed (or guessed correctly), it should be impossible to reconstruct the stream of random numbers prior to the revelation.


A secure block cipher can be converted into a CSPRNG by running it in counter mode. This is done by choosing a random key and encrypting a zero, then encrypting a 1, then encrypting a 2, etc. The counter can also be started at an arbitrary number other than zero.

What is the state here? The obvious answer seems to be the value of the counter, but I might have misunderstood something. If so, how does it satisfy the requirement that "it should be impossible to reconstruct the stream of random numbers prior to the revelation" in the event of state compromise? --SLi 12:53, 15 September 2007 (UTC)

I agree with you that this needs clarification. If you view that state as 'counter + key' than it is obviously not resistant against a state compromise. If you view the state as just the counter, then it might well be. In any case, it needs a citation. Sander123 08:38, 17 September 2007 (UTC)

State Compromise Extensions[edit]

Question, could "Every CSPRNG should withstand 'state compromise extensions'." be changed to "Every CSPRNG, for which the intended use is dynamic generation of pseudorandom bits, should withstand 'state compromise extensions'."? How is anyone going to compromise the state and "retrodict" the previous or future bits if the use is to a) seed a PRNG, b) generate and store the bits in a large binary file and c) shred, burn or otherwise destroy any evidence of the PRNG used in step a? — Preceding unsigned comment added by (talk) 16:02, 12 February 2012 (UTC)

but this isn't pseudo...[edit]

One design in this class is included in the ANSI X9.17 standard (Financial Institution Key Management (wholesale)), and has been adopted as a FIPS standard as well. It works as follows:

  • input: a 64 bit random seed s, and a DES EDE key k.

each time a random number is required:

  • using current date/time information D (in the maximum resolution available), compute I = DES_k (D)
  • output x=DES_k(I xor s), and update the seed s to DES_k(x xor I)
It has been suggested that this algorithm would be improved by using AES instead of DES (Young and Yung, op cit, sect 3.5.1)

But unless the times at which D is retrieved are chosen deterministically, that's not a pseudorandom number generator. For example, you can't retrieve the same sequence twice by starting from the same seed (unless you store all the values of D obtained during the first generation, that is). Essentially, you're just applying software whitening to the system clock. Thus I'm removing this example from the article. --A r m y 1 9 8 7  16:04, 11 July 2008 (UTC)

The 64 bits output at each stage is more than the entropy that can be read off of computer system clocks, even if they have microsecond resolution, which most don't. So, yes, this generator is not fully random.--agr (talk) 17:28, 11 July 2008 (UTC)
Yes, but it isn't fully pseudorandom, either. According to Pseudorandom number generator, "[t]he sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's state", a condition which the generator described above doesn't fulfill. (I assume that in that definition "relatively small" means "of size O(1)", whereas the generator above requires O(N) bits of input to produce N bits of output.) So, it isn't fully random, but it is "partly" random. (Imagine a generator which uses radioactive decay to produce random bits, but bit 0 has probability 0.999 and bit 1 has probability 0.001; its entropy is much less than the size of the output, but this doesn't mean it is a pseudorandom number generator, right?) --A r m y 1 9 8 7  10:29, 12 July 2008 (UTC)
Other designs mentioned, such as Yarrow, are not pure PRNGs either, yet the literature refers to them as PRNGs. I moved the X9.17 description to special designs and edited the text to make these distinctions clearer. --agr (talk) 10:55, 13 July 2008 (UTC)
Right. I hadn't even noticed the lead section, "When all the entropy we have is available before algorithm execution begins, we really have a stream cipher. However some crypto system designs allow for the addition of entropy during execution, in which case it is not a stream cipher equivalent and cannot be used as one. Stream cipher and CSPRNG design is thus closely related." --A r m y 1 9 8 7  09:22, 14 July 2008 (UTC)

Edit with summary: "see talk page"[edit]

I just edited the following original text:

The next-bit test is as follows: Given the first k bits of a random sequence, there is no polynomial-time algorithm that can predict the (k+1)th bit with probability of success higher than 50%.

I changed "higher" to "better". In fact, I could have changed it to "other". If an algorithm A(n) can predict the nth bit with a success rate r that is less than 50%, then an algorithm B(n) can be constructed (with trivial effort) to predict bits with a success rate greater than 50%, namely a rate of 1 - r. This is done simply by defining B(n) = NOT A(n). Therefore, if any prediction algorithm can be discovered that has a probability of success that is not exactly 50%, then one can be derived from it that has a probability greater than 50%. This leads to the corollary that any algorithm whose success rate is not exactly 50% is better than one with a success rate of exactly 50%.

Another way to look at this is that 50% success in predicting binary values represents absolutely no information. Anything else represents some information. (If we flip the 50%-likely-correct preditions, 0 to 1 and 1 to 0, we still have exactly the same probability of correctness: 50%. So the prediction algorithm has told us nothing.) The next-bit test requires that we get no information about the next bit of the random sequence from the current bit and a polynomial-time prediction algorithm. (I say this not from any knowledge of the test or of the definition of a CSPRNG, but merely by applying basic logic and mathematics to the information already I found present in the article.) (talk) 19:57, 5 June 2009 (UTC)

I believe this discussion is correct, although the current wording is probably clearer (either "higher" or "better" is fine). Dcoetzee 22:37, 5 June 2009 (UTC)


  1. ^ "BIllion Bit Test: Results and Conclusions", LavaRnd (LavaRnd), 22 Sep 2004, retrieved 3 July 2009 


I copy this from Talk:Pseudorandom number generator. I think the article should rather discuss cryptographically secure pseudo-random generators (CSPRGs) in general, and then introduce cryptographically secure pseudo-random number generators (CSPRNGs) and cryptographically secure pseudo-random bit generators (CSPRBGs) as sub-classes. Thoughts? Nageh (talk) 08:52, 21 May 2010 (UTC)

Is there even any significant difference between these terms? Can't you always construct one from the other? And please list sources. -- intgr [talk] 09:05, 21 May 2010 (UTC)
What do you mean by significant? It's a matter of definition. Yes, you can construct PRNGs from PRBGs and vice-versa, but that's not the point here. And hey, this is a talk page! I am trying to discuss an issue, so we do you want me to provide sources? (I have some, so if you insist.) Nageh (talk) 09:11, 21 May 2010 (UTC)
And if you look at Talk:Pseudorandom number generator, you'll see that I am asking for a reference where this is addressed and defined adequately. Why am I writing on a talk page, huh? Nageh (talk) 09:15, 21 May 2010 (UTC)


I don't understand this [1].

According to its page, /dev/random is true random. Whereas /dev/urandom is a PRNG sourced from /dev/random. Is that in dispute? WMC 23:18, 23 December 2010 (UTC)

Please consider my subsequent edit, in which I deleted the whole line. The one reason is that /dev/random is not a true PRG – "true" PRGs can only be generated from physical noise, radioactive decay, and the like. /dev/random emulates a true random PRG, and by measuring the entropy it attempts to construct a CSPRG. The second reason is that /dev/random is already mentioned in the first bullet on the Yarrow algorithm. The third is that /dev/urandom is not a CSPRG (which this article is about), but merely a PRG with inferior statistical properties (precisely because it does not block to wait for sufficient entropy). HTH, Nageh (talk) 09:37, 24 December 2010 (UTC)

Just for info, it seems from the documentation and from comments in the code that /dev/urandom is intended to still be cryptographically secure when there is insufficient new entropy for it to be truly random, in that it recycles old entropy by feeding SHA1 hashes into the pool - though I am prepared to believe if you say that such an algorithm isn't secure enough by today's standards. (By the way, I don't intend to edit the article again - I find it interesting but I think I've got out of my depth, so sorry if my earlier edit was wrong.) Scil100 (talk) 00:26, 25 December 2010 (UTC)

I will quote from man urandom:

A read from the /dev/urandom device will not block waiting for more entropy. As a result, if there is not sufficient entropy in the entropy pool, the returned values are theoretically vulnerable to a cryptographic attack on the algorithms used by the driver.

If it is (theoretically) vulnerable to a cryptographic attack it cannot be a cryptographically secure pseudo-random generator. It may still be suitable for some cryptographic applications like key derivation, for which strong CS properties may not be required. But then it is merely a PRG.
Using a cryptographic hash function (e.g., SHA) to extract randomness from old entropy is a good approach for minimizing the danger of an exploitable weakness in randomness. But it provides no strict guarantees: Cryptographic hash functions, though often treated so in theoretical analysis, are not regarded as having (strong) pseudo-random properties. For example, The Handbook explicitly regards hash-based pseudo-random generators as not being cryptographically secure. And when it comes to randomness extraction, HMAC and CMAC have been proven to be secure randomness extractors, a result that is not known for a simple cryptographic hash function. Nageh (talk) 12:09, 25 December 2010 (UTC)
Oh, and sorry, Scil100, for my strong words in one of my previous edit summaries. Nageh (talk) 12:12, 25 December 2010 (UTC)
Thanks. No worries. It was my fault entirely for trying to writing about stuff I don't know enough about. Scil100 (talk) 19:16, 27 December 2010 (UTC)
"If it is (theoretically) vulnerable to a cryptographic attack it cannot be a cryptographically secure pseudo-random generator"
I disagree. The term "CSPRNG" is used to classify PRNGs into ones that are intended for cryptography and ones whose output is merely statistically random. Even if a CSPRNG is broken, it's still a CSPRNG — like a broken cryptographic hash function is still a cryptographic hash function. /dev/urandom is certainly designed to be cryptographically strong.
That may be the current Wikipedia definition (from the lead sentence), but perhaps it is not correct. According the Handbook of Applied Cryptography chapter 5, definition 5.8 (and assuming that CSPRNG and "... Bit Generator" are equivalent for this purpose) a CSPRNG/CSPRBG is (very loosely) one whose output cannot be determined given all the previous outputs. Ie it is defined by the practical indeterminability of its output, NOT what purpose the output is intended for. Mitch Ames (talk) 08:48, 27 December 2010 (UTC)
And the collection of entropy is unrelated to a PRNG itself. Every PRNG requires entropy input in order to be useful. Every PRNG is insecure if the input is predictable to an attacker. The PRNG behind /dev/urandom is no different, it simply works with all the entropy it has.
I will also point out that the entropy estimator behind /dev/random has no academic basis or review; there is little evidence that it's helpful at all. If that entropy esimator fails, /dev/random is no better than /dev/urandom. However, in regular computers with real hard disks, there is always sufficient entropy available. The question is only about diskless embedded devices with no real entropy sources. -- intgr [talk] 22:38, 26 December 2010 (UTC)
It's not true that every PRNG requires entropy input in order to be useful. There are cases where it is useful to be able to easily regenerate the same set of pseudo-random data multiple times. In these cases I might deliberately seed the algorithm with the same start value. I've done this in the past when testing data encryption or hashing algorithms. I pass in some "random" data and record the output. Then I tweak the algorithm - eg optimising for speed or code size - then run it again with the same data and check that I get the same result. Of course I would run the tests with the sample data provided in the standards for the algorith, but sometimes it's good to see that the algorithm produces the same output (before and after optimization) for any arbitrary data. A deterministic PRNG is an easy way of creating relatively large amounts of reproducible data. Mitch Ames (talk) 09:02, 27 December 2010 (UTC)

Re Intgr: The term CSPRG is used to distinguish PRGs for which no polynomial-time distinguisher exists (or is unlikely to exist given some computational hardness assumption) from those PRGs for which a polynomial-time distinguisher does or may exist and which only has some desirable statistical properties. This does not mean that the output of PRGs is not suitable for specific cryptographic purposes, such as key derivation and salts. However, it is less desirable to use such "insecure" PRGs for key generation.

Note that there is no globally accepted definition for a PRG, and cryptographers and mathematicians often equate PRG := CSPRG.

Now regarding your observation that a broken cryptographic primitive is still called cryptographic. One reason is that it is odd to relabel a primitive after it is broken. The difference here is that it is said from the outset that for /dev/urandom a cryptographic attack may exist. If there is not even faith in that no practical distinguisher exists then it cannot be a CSPRG by definition. (But, it may still be a suitable PRG.)

Yes, collecting entropy is unrelated to a PRG. It was my impression from reading on man /dev/(u)random that the device emulates a "true" random generator in which case it has to continually collect new entropy. Now, insufficient entropy says nothing about its (in)security as a CSPRG, and I based my statement that /dev/urandom is not CS solely on the warning of a theoretical attack in the man page. Particularly, I still left /dev/random as a CSPRG in the article. (Yes, the situation may change if the entropy estimator gets broken, in which case both designs will not be CSPRGs.) Nageh (talk) 12:14, 27 December 2010 (UTC)

Different versions of Unix-like operating systems may implement /dev/random in different ways. I believe on OS-X uses yarrow and is the same as /dev/urandom. In any case, it would be helpful if this article made clear the different meanings of "Cryptographically secure pseudorandom number generator". --agr (talk) 16:27, 27 December 2010 (UTC)