# Turning PRPs in PRGs with a counter

I am following the Coursera Cryptography I course and I have the following question,

I am a bit perplexed by the statement, in week 2 lecture "What are block cyphers?" that a counter-mode PRF is a secure PRG.

PRPs are PRFs, and PRPs have the property that if (x₁, x₂) ∈ X, x₁ ≠ x₂, then PRP(x₁) ≠ PRP(x₂) -- since they are invertible.

Using a PRP in counter mode results in a series of values which are all different from each other. Now -- this is not random. In fact, we can see that, in the case of a 128 bit PRP, for example, after 2⁶⁴ different output it is actually more likely to get a repeat than not. However the PRG we created won't have this behavior and we would be able to distinguish them.

In other word, wouldn't this PRG susceptible to a birthday attack?

• You might like to read about the PRP/PRF switching lemma, which helps show that CTR mode is a secure PRG "up to the birthday bound" (i.e., as long as you don't generate too many outputs).
– D.W.
Commented Jul 20, 2014 at 6:09

You are quite correct. A PRP in counter mode is, in fact, distinguishable from a random sequence if you approach the "birthday bound". We get around this by never generating that much output at once. With a 128 bit block cipher, an output of $2^{40}$ bytes (which is a lot of output) gives us a distinguishing advantage of about $2^{-56}$ (the probability of a random sequence of blocks of that length would have a repeat) -- this is small enough that we don't worry about it.

• 2^40 bytes is not a lot of output, it's exactly 1 TiB. Commented Jul 20, 2014 at 12:58
• @Sklivvz: when was the last time you generated 1 TiB of output from a random number generator? In any case, if you need to generate more, all you need to do is periodically rekey the block cipher. Commented Jul 20, 2014 at 15:52
• For example if one encrypts a drive, it could be conceivably done by XOR-ing with a PRG-generated sequence, i.e. a stream cypher. 1TiB is not an uncommon size for a hard drive, it's actually a cheap 50\$ drive as of 2014. Commented Jul 20, 2014 at 18:16