🔒 安全

破解 lehmer64 随机数生成器Hacking the lehmer64 RNG

johndcook.com·2026-05-12

文章探讨了如何从 lehmer64 随机数生成器的输出流中恢复其内部状态，类似于之前对 Mersenne Twister 的攻击方法。lehmer64 是一种简单高效的伪随机数生成算法，由 Daniel Lemire 提出并因其高性能被广泛使用。作者通过分析其数学结构，展示了在仅观察 640 个连续输出值的情况下即可完全重构生成器状态的技术路径。该研究揭示了即使设计简单的 RNG 也可能存在严重的安全漏洞。

阅读原文

John

几天前我写了一篇关于破解 Mersenne Twister 的文章，解释了如何从640个输出中恢复随机数生成器的内部状态。

本文将用类似的方法分析 lehmer64 随机数生成器。该生成器实现非常简单。Daniel Lemire 发现它是“能通过 Big Crush 测试的最快传统随机数生成器”——Big Crush 是评估伪随机数生成器性能的一个权威测试套件。

lehmer64 的实现

在 C 语言中，lehmer64 生成器可以这样实现：

__uint128_t g_lehmer64_state;

uint64_t lehmer64() {
    g_lehmer64_state *= 0xda942042e4dd58b5ULL;  
  return g_lehmer64_state >> 64;
}

对应的 Python 代码需要通过模 2^128 运算来模拟 128 位整数的溢出行为，以模拟乘法后的状态变化。

逆向工程 lehmer64 比逆向工程 Mersenne Twister 更容易，因为只需要三个输出即可。然而，其背后的攻击理论更为复杂，详见 [1]。

以下代码将状态设置为任意初始种子值，并生成三个随机数值。

#include <stdio.h>
#include <stdint.h>

int main(void)
{
    g_lehmer64_state = 0x4789499d78770934; // seed
    for (int i = 0; i < 3; i++) {
        printf("0x%016lx\n", lehmer64());
    }

    return 0;
}

代码输出如下：

0x3d144d12822bcc2e
0x85a67226191a568d
0x53e803dffc88e8f8

利用 lehmer64 的漏洞

以下是根据 [1] 中的描述，用于恢复 lehmer64 生成器状态的 Python 代码。

def reconstruct(X):
    a = 0xda942042e4dd58b5
    r = round(2.64929081169728e-7 * X[0] + 3.51729342107376e-7 * X[1] + 3.89110109147656e-8 * X[2])
    s = round(3.12752538137199e-7 * X[0] - 1.00664345453760e-7 * X[1] - 2.16685184476959e-7 * X[2])
    t = round(3.54263598631140e-8 * X[0] - 2.05535734808162e-7 * X[1] + 2.73269247090513e-7 * X[2])
    u = r * 1556524 + s * 2249380 + t * 1561981
    v = r * 8429177212358078682 + s * 4111469003616164778 + t * 3562247178301810180
    state = (a*u + v) % (2**128)
    return state

让我们用上面 C 代码的输出来调用 reconstruct 函数。

X = [0x3d144d12822bcc2e, 0x85a67226191a568d, 0x53e803dffc88e8f8]
print( hex( reconstruct(X) ) )

输出结果为：

0x3d144d12822bcc2e1b81101c593761c4

现在解释一下令人困惑的部分：上面的数字是生成器在哪个时刻的状态？是在生成三个值之前还是之后？都不是！它是在生成第一个值之后的那个状态。

我们可以通过修改 C 代码并重新运行来验证这一点。

void print_u128(__uint128_t n)
{
    printf("0x%016lx%016lx\n",
           (uint64_t)(n >> 64),      // upper 64 bits
           (uint64_t)n);             // lower 64 bits
}

int main(void)
{
    g_lehmer64_state = 0x4789499d78770934; // seed
    for (int i = 0; i < 3; i++) {
        printf("0x%016lx\n", lehmer64());
        printf("state: ");
        print_u128(g_lehmer64_state);
    }
 
    return 0;
}

[1] 的主要目标是恢复 PCG 生成器的状态，而不是 lehmer64 生成器。后者只是一个附带的研究课题。恢复 PCG64 的状态要困难得多；作者估计需要大约 20,000 CPU 小时。论文表明，作为他们主要目标研究过程的一部分所采用的技术，可以快速恢复 lehmer64 的状态。

使用线性代数恢复 Mersenne Twister 的内部状态

测试 PCG 随机数生成器

随机数生成器测试

[1] Charles Bouillaguet, Florette Martinez, and Julia Sauvage. Practical seed-recovery for the PCG Pseudo-Random Number Generator. IACR Transactions on Symmetric Cryptology. ISSN 2519-173X, Vol. 2020, No. 3, pp. 175–196.

需要完整排版与评论请前往来源站点阅读。

lehmer64 的实现

利用 lehmer64 的漏洞

相关文章