
Title:
PRNG Implementation Solution  Applied Cryptography

Description:

The answer is no. It repeats values too

infrequently. This may seem a little surprising.

If it was random, well the probability of two

consecutive values being equal should be to

the negative 128, a very low probability, but

not zero. If this is an encryption cipher, well

it satisfies the property of invertibility. So

any value thats different here encrypts to a

different value. So that would mean that for

our actual pseudo random number generator, this

probability is actually equal to zero. And thats

different from what it would be in a real random

sequence. This probability is low enough that we

still wouldnt expect a repetition for a long

time, but we would expect to have one within

the first two to the 70 outputs. And we

will talk soon about the birthday paradox

to see why we would expect one this soon.

Still a pretty big number, but it would be enough

to distinguish this from pure randomness. So to

fix that, there is a couple of things we could do.

One is to occasionally change the key and after

some number of outputs we can take one output,

instead of using it as an output we use it as the

new key. So even if we dont have any more

randomness, we will still change the key; that

will affect this probability, it will no

longer be zero, we will start seeing values

that have some probability of repeating what

we saw with the previous key. So well

get a new key every few million outputs.

The other concern is whether this pool of

randomness is good enough? On Unix machines

there is a pool of randomness stored in

/dev/random and it is collecting events that

are believed to be random and out of the

control of the attacker. These could be user

actions like key presses; these could be

things that you collect over the network.

There is some risk that these could be compromised,

that some of them could be controlled or at

least predictable to the attacker. So we want

to have multiple pools of randomness and

combine them in a way that makes it very

difficult for an attacker to control this seed.

And this is essentially what the Fortuna

Pseudo Random Number Generator does

and thats one of the more popular widely

used ones. It does use this routine to avoid

this apparently nonrandom property and it uses

multiple pools of randomness selected in a way

that makes it very hard for an attacker to control

what the seed is, even if the attacker can

control one or a few of the pools of randomness.