Talk:Cryptographically secure pseudorandom number generator

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)

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)

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)

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)

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)

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)

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)