# 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. Jul 20 '14 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.