How to exploit a vulnerable pRNG?

Question

Sources often state that if a pRNG has a predictable seed like time of date the resulting output has little entropy and can be exploited.

But how do you actually go about exploiting the pRNG? Do you have to watch the output stream for a prolonged period of time? In that case what do you analyze and how do you use it?

Are there any papers on the subject?

Suppose you suspect that a system has a very weak pRNG seeded with mere time, how do you confirm suspicion? How do you use it?

Or if you want to test a pRNG to see if it's very weak, how would you go about it?

Answer 1

Holy questions batman. Hopefully I'm not too late to the party.

But how do you actually go about exploiting the pRNG?

That depends on the system using it, and what(if any) advantage is to be gained from knowledge of the next random number.

Do you have to watch the output stream for a prolonged period of time? In that case what do you analyze and how do you use it?

See, a lot of this depends hugely on the kind of RNG used. For example, consider two different RNG algorithms, both seeded with system time. The first is a linear congruential generator or LCG, the second is a Mersenne Twister. If you have the algorithm for the LCG, you can predict the the next number after seeing just one random number produced. Even if you don't, if you know the seed and/or have access to a decently sized stream of outputted random numbers, you can figure it out with brute force in a couple of minutes.

As for the mersenne twister, even if you know the algorithm, it would still take 624 random numbers outputted before you could possibly predict the next one, not to mention the jump in complexity of the algorithm you'd write to do that.

So already, there's a huge difference in difficulty of exploitation. Once you get to blum blum shub or another similarly crypto-appropriate algorithm, it becomes nearly impossible.

Are there any papers on the subject?

Loads. Here are some articles anyway:

This is a really cool example of a whole RNG-based exploit

This one is a bit more focused on the RNG itself

Suppose you suspect that a system has a very weak pRNG seeded with mere time, how do you confirm suspicion? How do you use it?

Again, it depends on the RNG used. For an LCG, with some basic knowledge, it wouldn't take too long to figure out. Do some reading on them, and you'll see what I mean. For anything more complex, the difficulty goes up exponentially.

Or if you want to test a pRNG to see if it's very weak, how would you go about it?

PRNG have periods, or a cycle of numbers that will keep repeating. This is a pretty good way of telling how good they are. Sometimes they're really short if the wrong numbers or generator is chosen. A really simple test that works if you have unlimited access to the generator (like if you've got some blackbox'd Random() function in your code you want to quality check), is to just record the first number you get, and wait to see how long it takes for that number to come up again. If it happens in a few minutes(2^32 numbers), you're dealing with a simple LCG. For something like a Mersenne Twister, it won't come up again for a couple millenia(2^19937 − 1).

Hopefully that helped a bit.