恢复xorshift128随机数生成器的内部状态Recovering the state of xorshift128

最近我写了几篇文章，探讨如何逆向工程随机数生成器的内部状态，先是 Mersenne Twister，然后是 lehmer64。本文将分析 xorshift128，其实现如下。

import random

# Seed the generator state
a: int = random.getrandbits(32)
b: int = random.getrandbits(32)
c: int = random.getrandbits(32)
d: int = random.getrandbits(32)

MASK = 0xFFFFFFFF

def xorshift128() -> int:
    global a, b, c, d

    t = d
    s = a

    t ^= (t << 11) & MASK t ^= (t >>  8) & MASK
    s ^= (s >> 19) & MASK

    a, b, c, d = (t ^ s) & MASK, a, b, c

    return a

恢复该生成器的内部状态很简单：它就是最后四个输出值按逆序排列的结果。这一点可通过下图说明。

这意味着一旦我们观察到四个输出值，就能预测后续的所有输出。以下代码展示了这一点。

让我们生成五个随机数值。

out = [xorshift128() for _ in range(5)]

运行

print(hex(out[4]))

得到输出 0xc3f4795d。

如果我们使用前四个输出来重置生成器的状态

d, c, b, a, _ = out
print(hex(xorshift128()))

会得到相同的结果。

统计性能好，安全性差

尽管 Mersenne Twister 和 lehmer64 具有可预测性，但其统计性能良好。xorshift128 生成器更容易被预测，但同样具备良好的统计特性。这类生成器适用于许多场景，如蒙特卡洛模拟，但在密码学应用中则极为危险。

在关于 lehmer64 的文章末尾提到，PCG64 的内部状态也可从其输出中恢复，但这需要极其复杂的数学运算和数千小时的计算时间。即便如此，它仍不适合用于密码学。要实现安全应用，应使用专为安全性设计的随机数生成器，例如 ChaCha。

那么为什么不干脆对所有情况都使用加密安全的伪随机数生成器（CSPRNG）呢？当然可以，但本文提到的其他生成器占用的内存更少，运行速度也更快。PCG64 处于一个有趣的中间位置：简单、快速，且不易被逆向。