BSLV 2014 - Breaking PRNGs
 

DarthNull.org • About Ⓘ

Hello! I'm David Schuetz.
This is where I ramble about...stuff.

BSLV 2014 - Breaking PRNGs

So I’m back in Las Vegas for another Hacker Summer Camp. After getting to town, checking in at Mandaly, and getting to BSidesLV, I hung out for a while and then decided I should check out a talk.

I didn’t have too much time that I could spend here, as I had to get back to BH for some volunteer duties, but I really was curious about the Mersenne Twister talk by Moloch and Dan Petro.

The Mersenne Twister is a pseudo random number generator (PRNG) that is used by many systems as a way to generate, well, random numbers. The problem is that it’s predictable, as are many other PRNGs. If you can figure out the original “seed” then you can predict the state of the PRNG system at any time and thus predict future random numbers.

In this talk, they described how PRNGs worked, showed some of the weaknesses, and then demonstrated some tools that they can use to break PRNG sequences. Since the seeds for some of these are pretty small (32 bits or even less), they can frequently be broken offline using nothing more powerful than a laptop.

Of course, if you’re attacking a remote site you might not have access to every single consecutive number in a random number stream, but their tool accounted for that too. If you enter some number of, well, numbers, it can then look for sequences with that number in it, where they’re all either directly consecutive or maybe spaced by a few intermediate numbers.

The key problem, they said, was one of “depth” — how far do you try working a seed to see if you’ve found the observed sequence before you assume you’re on the wrong seed and try another? Their tool has the ability to modify depth and other parameters, and thus does a pretty good job of breaking the sequences in many “normal” situations.

All in all, it was a very interesting talk. PRNGs are a bit of a “black box” to many people, and understanding how they work, how easy (some) are to break, and having a tool to demonstrate that (and even use it in a real world test) is definitely a valuable skill to have. I highly recommend checking out the video and/or slides once they’re posted.