Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
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

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
2^40 bytes is not a lot of output, it's exactly 1 TiB. –  Sklivvz Jul 20 '14 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. –  poncho Jul 20 '14 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. –  Sklivvz Jul 20 '14 at 18:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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