Untwisting the Mersenne Twister: How I Killed the PRNG

Random number generation has been insecure for decades and there hasn’t been a practical pen testing tool to tackle this problem – until now, that is.

Enter Untwister

Untwister is a tool designed to help pentesters predict random number sequences when an application generates them using an insecure algorithm. The tool is named for the Mersenne Twister, one of the most widely used random generators.

Researchers have understood this for decades, but the concept has been purely hypothetical.

Random number generation is used for:

• Password generation
• Unique file-sharing IDs
• URL shorteners
• Cryptographic nonces

And that’s only the tip of the RNG iceberg.

If someone finds the initial seed, he or she can generate all following random numbers. This means someone could possibly do things like cheat online gambling sites, impersonate other users, and access confidential data. Breaking random number generation has been almost completely theoretical before. Untwister has taken this idea and weaponized it. Untwister reads the output from insecure random number generators and reveals the initial seed used to create those numbers. It accomplishes this via a few different methods:

• Poorly chosen seeds. Application developers often choose seeds from not-so-secret numbers, such as the current server time or the service’s process ID (PID). This makes it easy to enumerate all possible valid seeds and recover the original.
• Seed brute-force. Even when seeds are unpredictably chosen, brute-force enumeration is usually feasible. Since most insecure random generators take 32-bit integers as seeds, a strong computer can run through all 4.2 billion seed values.
• State inference. Insecure random number generators still leak information about their internal state by way of selected numbers. Once an attacker observes enough of these values, all it takes is some math to reconstruct the generator’s current state. Once cracked, the generator’s state allows us to predict future and past values.

RNG Best Practices

How can developers protect their applications when security is at stake? By taking the time to do it properly. Most frameworks provide default random number generators, which are predictable and unsuitable for a secure context. To keep your random numbers unpredictable, however, use a Cryptographically Secure Pseudo-Random Number Generator (CSPRNG).

The exact available functions will depend on the language and framework, but some examples of CSPRNGs to use are:

• Reading from /dev/urandom on a Unix-like system
• The Java SecureRandom class
• The .NET RNGCryptoServiceProvider class
• The PHP openssl_random_pseudo_bytes() function

In contrast, some examples of random number generators to avoid are:

• The libc rand() function
• The Java Random class
• The .NET Random class
• PHP’s rand() and mt_rand() functions

The Untwister was originally presented by Bishop Fox's Joe DeMesy and Dan Petro at Security B-Sides Las Vegas on Aug. 5, 2014.

Want to download the Untwister for your pentesting purposes? Visit the Bishop Fox Github here.