预测 Math.random() 数字?

信息安全 javascript 随机的 节点.js
2021-08-25 18:00:36

我正在阅读Math.random() 的文档,并找到了注释:

Math.random() 不提供密码安全的随机数。不要将它们用于与安全相关的任何事情。请改用 Web Crypto API,更准确地说是 window.crypto.getRandomValues() 方法。

是否可以预测呼叫random将产生哪些数字?如果是这样 - 这怎么能做到?

3个回答

事实上,Math.random()在密码学上并不安全。


的定义 Math.random()

ES6 规范Math.random()的定义为JavaScript 引擎中函数的实现留下了很大的自由度:

返回一个带正号的数值,大于或等于 0 但小于 1,随机或伪随机选择,在该范围内具有近似均匀的分布,使用依赖于实现的算法或策略。此函数不接受任何参数。

Math.random为不同代码领域创建的每个函数必须从连续调用中产生不同的值序列。

那么让我们看看最流行的 JavaScript 引擎是如何实现它的。


Xorshift128+XorShift 随机数生成器之一,它是最快的非密码安全随机数生成器之一。

不过,我不知道上面列出的任何实现是否受到任何攻击。但是这些实现是非常新的,并且过去存在其他实现(和漏洞),如果您的浏览器/服务器尚未更新,它们可能仍然存在。

更新:douggard 的回答解释了如何恢复状态 XorShift128+ 并预测Math.random()值。


V8 的 MWC1616 算法

2015 年 11 月,Mike Malone 在一篇博客文章中解释说,V8 的 MWC1616 算法的实现在某种程度上被破坏了:如果你使用基于 V8 的浏览器,你可以在这个测试这个测试中看到一些线性模式。V8 团队处理了它并在 Chromium 49(2016 年 1 月 15 日)和 Chrome 49(2016 年 3 月 8 日)中发布了修复程序。

这篇发表于 2009 年的论文解释了如何根据之前的输出Math.random()(MWC1616 版本)来确定 V8 的 PRNG 的状态。

这是一个实现它的Python 脚本(即使输出不连续)。

这已在对使用 Node.js 构建的投注网站CSGOJackbot 的真实世界攻击中被利用。攻击者很公平,只是取笑了这个漏洞。


缺乏划分

在 ES6 之前,Math.random()定义没有指定不同的页面必须产生不同的值序列。

这允许攻击者生成一些随机数,确定 PNRG 的状态,将用户重定向到易受攻击的应用程序(将Math.random()用于敏感事物)并预测Math.random()要返回的数字。这篇博客文章提供了一些有关如何执行此操作的代码(Internet Explorer 8 及更低版本)。

ES6 规范(已于 2015年6 月 17 日被批准为标准)确保浏览器正确处理这种情况。


选错种子

猜测为初始化序列而选择的种子也可以让攻击者预测序列中的数字。这也是一个真实世界的场景,因为它已于2012 年在 Facebook 上使用。


这篇发表于 2008 年的论文解释了由于浏览器缺乏随机性而泄露某些信息的不同方法。


解决方案

首先,始终确保您的浏览器/服务器定期更新。

然后,如果需要,您应该使用加密函数:

两者都依赖于操作系统级别的熵,并且会让您获得加密随机值。

您可以使用 Z3 定理证明器来攻击这些。为了预测彩票模拟器中的值,在 Python 中实现了这样的攻击。

如前所述,现在大多数地方都在使用 XorShift128+,这就是我们要攻击的。您从实现正常算法开始,以便您可以理解它。

def xs128p(state0, state1):
    s1 = state0 & 0xFFFFFFFFFFFFFFFF
    s0 = state1 & 0xFFFFFFFFFFFFFFFF
    s1 ^= (s1 << 23) & 0xFFFFFFFFFFFFFFFF
    s1 ^= (s1 >> 17) & 0xFFFFFFFFFFFFFFFF
    s1 ^= s0 & 0xFFFFFFFFFFFFFFFF
    s1 ^= (s0 >> 26) & 0xFFFFFFFFFFFFFFFF 
    state0 = state1 & 0xFFFFFFFFFFFFFFFF
    state1 = s1 & 0xFFFFFFFFFFFFFFFF
    generated = (state0 + state1) & 0xFFFFFFFFFFFFFFFF

    return state0, state1, generated

