逆向《异星工厂》的随机数生成器
文章摘要
这是一篇耗时两年多的项目总结。作者的目标听起来很荒唐：在《异星工厂》（Factorio）游戏内部，只用游戏自带的运算电路（combinator），实时破解并预测游戏的伪随机数生成器，从而让一台全自动的机器只在「下一次随机数恰好会掷出传奇品质」的时刻才去合成物品。
动机来自 Space Age 资料片引入的「品质」机制：装了品质模块的机器有小概率产出更高品质的物品，而高品质物品属性更强。官方开发者的说法是这归根结底「就是统计学」——量足够大，实际分布就会接近期望分布。作者的疑问是：《异星工厂》是一个完全确定性的游戏（多人联机靠确定性同步），那它的「随机」从何而来？答案当然是伪随机数生成器。而如果你知道确切算法和内部状态，你就能在游戏外并行跑同一套算法，预测未来每一次调用的输出。
第一步是确认算法。 作者先做了常规的网络检索，在 Factorio 论坛找到一个 11 年前的老帖，Wube 的前开发者 Cube 在里面回答说他们选的是 taus88，理由主要是它是 boost 库里最快的生成器。作者不满足于八年前的二手信息，转而查看游戏二进制文件——所幸开发者随二进制一起发布了 .pdb 调试符号文件，于是可以生成注释良好的反编译结果。他先用 Ghidra，后来换成 Binary Ninja，很快找到了 RandomGenerator 类，其 getInt() 的实现里保存了三个 seed，各自独立更新，最终结果是三者异或。原始 taus88 定义中的常数几乎都被编译器的常量折叠优化掉了，但三状态结构与异或输出已经是强证据。为彻底排除疑虑，作者用 Python 的 sympy 把两个版本都符号化重写，逐位比对推进一步后的表达式（三乘三十二共 96 个比特），确认完全等价。
第二步是数学。 taus88 由三个线性反馈移位寄存器（LFSR）组成，而 LFSR 在文献里被认为是「可被轻易攻破」的弱 PRNG。文章用了大量篇幅（配交互式可点击的寄存器动画）从零讲清楚为什么：把 n 比特寄存器视为 GF(2) 上的向量而非一个整数，异或就是模 2 加法、与就是模 2 乘法，二者构成一个域；于是整个状态空间是 GF(2) 上的向量空间，而 LFSR 的每一步状态转移都是各比特的线性组合，可以写成矩阵乘法 s(t+1) = T·s(t)，T 是 GF(2) 上的 n×n 矩阵（可以直接当位图可视化）。一旦写成矩阵，跳跃 k 步就是 T 的 k 次幂。作者也说明了 T 的可逆性：由于 taus88 的三个 LFSR 实际长度分别是 31、29、28 位而字长是 32 位，低位是高位的线性相关项，严格来说矩阵不满秩，但把矩阵缩减到对应尺寸后即恢复满秩，因此逆矩阵存在，可以用高斯消元求出（在 GF(2) 上没有数值稳定性问题，可以直接解出完整逆矩阵）。
第三步是在游戏里实现。 整个流水线分为五步：采样、求当前状态、预测未来状态、换算成品质等级、通过适配器付诸使用。采样单元靠回收「维修包」实现——每次回收产出 0 或 1 件额外物品的概率各 50%，因此每次回收恰好泄露 2 个比特（每件产物对应随机数的最高位）。要恢复 88 比特就需要 44 次回收，于是他复制了 44 组测量单元，并用「同 tick 触发」的接线技巧（在每个插爪前插入 1 tick 延迟电路以构造独立子网络，赌游戏按网络 ID 顺序遍历更新）让所有调用落在同一 tick。关键的优雅之处在于：把观测映射回状态的那个矩阵不依赖任何动态状态，可以在 Python 里离线预计算好，游戏内只需要实现一次 GF(2) 上的矩阵向量乘法——由于每个元素非 0 即 1，乘法退化成条件判断，求和退化成异或，而《异星工厂》电路里多个设备往同一根线写信号时会自动求和，取和的最低位就等于异或，于是「隐式加法」把一大半工作省掉了。向前预测时他一次并行算 1000 步，用二叉树做成对异或归约。品质换算则需要逆向游戏的 rollQuality 函数。为了加速跳过「不好的」随机数，他利用「废料回收」这一每次完成合成消耗 12 次随机调用、基础耗时仅 0.2 秒的配方来快进，不足 12 的余数用每次只消耗 1 次调用的齿轮配方补齐，还要处理废料回收生产力带来的多次完成问题（他先用 AI 从模拟代码里推出闭式公式，再化简成电路）。系统还包含一个偏差检测器：一旦连续两次实际品质与预测不符，就自动重启机器，重新做一次完整的状态观测。
最后是诚实的局限性说明。 有人会问「我能拿这个去操纵我存档里的某某随机事件吗」，作者的回答是「极不可能」。原因在于游戏在 Map 对象上保存了六个（后来七个）全局 RNG，按用途划分：aiRandomGenerator、entitiesRandomGenerator、generalRandomGenerator、mapRandomGenerator、triggerRandomGenerator、unsafeRandom。好消息是虫子的生成与寻路用的是另一个生成器，与物品创建隔离；坏消息是物品创建用的 generalRandomGenerator 是「通用」的，会被大量无关逻辑共用——地板瓷砖随机变体、实验室与火车站的随机命名、玩家手动采矿或在尘土上行走产生的粒子、选择器电路自身的随机种子、采矿机在最后一块矿上的洗牌、Fulgora 的闪电、蜘蛛机器人的腿部落点等等。而且所有需要随机性的机器共用同一个 RNG，你在别处的废料回收线或铀处理线一开工，预测立刻失同步；何况这是一个讲究规模化的游戏，一秒钟几千次调用会直接超出预计算速度。所以这套东西必须从建档之初就纳入设计，而不是往现成存档上加装。
作者还补充了 2.1 版本的坏消息：游戏仍用 taus88，但重写了物品创建逻辑，一次调用会被复用于多个产出，而且现在似乎每一次合成操作（哪怕是确定性的）都会调用 RNG 来填充共享字段，这意味着任何其他机器都不能并行运行。中途还有一段插曲：某个实验版本里 Map::generalRandomGenerator 一度被用来控制鱼的运动，这意味着地图上任何一条鱼都会不断制造未知数量的调用、让预测无可挽回地失同步，除非把地图上所有鱼都清掉；所幸后来的 2.1.13 版新增了第七个生成器 Map::fishRandomGenerator。作者把世界存档、蓝图字符串和整理过的 Python 代码都公开了，并致谢启发他的 Minecraft「Mess Detector」项目作者、factorio-draftsman 库作者，以及「那个在遇到体积可观的 factorio.exe 时真的能正常工作的反编译器」Binary Ninja 团队（脚注里说 Ghidra 即便给 64GB 内存也跑不完）。
HN 评论精华
251 分、48 条评论，整体基调是集体叹服。
jvanderbot 给出了最佳 TL;DR： 「在游戏里搭了一个 RNG 输出预测器，只在随机数会掷出传奇时才去合成传奇物品。从基础品质到传奇的转化率高得惊人。仔细看文章开头那段视频——我是读完整篇文章才反应过来自己刚才看到了什么。」renyicircle 点出了他认为最酷的部分：逆向这个 PRNG 并预测掷点对这类算法而言相对简单，真正了不起的是用运算电路网络在游戏内实现了整套算法。FrustratedMonky 感慨「互联网上还有人在做纯粹极客的深度钻研，这让我看到希望」。poppafuze 则贡献了一句黑色幽默：「跟那个调试符号文件说再见吧。」
几条类似的「破解游戏 RNG」经历被翻了出来。 strstr 说他在大学入门课上做过简单版：班级竞赛里有石头剪刀布环节，平局用随机数打破，而 Java 的 PRNG 用首次调用时的微秒时间播种，于是他大量调用 RNG 收集熵、扫描可能的微秒时间找到种子，再预先把 PRNG 推到他能赢下所有平局的位置。3eb7988a1663 回忆起早期在线扑克系统用服务器时间作种子加弱 PRNG，靠底牌加公共牌几手之后就能确定种子并完美预测所有人的牌；e28eta 帮忙找到了对应的论文，指出问题是糟糕的洗牌实现加上用时刻作种子大幅压缩了搜索空间，用玩家两张底牌加三张翻牌就能实时找出种子，之后同一服务器上的每一手牌都能在「一秒内」解出。PennRobotics 详细介绍了《星露谷物语》的情况：游戏有两个种子，角色种子和多人游戏 ID；Switch 上既不容易访问存档、RNG 实现又与 PC 不同，目前有工具能通过分析旅行商车队的商品列表反推角色种子，但他还没见过破解另一个种子的工具——理论路径是通过检查已开的晶洞内容物来隔离出多人游戏 ID。
一条实质性的技术建议来自 6yyyyyy： 游戏、尤其是多人游戏，应该开始用密码学安全的随机数生成器和哈希函数来处理随机事件。这在《我的世界》里尤其是个问题——人们可以从自然地形的截图反推出坐标。他认为大多数游戏对随机性的性能需求没到成为瓶颈的程度。
关于 boost 那段模板代码，评论区吵了一小架。 cmovq 觉得文章后面给出的那段直白的非模板函数（八行左右的移位和异或）可读性明显更好。windenntw 解释说那叫基于模板的编译期编程：实例化三个 linear_feedback_shift_engine 会强制编译器按不同参数展开三份代码，而参数都是常量，所以即便是 1999 年的 C++ 编译器也能把这几份代码尽可能合并成你反编译看到的那一份；换句话说你写的是相对可读的代码，而产物是完全优化过的。他补充说要用近乎纯 C 实现，你需要相当复杂、更难写对的宏；纯 C 不用宏则得自己推演模板展开的组合，写出的代码更容易有 bug 也更难懂。eru 不太同意，认为用普通 C 函数加上一个足够聪明的编译器应该也行——他说自己让 AI agent 实际跑了一遍实验，在他那个版本的 clang 上，x86_64 生成的汇编相同（只差寄存器选择）。deterministic 则说他每次从项目里移除 boost，构建时间都会大幅下降，而且换掉 boost 代码通常并不费劲。ainiriand 留下了那句被顶起来的吐槽：「C++ 比揍自己老爸还丑。」
chaz6 还顺手关联了同一天的另一则《异星工厂》新闻：微软 C++ 博客提到该游戏必须使用自定义数学库，因为不同平台上的浮点结果差异会导致多人游戏失同步。