Talk:Cryptographically secure pseudorandom number generator

One-time pads and CSPRNG

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!

Consequently

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

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. 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

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?

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.

and

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)

The key is absolutely a part of the state of the PRNG, not just the counter. I have added a dubious tag, since the article is inconsistent. Darco (talk) 17:54, 10 April 2020 (UTC)

Also, strictly speaking, it doesn't satisfy the next-bit test, either. For example, if the previous block_size*2-1 bits are 1, then the probability that the next bit will also be 1 is 0%. Darco (talk) 18:01, 10 April 2020 (UTC)

i think the article is two minded about csprngs. in reality there is the formal definition and there are real world implementations that only partially satisfy the requirements. the formal part of the article fails to mention this, but some of the practical examples violate strict requirements. there are two ways out of this: either we need to widen the definition to contain both ideal csprngs and "wild" csprngs, or clearly explain in the examples section that these implementations fail to satisfy all requirements, but used anyway for practical reasons. i personally think ideal csprngs and practical csprngs would fit nicely in one article, only the distinction must be made explicit and clear. Krisztián Pintér (talk) 10:07, 12 April 2020 (UTC)

The article tries to explain the CTR_DRBG construct (per NIST terminology), but glosses over the details, thus the confusion. The counter (CTR) mode is only used to "generate" a single random number (say, 4 invocations with a 128-bit block for total of 512 bits). After that, an "update" is performed (also using the CTR mode) that regenerates both the key and the counter value. As a result, if Eve gets hold of the new state, she will have to reverse the block encryption to get the previous values, which is assumed to be impossible. So (1) the text as-is is correct (2) It can be improved by adding the details (for example, per NIST SP 800-90A). And yes, key is very much part of the state here. Dimawik (talk) 23:25, 30 August 2023 (UTC)

I have replaced the confusing text (also incorrect in a case of using the streaming cipher) with short sentences pointing to NIST/ANSI constructs that are actually used in practice. This text can be easily expanded based on, say, SP 800-90Ar1. Dimawik (talk) 23:47, 30 August 2023 (UTC)

The key is not considered part of the state. It is part of the secret. No cryptographic scheme survives its keys/seeds/secret being discovered.

The state is that which can potentially be tractably discernible from external context. For example, if used as a stream cipher, a block cipher CPRNG in counter mode can have its count discovered if the number of bits encrypted is known, or in output feedback mode can have its last block discovered because its plaintext is known.

I'm not sure I follow regarding it not passing the next-bit test. Note that it only has to resist the next-bit test for a polynomial time adversary. Failing the test if the adversary has access to e.g. output length exponential in the block size is expected. 47.203.176.153 (talk) 09:12, 26 August 2023 (UTC)

Key here is a part of the state, see my reply above. Dimawik (talk) 23:26, 30 August 2023 (UTC)

I am almost certain the construction being described was not CTR_DRBG but rather the counter mode described by most introductory cryptography sources (e.g. https://joyofcryptography.com/pdf/chap6.pdf, construction 6.2) which in particular assume the key is secret and do not have any forward secrecy assurances if the key is compromised. In any case, in lieu of a more detailed account of the concerns with this construction motivating the design of CTR_DRBG, reference to CTR_DRBG is an improvement. 47.203.176.153 (talk) 10:34, 11 September 2023 (UTC)

I absolutely agree with you: the original text was describing an approach that used a pure CTR mode as a PRNG. However, the article is about a practical device that is both complex and critical for the security. In such a situation trust is of utmost importance, this trust more or less requires a validation by an independent party. As of this writing, CTR_DRBG will pass such validation, while the simple CTR construct will not and thus is not state-of-the-art. Therefore, the simple CTR approach belongs in the History section (if there are reviews pointing to its previous use) or should not be mentioned at all (my position). There are thousands of possible PRNG designs, almost all of them are not suitable for the cryptographic applications (as an obvious deficiency of the pure CTR construct I would point to its great susceptibility to the side-channel attack). Dimawik (talk) 17:11, 11 September 2023 (UTC)

State Compromise Extensions

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 76.181.226.94 (talk) 16:02, 12 February 2012 (UTC)

CSPRNG is a practical device. Design hypothesized here will not pass any modern validations and thus cannot be truly considered a CSPRNG. Dimawik (talk) 17:14, 11 September 2023 (UTC)

but this isn't pseudo...

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"

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.) 71.242.7.208 (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)

