YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← PRNG Implementation Solution - Applied Cryptography

Get Embed Code
1 Language

Showing Revision 4 created 05/25/2016 by Udacity Robot.

  1. The answer is no. It repeats values too
  2. infrequently. This may seem a little surprising.
  3. If it was random, well the probability of two
  4. consecutive values being equal should be to
  5. the negative 128, a very low probability, but
  6. not zero. If this is an encryption cipher, well
  7. it satisfies the property of invertibility. So
  8. any value thats different here encrypts to a
  9. different value. So that would mean that for
  10. our actual pseudo random number generator, this
  11. probability is actually equal to zero. And thats
  12. different from what it would be in a real random
  13. sequence. This probability is low enough that we
  14. still wouldnt expect a repetition for a long
  15. time, but we would expect to have one within
  16. the first two to the 70 outputs. And we
  17. will talk soon about the birthday paradox
  18. to see why we would expect one this soon.
  19. Still a pretty big number, but it would be enough
  20. to distinguish this from pure randomness. So to
  21. fix that, there is a couple of things we could do.
  22. One is to occasionally change the key and after
  23. some number of outputs we can take one output,
  24. instead of using it as an output we use it as the
  25. new key. So even if we dont have any more
  26. randomness, we will still change the key; that
  27. will affect this probability, it will no
  28. longer be zero, we will start seeing values
  29. that have some probability of repeating what
  30. we saw with the previous key. So well
  31. get a new key every few million outputs.
  32. The other concern is whether this pool of
  33. randomness is good enough? On Unix machines
  34. there is a pool of randomness stored in
  35. /dev/random and it is collecting events that
  36. are believed to be random and out of the
  37. control of the attacker. These could be user
  38. actions like key presses; these could be
  39. things that you collect over the network.
  40. There is some risk that these could be compromised,
  41. that some of them could be controlled or at
  42. least predictable to the attacker. So we want
  43. to have multiple pools of randomness and
  44. combine them in a way that makes it very
  45. difficult for an attacker to control this seed.
  46. And this is essentially what the Fortuna
  47. Pseudo Random Number Generator does
  48. and thats one of the more popular widely
  49. used ones. It does use this routine to avoid
  50. this apparently non-random property and it uses
  51. multiple pools of randomness selected in a way
  52. that makes it very hard for an attacker to control
  53. what the seed is, even if the attacker can
  54. control one or a few of the pools of randomness.