Random number manipulation possibilities

Post all other topics which do not belong to any other category.
h.q.droid
Inserter
Inserter
Posts: 46
Joined: Mon Nov 18, 2024 12:10 pm
Contact:

Random number manipulation possibilities

Post by h.q.droid »

I got annoyed at the quality gacha and attempted random number manipulation. I didn't succeed yet, but I disassembled and debugged the factorio executable and got some preliminary results:

Quality is rolled at the *start* of crafting, while probabilistic output (like U-238 / U-235 / recycling bioflux) are rolled at the *end* of crafting.

One global RNG instance is shared by at least the following things:
  • Quality roll
  • Probabilistic output roll
  • Asteroid generation, which rolls every tick
  • Turret shooting
  • Enemy AI
  • Some mining activity, maybe the resource consumption reduction of big mining drill
  • Some asteroid collection activity?
But not:
  • Random mode of selection combinator (each has its own private RNG instance)
The generator is a custom xorshift variant with 96-bit state, easy to evaluate with in-game combinators:

Code: Select all

uint32_t getInt(uint32_t *state){
  uint32_t uVar1;
  uint32_t uVar2;
  uint32_t uVar3;
  
  uVar3 = *state;
  uVar1 = (uVar3 << 13 ^ uVar3) >> 19 ^ (uVar3 & 0xffffe) << 12;
  uVar3 = state[1];
  *state = uVar1;
  uVar2 = (uVar3 * 4 ^ uVar3) >> 25 ^ (uVar3 & 0xffffff8) << 4;
  state[1] = uVar2;
  uVar3 = state[2];
  uVar3 = (uVar3 * 8 ^ uVar3) >> 11 ^ (uVar3 & 0x7ff0) << 17;
  state[2] = uVar3;
  return uVar1 ^ uVar2 ^ uVar3;
}
It's essentially XOR matrix multiplication so you can directly predict the result after an arbitrary number of rolls in one go.

Quality roll logic: roll once p=getInt()/4294967296, if p<quality_percent, bump one level, if p<quality_percent*10%, bump another, continue until highest researched quality is reached or test failed. I haven't reverse-engineered the production roll logic yet.

This enables a few building blocks:
  • Probe RNG state with quality / probabilistic production.
  • Consume RNG rolls with cheap with-quality production or circuited turrets shooting at something.
But we lack reliability: some unpredictable rolls can happen between controllable rolls every tick. So the most reliable option is to somehow predict future rolls on the same tick we probe the RNG state or abort production after we finished predicting the quality roll, neither seem possible right now.

There are several possible directions:

Expensive semi-auto quality scumming. Say you have ~2k cryogenic plants making expensive stuff like fusion generator from common materials + 96 recyclers leaking RNG state. Start all recyclers on the same tick, then start all cryogenic plants on the exact tick the recyclers will create output. Then you can predict the quality rolls of each plant with combinators from the recylcer results and only enable those producing legendary ones. After you get the legendary products though, you'll have to clean up by manually deconstructing / reconstructing everything and start over.

Math stuff. The RNG quality is not very good and exhibits significant auto-correlation. But I haven't found a way to exploit such correlation reliably in-game yet.

Speedrun-only option: if you have no space platform moving / collecting asteroids, have no random crafting / big-drill mining and somehow kill all enemies within active chunks, you have total control over the RNG for like one minute before biters roll their expansion, during which you can guarantee a bunch of quality stuff from common materials.
User avatar
Khazul
Fast Inserter
Fast Inserter
Posts: 199
Joined: Fri Sep 03, 2021 4:47 am
Contact:

Re: Random number manipulation possibilities

Post by Khazul »

RNG instancing and the method used I expect are to provide determinism in multiplayer ie that the action on the server can be performed by the client and they both end up with the same result so the client only need to know what actions to perform and doesnt need to also be told the result of such actions. This I expect is essential for multiplayer performance as sending action rather than action+state updates would be a significant saving and likely what makes this game viable at all for multiplayer.
Tertius
Smart Inserter
Smart Inserter
Posts: 1078
Joined: Fri Mar 19, 2021 5:58 pm
Contact:

Re: Random number manipulation possibilities

Post by Tertius »

