6
$\begingroup$

I am going through Dan Boneh's Cyprography lectures on Coursera.

In Lecture 6 https://class.coursera.org/crypto-010/lecture/6

At 7:30 minutes, he discusses the problems with 802.11b design. I understand his critique. However, he then moves on to what would be better design at 12:55 minutes.

He says that they could use a PRG to generate a very long key from the key and then use segments of the PRG(K) to encrypt each frame.

Even if you generate a very long PRG(K), considering the amount of traffic exchanged, wouldn't key still get repeated every few hours or so - i.e. you come to the end of the PRG(K), you have to start reusing first segment of PRG(K) again - which will lead to the key reuse problem. So what am I missing here?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ That's a great course. Just took it. Enjoy! $\endgroup$
    – Linuxios
    Commented Jun 25, 2015 at 15:46

1 Answer 1

Reset to default
11
$\begingroup$

...wouldn't key still get repeated every few hours or so - i.e. you come to the end of the PRG(K)...

This is where you are mistaken. Modern cryptographic PRGs simply do no repeat within any conceivable time frame. That is, starting from a seed, a well-constructed PRG (and this is true even when they are not so well constructed, like RC4) will simply never "come to an end" within our life time. You will have to run it for such a long time that the universe will probably have grown dark before you see it cycling back. Hence, for all practical purposes, cryptographic PRGs never repeat.

However, as noted in the video, this only holds true starting from some initial seed which is held fixed throughout the process. Note that the problem with WEP was that they reused the input (i.e. the seed) to the PRG, it was not because the output cycled around! Once you reuse the seed to a PRG then you will of course see the same output stream.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Note that the problem with WEP was that they reused the input (i.e. the seed) to the PRG, it was not because the output cycled around! - yes I did understand that. However, I didn't know that PRGs didn't cycle. Thank you $\endgroup$
    – user93353
    Commented Jun 25, 2015 at 12:46
  • 3
    $\begingroup$ @user93353 hakoja already said this, but to be absolutely clear, they do cycle (any deterministic process with a finite state eventually has to come back to a previous state, mathematically speaking), but they have very long periods (e.g. 2^200 or more). A PRG with a cycle of length 2^200 generating one trillion numbers per second will return to its origin after slightly more than 50 million trillion trillion years. $\endgroup$
    – hobbs
    Commented Jun 25, 2015 at 16:43
  • 1
    $\begingroup$ For perspective on the time scale @hobbs gave, that's after the predicted death of not only our own sun, but every star in the entire universe (even the ones that haven't formed yet)! $\endgroup$
    – Sabre
    Commented Jun 25, 2015 at 17:21

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.