CSPRG vs. CSPRNG vs. CSPRBG

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)

/dev/random

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)

Hyphenation

Should there be a hyphen in Cryptographically-secure? — Preceding unsigned comment added by 198.208.251.22 (talk)

I believe not, most sources don't have a hyphen/dash there. -- intgr [talk] 07:46, 14 April 2015 (UTC)

CSPRNG libraries and implementations

It seems like this page should have a section discussing CSPRNG libraries and implementations. Or does that exist in a separate article? If so, does that article already exist? Risc64 (talk) 07:03, 30 December 2015 (UTC)

DUHK (Don't Use Hard-coded Keys) is a vulnerability that affects devices using the ANSI X9.31 Random Number Generator (RNG) in conjunction with a hard-coded seed key.

https://duhkattack.com/ 441ac5d1 (talk) 08:53, 24 October 2017 (UTC)

Multiple senses of CSPRNG

There are a few senses of CSPRNG at play here:

• An algorithm to turn a random seed into an infinite stream (AES-CTR, Blum-Blum-Shub, etc.). The first half of Definitions and the first 2/3 of Designs seem to talk about those.
• A design such as Yarrow or Fortuna. Unlike bare ciphers, these are designed to accept lots of entropy bits that are imperfectly random, to accept entropy at random times, and to do their best to minimize the scope of impact even if internal state is compromised (vs. an AES-CTR key leak obviously revealing all past/future random numbers).
• A concrete function like CryptGenRandom, arc4random, or I guess ANSI X9.17: these are backed by some design, whether Yarrow, Fortuna, or something the authors put together themselves, and also by some specific code for gathering and maybe estimating entropy.

The weird thing is no one really messed up in adding their piece, because "CSPRNG" is actually used to mean each of those things, but it seems helpful to call out the distinctions. And they really are distinct concepts. AES-CTR is not just the same kind of thing as Yarrow but weaker; the two actually take different kinds of input at different times. And the specific functions like CryptGenRandom involve security-critical things that are abstract/assumed in the Yarrow and Fortuna designs, like the entropy sources--an implementation can fail despite even if built on a solid design if the inputs are bad enough. — Preceding unsigned comment added by 76.103.246.130 (talk • contribs)

(1) "CS" here actually has a quite precise meaning and the simple AES-CTR does not meet the requirements. The first definition is not thus not "CS" and should not even be mentioned here. (2) I see no practical difference between an "algorithm" and "concrete function"; algorithms are always expressed in some language, and C/C++/C#, etc. are not special, just not always as readable as pseudocode. (3) The source of entropy is not part of "PRNG". Thus, there is essentially a single subject here: an algorithm that provides cryptographically secure random numbers when seeded with an unpredictable bit string. The existing text should simply be trimmed to delete the "simple" (and wrong) designs and possibly expanded to describe the actual CSPRNG algorithms (there are not too many of these). The "simple" approaches can only be listed in the "these are not CSPRNG" section, if a source for that statement can be found. --Dimawik (talk) 17:50, 31 August 2023 (UTC)

"Special designs"

What does "special" even mean in the name of the "special designs" section? It lists a bunch of generators that fall into the type described the cryptographic section, but also one that does not fall into either.

• "Designs based on cryptographic primitives" should include AES CTR DRBG, the two RC4 things (ISAAC, arc4random), and the two ChaCha20 things.
  • ANSI X9.17 probably also falls in the bucket. Yarrow and Fortuna use a hash function somewhere, so arguably they also count.
  • CryptGenRandom also counts as using SHA-1, if we follow the description and the "FIPS 186-2 appendix 3.1" reference. It would probably fall into the same bucket as Yarrow in how it mixes things for the seed.
• Well, and that's it! The only thing left is the one "linear-feedback shift register" (LFSR). That really doesn't fall into any of these buckets. That thing should be removed, in my opinion, because there is no claim of cryptographic security from the author. Just because something passes the statistical test doesn't mean someone can't predict the output.

At present we have a sentence that says "the last often introduces additional entropy when available". I don't believe "special-purpose" is the best word for describing this kind of difference. I think the categories from 76.103.246.130 also ties into this.

--Artoria2e5 🌉 10:59, 4 March 2024 (UTC)

So I decided to instead call them "practical" and changed the distinction from "mixes in entropy" to "handles the seeding for you". I think that works better, though maybe a better word can be found. Artoria2e5 🌉 11:59, 4 March 2024 (UTC)