6
$\begingroup$

Wikipedia claims:

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 0, then encrypting a 1, then encrypting a 2, etc. The counter can also be started at an arbitrary number other than zero. Obviously, the period will be 2^n for an n-bit block cipher; equally obviously, the initial values (i.e., key and "plaintext") must not become known to an attacker, however good this CSPRNG construction might be. Otherwise, all security will be lost.

Here's a trivial counter-example:

Say I'm interested in generating psuedo-random 128 bit numbers. I'm using this method with a 128bit block cipher, but since the block cipher is giving out essentially a psuedo-random permutation of the counter - all the numbers I get are different! They are obviously not going to pass any basic randomness tests?!

Is this a mistake in Wikipedia (or just a misleading explanation?) or there's something I got wrong here?

If the answer is that it simply wouldn't work for values equal or larger than 128 bits, I would still doubt it would give out good quality output for 64 bits, since it has a very predictable pattern that the concatenation of any two consecutive 64 bit values is unique pattern that would never repeat (if that's a not a "real concern" mathematically, could you explain why? and what about 96 bit numbers?).

And if this is actually the case, are there any alternative examples of CSPRNG constructions that generate quality values for arbitrarily large amount of bits? are secure hashes any better (it seems reasonable I guess..)?

[Note: I've found this answer that very shortly addresses this issue but I didn't find it satisfying enough]

Update: Wikipedia seems to be updated now as a result of this discussion! Many thanks for @CodesInChaos who improved the article. This is useful knowledge for myself and many other people.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ The answer is basically the PRF/PRP switching lemma, which essentially says that a pseudorandom permutation is indistinguishable from a pseudorandom function unless we observe a collision for one of them. See also this question on cstheory.SE. $\endgroup$
    – Ilmari Karonen
    May 19, 2015 at 16:00
  • $\begingroup$ I wouldn't say that the original version was incorrect, it just didn't mention an important limitation. $\endgroup$
    – CodesInChaos
    May 19, 2015 at 16:06

1 Answer 1

Reset to default
7
$\begingroup$

For a random function you'd expect all outputs to be different if you generate fewer than $2^{n/2}$ blocks (birthday problem). Thus PRPs and PRFs are indistinguishable unless you observe about $2^{n/2}$, at which point you'd expect collisions using the PRF but not using the PRP.

For a 128 bit cipher this is a lot of data, so we generally don't care about this. But using a 64 bit cipher, you shouldn't encrypt more than a few gigabytes of data using the same key.

are there any alternative examples of CSPRNG constructions that generate quality values for arbitrarily large amount of bits?

In principle yes. I think using a variant of CTR mode which uses a secret IV and xors the counter+IV into the output might work. It'd get rid of the trivial "no duplicates" pattern, but it might be distinguishable in other ways.

128 bit blocks should be good enough as a stream cipher/CSPRNG. But if it's a bit too low for your taste (Generating $2^{64}$ blocks is feasible with sufficient effort), you can simply use larger blocks. Typically hash functions (like SHA-2), which want to avoid collisions, use 256 or 512 bit block ciphers.

I've changed the paragraph on wikipedia to

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 0, then encrypting a 1, then encrypting a 2, etc. The counter can also be started at an arbitrary number other than zero. Assuming an n-bit block cipher the output can be distinguished from random data after around $2^{n/2}$ blocks since, following the birthday problem, colliding blocks should become likely at that point, whereas a block cipher in CTR mode will never output identical blocks. For 64 bit block ciphers this limits the safe output size to a few gigabytes, with 128 bit blocks the limitation is large enough not to impact typical applications.

I mention the $2^{n/2}$ birthday bound limitation. Removed the part about the period, since it doesn't matter in practice (it's far above both practical output size and safe output size). I also removed the part about keeping key and plaintext (what plaintext? It's a CSRPNG, not a cipher) secret. I'm not really happy with the formulation, so feel free to improve it.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks for the answer! My question was somewhat "theoretical" and not completely practical in nature! What I actually meant was that in order to call something a "psuedo-random" number generator, it should produce values that do repeat :) but of course it is completely impractical to wait so long to "celebrate" a repeating 128bit value even with a generator where collisions are possible. So calling a CTR mode block cipher a "pseudo-random number generator" is inaccurate for 128bit values as it never produces any repetitions! (within a single cycle, I mean) $\endgroup$
    – Anon2000
    May 19, 2015 at 14:46
  • $\begingroup$ @Anon2000 The size of the values is irrelevant, as you already noted, you could concatenate 2 64 bit values to obtain a full block. What matters how much data you output. The security claim for CTR mode is something like "The output is indistinguishable from random data as long as you observe significantly less than $2^{n/2}$ blocks and you don't have enough computational power to bruteforce the key". If you really care, you can quantify that as the probability of distinguishing the random data from the output given the total size of the outputs and the available computational power. $\endgroup$
    – CodesInChaos
    May 19, 2015 at 14:53
  • $\begingroup$ Yes, I understand what you say and it is very helpful! Thanks! but in pure interpretation of the terminology, it should not be called a "psuedo-random number generator" because it does not produce repeating values! What you say is that up to 2^n/2 it is indistinguishable from a "real" PRNG because the probability of a repetition [for a "real" one] is very small anyway. A more descriptive classification would be "unique psuedo-random value generator" (or something like that). This might appear like nitpicking, I know, but I thought this was a meaningful point :) $\endgroup$
    – Anon2000
    May 19, 2015 at 15:03
  • $\begingroup$ @Anon2000 Cryptographers almost always deal with indistinguishability, so the distinction between "real" and "indistinguishable from real" is only made in formal contexts, such as security proofs. For example we don't assume that AES is a PRP, we merely assume it's indistinguishable from one. Cryptography is all about reducing the probability of undesirable outcomes so much that they don't matter in practice. $\endgroup$
    – CodesInChaos
    May 19, 2015 at 15:25
  • $\begingroup$ Actually, I'm not into "nitpicky" stuff at all, I'm a relatively practical person (software developer).. and my knowledge of cryptography is actually limited. I asked it because I thought Wikipedia was misleading in its description (for a non-expert like me I guess). Another thing mentioned in the Wikipedia article was the "claim" that it has a cycle of 2^n, which based on what you say is inaccurate, because it is only "usable" as a PRNG up to 2^n/2. Do you think the Wikipedia article should be updated perhaps? $\endgroup$
    – Anon2000
    May 19, 2015 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.