How hackers reverse Math.random()

### TL;DR 计算机的“随机数”实际来自可预测的数学公式，只要知道算法和足够的状态，就能反向推导出过去和未来的所有随机数。本文演示如何破解线性同余生成器、XOR shift 生成器，以及 Flash 的随机数生成器，最后通过预测扫雷地雷位置展示实际攻击。 --- ## 计算机如何生成随机数 当你让电脑选一个随机数时，它通常是从一个完全可以预测的序列中取值。这个序列由简短的数学公式生成，每次需要随机数时运行一次。最简单的例子是**线性同余生成器**（Linear Congruential Generator, LCG）： ``` 下一个数 = (上一个数 × 9301 + 49297) % 233280 ``` “取模”意味着数字超过 233280 就回绕到 0，就像《小行星》游戏里物体从屏幕一侧穿到另一侧。用这样的公式生成的“随机”数列足够长（本例约 23 万个数才重复），而且画成图像时大致像噪声。但如果改变网格尺寸，还是能看到线条图案。 --- ## 破解线性同余生成器 LCG 的可逆性依赖于**模逆元**。已知下一个数，要算回上一个数，需要反解： ``` 上一个数 = (下一个数 − 49297) × 模逆元 % 233280 ``` 普通除法在取模下不成立，但当模数与乘数互质时，存在一个数（称为模逆元）使得 `乘数 × 模逆元 ≡ 1 (mod 模)`。本例中 9301 的模逆元是 179509，于是可以写出逆向函数。 **现实场景**：PHP 的 `lcg_value()` 使用类似的 LCG。如果网站用它生成验证码，攻击者只需用自己收到的验证码逆向推出种子，就能预测你丢失账号的验证码。 --- ## 破解 XOR-Shift 生成器 XOR shift 是另一种常见的随机数生成器，尤其用于 Flash 和 JavaScript。一个 32 位的版本： ``` x ^= x << 13 x ^= x >> 17 x ^= x << 5 ``` 每一行都是“先移位，再异或”。异或（XOR）运算有个好性质：**两次异或同一个数会还原**。所以逆向 XOR shift 的关键是逐步恢复被影响的位。例如左移并异或 7 位时，最低 7 位没有受到影响，可以利用它们反复异或回去，直到完全恢复原值。 对于 Xorshift128+（JavaScript 的 `Math.random()`），已有手工逆向方法（Scott Contini）或使用 Z3 求解器。Minecraft 使用的 Xoroshiro128++ 更难，但社区仍在攻关。 --- ## 破解 Flash 的随机数生成器 Flash Player 的随机数机制非常复杂：先用**线性反馈移位寄存器**（LFSR）初始化种子，然后组合 XOR shift、减法移位、多项式形式的 LCG，再来一次 XOR shift 和减法移位。每一步都可逆。2017 年 Dango 编写了完整逆向函数，2019 年 George Teșeleanu 论文优化了过程。之后速通玩家 Koong 实现了工作演示，但原项目文件丢失；社区通过反编译归档版本，修复了一个反编译器 bug，最终成功重现。 现在可以完全控制 Flash 的每一个随机数。例如在四叶草游戏中强制生成低数值，让所有三叶草出现在田地顶部。 --- ## 实际演示：预测扫雷地雷位置 **不修改种子、不注入代码**，仅通过观察一个初级扫雷谜题的地雷位置，反向搜索数十亿种子，找到能生成完全相同谜题的种子，然后预测下一个专家谜题的 99 颗地雷。演示成功标记了所有地雷。有趣的是，在逆向专家模式生成器时，发现源代码有一个 bug，导致某些地雷永远不会出现在特定位置——这个漏洞本身比反向生成器更有用。 --- ## 结论与建议 - 不要用普通随机数生成器做安全相关的事（如验证码、加密），务必使用标记为“密码学安全”的生成器。 - 对于本地离线生成随机数的场景（如单机游戏），基本可以肯定可以被破解。开发者不必过度焦虑算法选择，而应关注**数据泄漏**（例如 Flash 在不同程序间共享种子）和**可预测的模式**（如扫雷 bug）。 - 速通记录中的“超自然运气”可能只是逆向随机数的结果。 > *“我只有在胜算完全由我掌控时才会赌博。”* --- **Source**: [How hackers reverse Math.random() – YouTube](https://www.youtube.com/watch?v=XDsYPXRCXAs) (Comments on [Lobsters](https://lobste.rs/s/kzw3rt/how_hackers_reverse_math_random))