How do you get *state ingame? As long as you don't know the seed, you're unable to predict.
Nidan
Filter Inserter
Filter Inserter
Posts: 283
Joined: Sat Nov 21, 2015 1:40 am
Contact:

Re: Random number manipulation possibilities

Post by Nidan »

Tertius wrote: Thu Dec 19, 2024 10:10 am How do you get *state ingame? As long as you don't know the seed, you're unable to predict.
Unless you mess with the state (~ reseeding), any PRNG will give you a fixed and repeating sequence of numbers(*), the "randomness" comes from the fact that you don't know where in the sequence you are. Therefore, if you can control the questions asked, you get information about its internal state from observing the output: Ask a PRNG for a coin flip (one bit) and you get one bit of information about the current state. (Out of all possible states, half can't give you the result you observed.) Repeat that often enough, and you can get the current state.

OP describes such an attack (and claims factorios PRNG has a particular weakness they can make use of). A bunch of controlled questions are made in sequence. The first part (recyclers) tries to get as much information as possible, the second part (quality) is then predicted.

*) For a PRNG with n bits of state, that sequence should be 2^n numbers long.
coffee-factorio
Long Handed Inserter
Long Handed Inserter
Posts: 84
Joined: Thu Oct 17, 2024 10:56 pm
Contact:

Re: Random number manipulation possibilities

Post by coffee-factorio »

Tertius wrote: Thu Dec 19, 2024 10:10 am How do you get *state ingame? As long as you don't know the seed, you're unable to predict.
So imagine you have a message and you do some math to each letter to make it different. That's what a prng does too in way. You can imagine taping the the message together to make a loop. And then when you run over the message again you rewrite it. You can't in practice do that with a PRNG because you have to keep your place on the tape to, an eventually that forces you to restart instead of walking forever.

So what OP is doing is smart in that he can get the description of the math operations and I support their interest in computer science.

But I do have to point out that OP could mod in some tuners if someone hasn't already to just make a machine of their choice at the cost they feel is necessary to spend. As that will let them have a machine of whatever speed they want at whatever price they feel is fair without having to reverse engineer code.

Instead of save scumming you can just use a mod to have a machine or item at your price.

And that's how you get a space probe that includes a rock picker as a dependent part -_-
kovaxis
Manual Inserter
Manual Inserter
Posts: 2
Joined: Mon Dec 23, 2024 4:59 pm
Contact:

Re: Random number manipulation possibilities

Post by kovaxis »

Very interesting. How exactly do you think "probing the RNG" would work? You seem to imply that you know how to make it work, but don't explain it.

My guess is that with a recipe that has random output with 50% chance, then whether there's a random output or not reduces (maybe with some error) to

Code: Select all

getInt() < 2^31
. In this case, we can reliably get the most significant bit of output per recipe crafted, and then solve the matrix equations to get the state.

Also, what is the sub-tick ordering of the random queries? Is it just the build order? What about events that are not attached to entities? (eg. asteroids spawning?)

I think quality scumming might work well, maybe with the recursive blueprints mod (although using mods kind of breaks the purpose of this exploit). Maybe change recipes with signals instead of deconstructing the machines? Not sure if it works.
h.q.droid
Inserter
Inserter
Posts: 46
Joined: Mon Nov 18, 2024 12:10 pm
Contact:

Re: Random number manipulation possibilities

Post by h.q.droid »

kovaxis wrote: Mon Dec 23, 2024 5:58 pm Very interesting. How exactly do you think "probing the RNG" would work? You seem to imply that you know how to make it work, but don't explain it.

My guess is that with a recipe that has random output with 50% chance, then whether there's a random output or not reduces (maybe with some error) to

Code: Select all

getInt() < 2^31
. In this case, we can reliably get the most significant bit of output per recipe crafted, and then solve the matrix equations to get the state.

Also, what is the sub-tick ordering of the random queries? Is it just the build order? What about events that are not attached to entities? (eg. asteroids spawning?)

I think quality scumming might work well, maybe with the recursive blueprints mod (although using mods kind of breaks the purpose of this exploit). Maybe change recipes with signals instead of deconstructing the machines? Not sure if it works.
Since I haven't found a way to exploit the state, I haven't investigated the probing / sub-tick ordering too deeply. I do intend to use a 50% recipe to get the MSB like you said. Need to debug the non-quality code a bit for a fully working solution, though, since it's impossible to get 50% with quality modules due to premature rounding.

