6
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – D.W.
    Commented Jul 20, 2014 at 6:09

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 2^40 bytes is not a lot of output, it's exactly 1 TiB. $\endgroup$
    – Sklivvz
    Commented Jul 20, 2014 at 12:58
  • $\begingroup$ @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. $\endgroup$
    – poncho
    Commented Jul 20, 2014 at 15:52
  • $\begingroup$ 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. $\endgroup$
    – Sklivvz
    Commented Jul 20, 2014 at 18:16

Your Answer

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

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