Reversing Factorio's RNG

Factorio version 2.1 alters the Random Number Generator (RNG) mechanism, which affects existing in-game implementations utilizing the RNG. The underlying RNG algorithm remains unchanged, as the game continues to employ the same algorithm. For additional details, consult section 6.1 of the Factorio 2.1 documentation. With the introduction of the Space-Age DLC, the game incorporated various new mechanics, one of which is the concept of diverse item and building qualities.

By default, items are generated with common quality; however, using quality modules during crafting introduces a small probability of obtaining higher-quality items. In essence, this implies that items and buildings can achieve enhanced stats, such as accelerated crafting speeds, stronger buffs from modules, extended power pole ranges, and faster inserter movements.

Consequently, players are motivated to acquire a substantial quantity of high-quality items and buildings to optimize their gameplay experience. The developers highlighted that the randomness involved in this process is primarily statistical, suggesting that with a sufficiently large quantity of high-quality items being generated, the distribution of qualities should closely align with the expected distribution.

However, one might question whether there are alternative methods to scale up this process. From a programming perspective, how can a deterministic game like Factorio incorporate a random mechanic? Naturally, this is a common occurrence in computing, where pseudo-random number generators (PRNGs) are employed. A PRNG is a deterministic algorithm capable of generating a sequence of numbers that appear random, characterized by properties such as a well-defined distribution of outputs and the absence of discernible patterns.

While developers typically treat PRNGs as black box functions, examining the underlying code enables manipulation of the algorithm, allowing for the prediction of future outputs and subsequent game events. The subsequent sections of this report delve into these aspects, starting with an overview of the RNG employed by Factorio, followed by an analysis of its breakability and potential in-game exploitation.

It is essential to note that understanding linear algebra is sufficient to grasp the background material presented here. Following this investigation, the focus shifts to determining the specific PRNG algorithm utilized by Factorio. As there exist multiple implementations of PRNGs, identifying the exact algorithm used by Factorio is crucial.

Through preliminary internet research, the focus narrowed down to the taus88 generator, selected by the development team due to its speed. This choice was made evident in a forum post by Cube, a former Wube developer, who explained that the generator was chosen for its speed rather than any performance bottlenecks. The taus88 generator is implemented using three linear feedback shift registers (LFSRs), which are subsequently XORed together to produce the final output.

To verify the accuracy of the forum's information, the game's binary was analyzed. Although Factorio is a closed-source game, the developers provide .pdb files containing debug symbols, enabling decompilation and inspection of the game's code using tools like Ghidra or Binary Ninja. By examining the RandomGenerator class within the game's code, it was confirmed that the taus88 generator is implemented using three separate seeds, each updated independently, and the final result is obtained by XORing the outputs of all three LFSRs.

To further validate the equivalence between the original taus88 definition and the implementation in Factorio, Python scripts were developed to simulate both versions and compare their outputs step-by-step. The Python code for this purpose can be found at a specified GitHub repository. Consequently, it has been conclusively determined that Factorio utilizes the taus88 generator, a combination of three LFSRs, which exhibits known weaknesses in terms of randomness.

Despite this, the deterministic nature of the algorithm allows for the prediction of future RNG outputs, enabling the manipulation of game events and potentially enhancing the player's experience.