I haven't fully checked the sub-tick ordering either. During my debugging, the asteroid spawning always seems to have its own phase, happening in a big clump either after or before other stuff. It could be me never catching multiple surfaces producing stuff on the same tick, though.

Signal-changing recipes waits for the current production session to finish so kinda hard to exploit here.
kovaxis
Manual Inserter
Manual Inserter
Posts: 2
Joined: Mon Dec 23, 2024 4:59 pm
Contact:

Re: Random number manipulation possibilities

Post by kovaxis »

I've made some progress. I'm focusing on a proof-of-concept "speedrun style" exploit for now, in the Factorio sandbox.

I have this contraption:
Contraption
It recycles gears (which have a 50% chance of producing iron plate), and if no iron plate is produced, it places a copper plate on the belt instead. This means that the resulting pattern of copper/iron on the belt should be exactly the MSB bits produced by the RNG:
Pattern of plates on belt
And made a Python script that I can feed the pattern of Iron/Copper plates, and can predict the future production of Iron/Copper!
It turns out you only need 88 samples, since there are 8 bits of state that are simply discarded when transitioning state.
I distilled a matrix that you can just multiply with your 88 MSB bits and get the 96 bits of state at the end of the 88-query sequence:
Recipe matrix
To use it, multiply the recipe matrix by a column vector of the samples, ordered from the oldest at the top and the newest at the bottom:

Code: Select all

state = recipe_matrix * sample_vector
The state is just a 96-bit vector, with the LSB of the first word at the beggining and the MSB of the third word at the end. I managed to predict quality output using this technique! I recycled 100 gears, figured out I needed to wait exactly 445 crafts to get a 2-step quality increase (random value < 0.001), crafted 444 gears, then crafted 1 exoskeleton out of common materials and got a rare exoskeleton!

There are a few details:
- For some reason I had to negate the inputs. According to the wiki, the formula for the number of items that a recycler will produce is floor(0.25 * I / O + r), with I the number of inputs, O the number of outputs and r a random value. For some reason, I had to consider Iron as an MSB of 0 and No-Iron as an MSB of 1. It looks like r is computed as 1 - getInt()/2^32?
- Implementing the matrix multiplication using combinators in-game looks horrible. 264 arithmetic combinators to combine all 88 samples. The thing is, there is probably a cleaner way, something along the lines of inverting the state-transition function and iterating the same set of combinators many times. I'll give it some more thought when I have more sleep in my body.

Btw merry christmas!
h.q.droid
Inserter
Inserter
Posts: 46
Joined: Mon Nov 18, 2024 12:10 pm
Contact:

Re: Random number manipulation possibilities

Post by h.q.droid »

Merry Christmas! Best Christmas gift I ever got!

The product-giving code is really complicated with 2 if-else branches containing 3 different rolls. The shortest path only reaches one. I haven't debugged it yet. Thanks for discovering the inversion! Your contraption looks really cool :)

For combinators, do you really need a full 88-bit multiplication? Speedrun only needs to predict ~8 bits for a rare product so you only need to multiply 8 columns. With the implicit addition of wire connection, if you could route the 88 inputs to one different belt segment each, you can use the wires to connect the belts corresponding to 1-cells to one iron-AND-1 arithmetic combinator for each column (add is xor if you ignore carry). Just need a few other belts to split wire connections. That's what I thought of when trying for zero-tick signal control. I haven't found a practical way to overflow the high bits or do and-of-even-odd-tests though.
h.q.droid
Inserter
Inserter
Posts: 46
Joined: Mon Nov 18, 2024 12:10 pm
Contact:

Re: Random number manipulation possibilities

Post by h.q.droid »

Sorry for necro-ing this, but I just saw on reddit the last-minute-science-recycle trick. When combined with RNG manipulation, this can return 100% science on recycle and last indefinitely! A speedrunner would only need to ship a few of each science back to Nauvis to keep researching until the Gleba one expires (making them rare could allow them to last an entire game). That would also allow reducing competing random draws to virtually nothing and greatly simplify the manipulation process. If enemies ever prove to be a problem, one could even nuke the Nauvis / Gleba bases and do the infinite research in a space platform.
Post Reply

Return to “General discussion”