Hacking the lehmer64 RNG

A couple days ago I wrote about hacking the Mersenne Twister. I explained how to recover the random number generator’s internal state from a stream of 640 outputs. This post will do something similar with the lehmer64 random number generator. This generator is very simple to implement. Daniel Lemire found it to be “the fastest conventional random number generator that can pass Big Crush,” a well-respected test for pseudorandom number generators. Implementing lehmer64 The lehmer64 generator can be implemented in C by __uint128_t g_lehmer64_state; uint64_t lehmer64() { g_lehmer64_state *= 0xda942042e4dd58b5ULL; return g_lehmer64_state >> 64; } The analogous code in Python would have to simulate the overflow behavior of a 128-bit integer by reducing the state mod 2128 after the multiplication. Reverse engineering lehmer64 is easier than reverse engineering the Mersenne Twister because only three outputs are needed. However, the theory behind the exploit is more sophisticated. See [1].…