该算法接受两个状态变量 XOR 并将它们移动,然后返回更新状态变量的总和。同样重要的是每个引擎如何获取返回的 uint64 并将其转换为双精度值。我通过挖掘每个实现的源代码找到了这个信息。

# Firefox (SpiderMonkey) nextDouble():
# (rand_uint64 & ((1 << 53) - 1)) / (1 << 53)

# Chrome (V8) nextDouble():
# ((rand_uint64 & ((1 << 52) - 1)) | 0x3FF0000000000000) - 1.0

# Safari (WebKit) weakRandom.get():
# (rand_uint64 & ((1 << 53) - 1) * (1.0 / (1 << 53)))

每个都有点不同。然后,您可以获取 Math.random() 产生的双精度并恢复算法产生的 uint64 的一些低位。

接下来是在 Z3 中实现代码,以便可以象征性地执行它并且可以求解状态。有关更多上下文,请参阅 Github 链接。它看起来与普通代码非常相似,只是您告诉求解器低位必须等于从浏览器恢复的低位。

def sym_xs128p(slvr, sym_state0, sym_state1, generated, browser):
    s1 = sym_state0 
    s0 = sym_state1 
    s1 ^= (s1 << 23)
    s1 ^= LShR(s1, 17)
    s1 ^= s0
    s1 ^= LShR(s0, 26) 
    sym_state0 = sym_state1
    sym_state1 = s1
    calc = (sym_state0 + sym_state1)

    condition = Bool('c%d' % int(generated * random.random()))
    if browser == 'chrome':
        impl = Implies(condition, (calc & 0xFFFFFFFFFFFFF) == int(generated))
    elif browser == 'firefox' or browser == 'safari':
        # Firefox and Safari save an extra bit
        impl = Implies(condition, (calc & 0x1FFFFFFFFFFFFF) == int(generated))

    slvr.add(impl)
    return sym_state0, sym_state1, [condition]

如果您向 Z3 提供 3 个连续生成的双打,它应该能够恢复您的状态。下面是 main 函数的一个片段。它在 Z3 的两个 64 位整数(未知状态变量)上调用符号执行的 XorShift128+ 算法,从恢复的 uint64 中提供较低(52 或 53)位。

如果成功,求解器将返回 SATISFIABLE,您可以获得它求解的状态变量。

    for ea in xrange(3):
        sym_state0, sym_state1, ret_conditions = sym_xs128p(slvr, sym_state0, sym_state1, generated[ea], browser)
        conditions += ret_conditions

    if slvr.check(conditions) == sat:
        # get a solved state
        m = slvr.model()
        state0 = m[ostate0].as_long()
        state1 = m[ostate1].as_long()

有一个稍微详细的书面记录在这里,重点是使用这种方法来预测一个强力球模拟器中奖号码。

Math.random(和类似的其他功能)从种子开始并创建一个新数字。对用户来说,它似乎是随机的,因为当然算法是按照它看起来的方式调整的。但事实上,任何地方都没有真正的随机性来源。如果你知道生成器的内部状态(它是 100% 确定性的软件,没有什么特别的),你就会知道它生成的所有未来(并且取决于算法也可能是过去)数字。

“真正的”随机源可以是测量放射性粒子衰变之类的东西,或者在更真实的世界中,任何类型的电白噪声,或者更实际地,诸如用户移动鼠标或按键之间的微小偏差之类的东西诸如此类的事情。什么都没有Math.random

Math.random是(就像random大多数语言/库的功能一样)以这种方式设计的,并且您可以从同一种子中恢复一串“随机”数字的属性在许多情况下实际上是一个有用的功能。只是不是为了安全。