Reversing Factorio's RNG

Broken in Factorio 2.1 – Version 2.0 only!Factorio 2.1 changes the way the RNG is used.This breaks my in-game implementations. The theoretical aspects of how the RNG works still apply, as they still use the same RNG. For more info see section 6.1. Factorio 2.1. Introduction With the release of the Space-Age DLC in Factorio several new mechanics were introduced. One major mechanic was the new concept of different items and building qualities. By default, items are created with common quality. If quality modules are used in the crafting machine we gain a small chance to obtain items of higher quality. What does that entail? In short: Items and buildings gain improved stats, such as faster crafting speeds, modules providing stronger buffs, power poles having an increased range and inserters swinging faster. Thats pretty neat – hence we are interested in obtaining the highest possible quality on our items and buildings. To source a large number of such items the devs essentially said that this randomness boils down to “basically statistics”,1 i.e. if the volume high quality items one obtains is sufficiently large, then the observed distribution of qualities will be close to the expected distribution. But is it the only way to scale? Thinking about it, one might ponder: How is it possible for a deterministic game like Factorio to have a random mechanic? The short answer is: It isn’t random. Instead – as is common in computing – the simulation makes use of a pseudo-random number generator (PRNG). A PRNG is a deterministic algorithm which produces a sequence of numbers which for all intents and purposes appears to be random. In particular this means properties like it following a well defined distribution of outputs, which contains no discernable patterns. Normally in computer science one can get away with treating the PRNG as just a black box function which can yield random numbers, without concerning oneself with how it actually works. Yet by taking a look under the hood we can do something funny. The Funny: What happens if we know the exact algorithm and its internal state?Then we could just run the same algorithm on the state and obtain the same outputs, which will also be seen by the game internally. Its necessarily always the same outputs, as otherwise the chosen algorithm would not be deterministic. As such we can run the same computations simultaneously to the game and predict the future outputs of the PRNG, allowing us to predict the future “random” events which will occur in the game, such as which crafts will observe an increase in quality. In the following sections I’ll build up to that point, starting from what RNG the game uses, how it is breakable and how it can be abused ingame. The entire background should be understandable if you have a rudimentary understanding of linear algebra. That should be the only prerequisite. Starting from Nothing Soooo, how does one figure out what PRNG algorithm Factorio uses? Afterall, there are several different implementations out there they could have chosen from. To figure this out, my first step was a rudimentary internet research. As the Factorio community is quite large and filled with many technically inclined individuals, surely someone must have asked this question before. After digging around a bit I found a post on the Factorio forums asking basically the same thing I wanted to know, though 11 years have passed since then. In that thread, we also find the following answer by Cube, a former developer at Wube. They wrote: […] We chose taus88 mainly because it is the fastest from boost’s generators. I was thinking of removing one of the three LFSRs (that should make it about 40% (?) faster), but there is no point, since the ran[d]om numbers are not a bottleneck for us. This already gives us a lead on where to look next: the Boost.Random library. There we find the following (abbreviated) implementation for the taus88 generator: typedef xor_combine_engine< xor_combine_engine< linear_feedback_shift_engine<uint32_t, 32, 31, 13, 12>, 0, linear_feedback_shift_engine<uint32_t, 32, 29, 2, 4>, 0>, 0, linear_feedback_shift_engine<uint32_t, 32, 28, 3, 17>, 0> taus88; template<class UIntType, int w, int k, int q, int s> class linear_feedback_shift_engine { // w = word size (e.g. 32 for 32 bit uint) // k = number of bits in the LFSR // q = feedback tap position // s = number of steps to do at once // wordmask() = 0b11...111; mask of w low bits set result_type operator()() { const UIntType b = (((value << q) ^ value) & wordmask()) >> (k-s); const UIntType mask = (wordmask() << (w-k)) & wordmask(); value = ((value & mask) << s) ^ b; return value; } } This means that taus88 consists of 3 linear_feedback_shift_engine whose results are XORed together. Note that this linear feedback shift engine is more commonly referred to as a linear feedback shift register (LFSR). Though when starting the project that post was already 8 years old. Hence, I wanted to cross-check the information given on the forum against the most accurate source available: The game binary. While the game itself is closed source, the developers graciously ship a .pdb file containing the debug symbols alongside the game binary. This means we can generate a well-annotated decompilation of the binary to inspect the code and figure out what is going on under the hood. To this end, I used the open source decompilation tool Ghidra, switching to Binary Ninja later on in the project. Regardless of which tool one uses, one can rather quickly find the RandomGenerator class in the game’s code, where getInt() is implemented as follows: uint RandomGenerator::getInt(RandomGenerator *this) { uint a = this->seed1; uint b = this->seed2; uint c = this->seed3; a = (a << 12 ^ a >> 6) & 0x1fff ^ a >> 19 ^ a << 12; b = (b << 4 ^ b >> 23) & 0x7f ^ b >> 25 ^ b << 4; c = (c << 17 ^ c >> 8) & 0x1fffff ^ c >> 11 ^ c << 17; this->seed1 = a; this->seed2 = b; this->seed3 = c; return a ^ b ^ c; } The first thing which stands out is that almost none of the constants used in the original taus88 definition remain. This can be attributed to the compiler performing optimizations such as constant folding to reduce the number of required operations. Yet the fact that we store 3 seeds for our RNG state is a first strong indicator that it is indeed the same generator. Likewise, the states are updated independently of one another, with the final result being the XOR of all three states. To rid myself of all remaining doubt about whether the two implementations are equivalent, I rewrote both variants in Python so they can be run using sympy, a Python library for symbolic manipulation. Advancing both variants by a single step confirms that all bits of the corresponding registers update in the exact same fashion. I used sympy here because doing these equivalence checks by hand (3⋅32=963 \cdot 32 = 96) would have been quite tedious. The corresponding code can be found here. Ok, with all that established, we are certain that the RNG used in Factorio is indeed the taus88 generator, which itself is a combination of 3 LFSRs. This is a very interesting result, as LFSRs are known to be quite weak PRNGs – in the literature one even finds the statement that they are trivially breakable.2 To understand what makes them ”weak” and how we can exploit this weakness to predict the future RNG calls, we first need to look at the underlying mathematics of LFSRs, which is the subject of the next section. LFSR Maths Review To begin, we need to understand what the linear feedback shift register (LFSR) actually models. First, consider a simple register. It describes a collection of bits, aggregated into a single value xx: x=xn−1…x2x1x0x = x_{n-1} \dots x_2 x_1 x_0 Each individual bit xix_i can be seen as a binary variable with xi∈{0,1}=F2x_i \in \{0, 1\} = \mathbb{F}_2. While it is common to consider this register value xx to represent a number in the range [0,2n − 1]⊆Z[0, 2^n~-~1] \subseteq \mathbb{Z}, it is more useful in our case to instead consider the register to actually describe a vector of individual bits, i.e. x∈F2nx \in \mathbb{F}_2^n. Additionally, we consider two operations which operate on each individual bit: xi⊕yix_i \oplus y_i: The XOR operation takes 2 bits and returns 1 if the bits differ and 0 if they are equal. Note that this is equivalent to addition modulo 2. xi⋅yix_i \cdot y_i: The AND operation takes 2 bits and returns 1 if both bits are 1, otherwise it returns 0. This is equivalent to multiplication modulo 2. Now extend that notion of a register into a shift register. To shift, move all bits in the register downwards by taking each higher bit and shifting it 1 position down, dropping the lowest bit as the output. Here we follow the convention that the most significant bit (highest bit) is the leftmost bit xn−1x_{n-1} and the least significant bit is the rightmost bit x0x_0. You can interact with this kind of register below. Tap the individual bits to toggle them, and use the controls to start, stop and step the registers. 1000011 1x 2x 5x Well… This is boring! We converge pretty quickly to the same value of 0 regardless of the initial state. This does not seem random at all! To keep our shift register from always just discarding all information we will add another component, namely some feedback. The first idea is to just loop the discarded lowest bit back into the highest bit, as it previously had no preceding bit from which it could obtain (new) information, while we discard information in the lowest bit. Doing this we have basically implemented a bit roll operation: 0000011 1x 2x 5x Hmmm… At least we no longer always arrive at an empty register. But the sequence when the last bit lights up is very predictable. This is due to the fact that the information that we observe repeats every nn steps – each bit remains unmodified after all! Thanks to the low cycle length, one can again quickly spot the pattern produced by our current feedback shift