使用机器学习破解随机数生成器 – 第 1 部分：xorshift128

大纲

• 一、简介
• 2. xorshift128 PRNG 是如何工作的？
• 3. 神经网络和异或门
• 4. 使用神经网络对 xorshift128 PRNG 进行建模
  • 4.1 神经网络模型设计
  • 4.2 模型结果
  • 4.3 模型深潜
• 5. 创建抗机器学习版本的 xorshift128
• 六，结论

一、简介

这篇博文提出了一种使用机器学习破解伪随机数生成器 (PRNG) 的方法。在这里破解，我们的意思是我们可以在不知道种子的情况下使用先前生成的数字来预测随机数的序列。我们首先打破了一个简单的 PRNG，即 XORShift，遵循发表在[1]中的帖子。我们从那篇文章中提出的模型中简化了神经网络模型的结构。此外，我们实现了更高的准确度。本博客旨在展示如何训练机器学习模型，该模型可以在不知道种子的情况下生成随机数时达到 100% 的准确率。我们还深入研究了经过训练的模型，以展示它是如何工作的，并从中提取有用的信息。

在提到的博客文章[1] 中，作者使用深度学习模型在没有 PRNG 种子的情况下以高精度复制了xorshift128 PRNG 序列。训练后，该模型可以使用任意连续四个生成的数字来复制相同的 PRNG 序列，并且按位精度大于 95%。该实验的实施细节和最佳训练模型可以在[2]中找到。 

乍一看，这似乎有点违反直觉，因为机器学习算法背后的整个想法是从数据中的模式中学习以执行特定任务，范围从监督学习、无监督学习到强化学习。另一方面，伪随机数生成器的主要思想是生成随机序列，因此这些序列不应该遵循任何模式。因此，（一开始）训练一个从数据模式中学习的机器学习模型（从不应该遵循任何模式的 PRNG 中学习）没有任何意义。不仅学习，而且获得 95% 的位精度，这意味着该模型将生成 PRNG 的精确输出，并且平均只会出错两位。所以，这怎么可能？为什么机器学习可以破解 PRNG？我们甚至可以比 95% 的位精度更好吗？这就是我们将在本文其余部分讨论的内容。让我们首先检查 xorshift128 算法。

**编者注：这与安全性有何关系？虽然这项研究着眼于非加密 PRNG，但我们一般有兴趣了解基于深度学习的方法如何在假定生成随机输出的函数中查找潜在模式，这是尝试使用深度学习的先决条件在密码（P）RNG 中找到以前未知的模式，因为这可能会作为对这些函数进行密码分析的有趣补充方法。在这里，我们展示了我们开始探索这个空间的工作。**

2. xorshift128 PRNG 是如何工作的？

要了解机器学习 (ML) 是否可以破解 xorshift128 PRNG，我们需要了解它的工作原理并检查它是否遵循任何模式。让我们从深入研究 xorshift128 PRNG 算法的实现开始，了解它是如何工作的。该算法的代码实现可以在 Wikipedia 上找到并在[2]中共享。这是 repo 中用于生成 PRNG 序列（用于训练 ML 模型）的函数：

def xorshift128():
    '''xorshift
    https://ja.wikipedia.org/wiki/Xorshift
    '''

    x = 123456789
    y = 362436069
    z = 521288629
    w = 88675123

    def _random():
        nonlocal x, y, z, w
        t = x ^ ((x << 11) & 0xFFFFFFFF)  # 32bit
        x, y, z = y, z, w
        w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))
        return w

    return _random

从代码中我们可以看出，实现很简单。它有四个内部数字，x、y、z和w，同时代表种子和 PRNG 的状态。当然，我们可以更新这个生成器实现，为种子提供不同的函数调用，而不是对其进行硬编码。每次我们调用生成器时，它都会按如下方式移动内部变量：y → x，z → y和w → z。w的新值 是通过对x和w 的旧值应用一些位操作（移位和异或）来评估的。新的w然后作为随机数生成器的新随机数输出返回。让我们调用函数输出o。 

使用此代码，我们可以导出输出的每个位的逻辑表达式，这导致我们得到输出的以下输出位表示o：

O ₀ = W ₀ ^ W ₁₉ ^ X ₀ ^ X ₈

O ₁ = W ₁ ^ W ₂₀ ^ X ₁ ^ X ₉

.

.

O ₃₁ = W ₃₁ ^ X ₂₀  ^ X ₃₁

其中 O _i是输出的第 i^位，符号^是按位异或。该算法的示意图如下图所示：

我们可以从这个算法中注意到，我们只需要w和x来生成下一个随机数输出。当然，我们需要y和z来生成随机数，但是o的值仅取决于x和w。

所以在理解了算法之后，我们可以看到最后四个生成的数字和下一个之间的简单关系。因此，如果我们知道这个 PRNG 生成的最后四个数字，我们可以使用该算法生成整个序列；这可能是该算法在密码学上不安全的主要原因。尽管算法生成的数字似乎是随机的，它们之间没有明确的关系，但具有算法知识的攻击者可以使用任意四个连续生成的数字来预测 xorshift128 的整个序列。由于这篇文章的目的是展示 ML 模型如何学习样本 PRNG 中的隐藏关系，我们假设我们只知道新生成的数字与其后四个数字之间存在某种关系，而不知道算法。

稍微回到主要问题：机器学习算法能否在不知道其实现的情况下仅使用最后四个输入来学习生成 xorshift128 PRNG 序列？

为了回答这个问题，让我们首先介绍一下人工神经网络（简称 ANN 或 NN）以及它们如何对 XOR 门进行建模。

3. 神经网络和异或门

神经网络 (NN)，又名多层感知器 (MLP)，是最常用的机器学习算法之一。它由称为神经元或感知器的小型计算单元组成，它们被组织成一组未连接的神经元，称为层。这些层相互连接以形成从 NN 的输入到其输出的路径。下图是2层NN的简单例子（输入层不计）。NN 的数学公式的细节超出了本文的范围。

在从输入数据训练 NN 时，神经元之间的连接（即权重）要么变得更强（高正值或低负值）以表示两个神经元之间的高正/负强连接，要么变得更弱（接近0) 表示完全没有联系。在训练结束时，这些连接/权重对存储在 NN 模型中的知识进行编码。 

用于描述 NN 如何处理非线性数据的一个示例是 NN 用于对双输入 XOR 门进行建模。选择二输入异或函数的主要原因是，虽然它很简单，但它的输出不是线性可分的[3]。因此，使用具有两层的 NN 是表示两个输入 XOR 门的最佳方式。下图（来自Abhranil 博客 [3]）显示了我们如何使用两层神经网络来模拟双输入 XOR。线上的数字是权重，节点内的数字是阈值（负偏差）并假设使用阶跃激活函数。

如果我们有两个以上的 XOR 输入，我们将需要增加隐藏层（中间的层）中的节点数量，以便能够表示 XOR 的其他组件。 

4. 使用神经网络对 xorshift128 PRNG 进行建模

基于我们在上一节中讨论的内容以及我们对 xorshift128 PRNG 算法如何工作的理解，现在 ML 可以学习 xorshift128 PRNG 算法遵循的模式是有意义的。我们现在还可以决定如何构建神经网络模型来复制 xorshift128 PRNG 算法。更具体地说，我们将使用只有一个隐藏层的密集神经网络，因为这就是我们表示在 xorshift128 算法中实现的任何 XOR 函数集所需的全部内容。与[1]中建议的模型相反，我们认为没有任何理由使用像 LSTM（“长短期记忆”，一种递归神经网络）这样的复杂模型)，特别是所有输出位都直接连接到具有 XOR 函数的输入位集合，正如我们之前所展示的，并且不需要像在 LSTM 中那样保留内部状态。

4.1 神经网络模型设计 

我们提出的模型将在输入层有128 个输入来表示最后四个生成的整数，每个 32 位，在输出层有32 个输出 来表示下一个 32 位随机生成的数字。我们需要决定的主要超参数是隐藏层中神经元/节点的数量。我们不希望少数节点不能代表所有 XOR 函数术语，同时我们不希望使用大量不会使用的节点，这会使模型复杂化并增加训练量时间。在这种情况下，根据输入、输出的数量和 XOR 函数的复杂性，我们做出了有根据的猜测并使用了1024隐藏层的隐藏节点。因此，我们的神经网络结构如下（忽略输入层）：

_________________________________________________________________
层（类型）输出形状参数#   
==================================================== ================
密集（密集）（无，1024）132096    
_________________________________________________________________
dense_1（密集）（无，32）32800     
==================================================== ================
总参数：164,896
可训练参数：164,896
不可训练参数：0
_________________________________________________________________

可以看到，隐藏层的参数（权重和偏置）个数为 132,096（128×1024 个权重 + 1024 个偏置），输出层的参数个数为 32,800 个（1024×32 个权重 + 32偏差），总共需要训练164,896 个参数。与[1]中使用的模型比较：

_________________________________________________________________
图层（类型） 输出形状参数 #   
==================================================== ================
lstm (LSTM)（无，1024）4329472   
_________________________________________________________________
密集（密集）（无，512）524800    
_________________________________________________________________
dense_1（密集）（无，512）262656    
_________________________________________________________________
dense_2（密集）（无，512）262656    
_________________________________________________________________
dense_3（密集）（无，512）262656    
_________________________________________________________________
dense_4（密集）（无，512）262656    
_________________________________________________________________
dense_5（密集）（无，32）16416     
==================================================== ================
总参数：5,921,312
可训练参数：5,921,312
不可训练参数：0
_________________________________________________________________

这个复杂的模型有大约600 万个参数需要训练，这将使模型训练更加困难，并且需要更长的时间才能获得好的结果。它也很容易被困在那个巨大的 600 万维空间中的一个局部最小值中。此外，存储此模型并稍后提供服务将使用存储/服务模型所需空间的36 倍。此外，模型参数的数量会影响训练模型所需的数据量；参数越多，训练它需要的输入数据就越多。

该模型的另一个问题是使用的损失函数。我们的目标是获得尽可能多的正确位；因此，在这种情况下最适合使用的损失函数是“ binary_crossentropy ”，而不是“ mse ”。在不涉及这两个损失函数的数学的情况下，可以说我们不在乎输出是 0.8、0.9 还是 100。我们只关心该值是否超过了某个阈值以被视为一个或不被视为零。该模型中参数的另一个非最佳选择是输出层的激活函数。由于输出层包含 32 个神经元，每个神经元代表一个位，其值应始终为 0 或 1，因此对于这些类型的节点最合适的激活函数通常是sigmoid功能。相反，该模型使用线性激活函数来输出从 -inf 到 inf 的任何值。当然，我们可以将这些值设置为阈值以将它们转换为 0 和 1，但该模型的训练将更具挑战性并且需要更多时间。 

对于其余的超参数，我们使用了与[1]中的模型相同的参数. 此外，我们使用与其他模型相同的输入样本，其中包括从上述 PRNG 函数中采样的大约 200 万个随机数用于训练，以及 10,000 个随机数用于测试。训练和测试随机数样本形成一个四方序列的随机数作为模型的输入，下一个随机数作为模型的输出。值得一提的是，我们认为我们不需要那么多数据来达到我们所达到的性能；我们只是试图与引用的文章保持一致。稍后，我们可以通过实验来确定足以生成训练有素的模型的最小数据量。下表总结了我们模型与[1]中提出的模型相比的模型参数/超参数：

	[1]中的 NN 模型	我们的模型
型号类型	LSTM和密集网络	密集网络
#图层	7	2
#神经元	1024 LSTM 2592密集	1056 密集
#可训练参数	5,921,312 （4,329,472 仅来自 LSTM 层）	164,896
激活函数	隐藏层：  relu 输出层：线性	隐藏层：relu 输出层：sigmoid
损失函数	毫秒	二元交叉熵

我们提出的模型与[1]中的帖子模型之间的比较

4.2 模型结果

经过几个小时的模型训练和超参数优化，NN 模型已经达到了100%的按位训练精度！当然，我们通过模型运行测试集，我们得到了相同的结果，并且具有 100% 的位精度。为了对我们取得的成就更有信心，我们生成了一个包含 100,000 个随机数的新样本，其种子与用于生成先前数据的种子不同，并且我们得到了相同的 100% 位精度结果。值得一提的是，虽然参考文章达到了95%+ 按位精度，这看起来是一个很有希望的结果。然而，当我们评估模型精度（相对于位精度）时，即它能够在不翻转任何位的情况下生成精确的下一个随机数，我们发现模型的精度下降到26% 左右。与我们的模型相比，我们有100%的准确率。95%+ 按位并不像它可能出现的那样仅在 2 位上失败（32 位的 95% 小于 2），而是这些 5% 的错误分散在14 位中。换句话说，尽管参考模型的按位精度为95%+，但只有 18 位是 100% 正确的，平均而言，其余 14 位中的 2 位会被模型更改。

下表总结了两种模型的比较：

	[1]中的 NN 模型	我们的模型
位精度	95 % +	100 %
准确性	26 %	100 %
位可以翻转（共 32 个）	14	0

模型精度比较

在机器学习中，获得 100% 的准确率通常不是好消息。这通常意味着要么我们没有很好地表示整个数据集，要么我们过度拟合样本数据的模型，要么问题是确定性的，它不需要机器学习。在我们的例子中，它接近于第三种选择。xorshift128 PRNG 算法是确定性的；我们需要知道哪些输入位用于生成输出位，但是连接它们的函数 XOR 是已知的。所以，在某种程度上，这个算法很容易被机器学习破解。因此，对于这个问题，获得 100% 准确的模型意味着 ML 模型已经学习了输入和输出位之间的位连接映射。所以，如果我们从这个算法中得到任何结果的四个随机数，

4.3 模型深潜

本节将深入研究该模型，以了解它从 PRNG 数据中学到的更多内容，以及它是否符合我们的预期。 

4.3.1 模型第一层连接

如第 2 节所述，xorshift128 PRNG 使用最后四个生成的数字来生成新的随机数。更具体地说，xorshift128 PRNG 的实现仅使用四个数字中的第一个和最后一个数字w和x来生成新的随机数o。所以，我们要检查连接128的权重输入，最后四个生成的数字合并，从输入层到隐藏层，我们训练的模型的 1024 个隐藏节点，以查看它们的连接强度，因此我们可以验证哪些位用于生成输出。下图显示了将每个输入（以 x 轴表示）连接到隐藏层中的 1024 个隐藏节点的 y 轴上的权重值。换句话说，图上的每个点代表从任何隐藏节点到 x 轴输入的权重：

正如我们所看到的，很少有隐藏节点连接到其中权重大于~2​​.5 或小于~-2.5 的输入之一。其余在 -2 和 2 之间的低权重节点可以认为是未连接的。我们还可以注意到位 32 和 95 之间的输入没有连接到任何隐藏层。这是因为我们之前所说的 xorshift128 PRNG 的实现仅使用来自输入的x（从 0 到 31 的位）和w（从 96 到 127 的位），而另外两个输入y 和z表示来自 32 的位到 95，不用于生成输出，这正是模型学到的。这意味着模型已经从训练阶段给出的数据中准确地学习了该模式。

4.3.2 模型输出解析

与我们在上一节中所做的类似，下图显示了将每个输出（以 x 轴表示）连接到隐藏层中的 1024 个隐藏节点的权重：

就像我们之前的观察一样，每个输出位只连接到隐藏层的极少数节点，可能除了第 11 位之外，它的决定性较小，可能需要更多的训练才能减少出错的可能性。我们现在要检查的是这些输出位是如何连接到输入位的。我们将在这里只探索第一部分，但我们可以以同样的方式完成其余部分。如果我们只关注图中的第 0 位，我们可以看到它只连接到来自隐藏层的五个节点，两个具有正权重，三个具有负权重，如下所示：

那些连接的隐藏节点是120、344、395、553和788。尽管这些节点看起来是随机的，但如果我们绘制它们与输入的连接，我们会得到下图：

正如我们所看到的，很少有位会影响我们在图中圈出的那些隐藏节点。它们是位 0、8、96 和 115，如果我们将它们以 32为模，我们会从第一个数字x中获得位 0 和 8，从第四个数字w中获得 0 和 19 位。这与我们在第 2 节中推导出的 xorshift128 PRNG 函数相匹配，输出的第一位是这些位的 XOR，O ₀ = W ₀ ^ W ₁₉ ^ X ₀ ^ X ₈. 我们期望具有一个输出节点的五个隐藏节点类似于这四个输入位的 XOR 功能。因此，如果给定足够的训练数据，ML 模型可以学习任意输入位集合的 XOR 函数。

5. 创建抗机器学习版本的 xorshift128

在分析了 xorshift128 PRNG 的工作原理以及 NN 如何轻松破解它之后，我们可以建议对算法进行简单的更新，使其更难使用 ML 破解。这个想法是在种子中引入另一个变量，它将决定：

1. 要使用x、y、z和w中的哪些变量来生成o。
2. 将这些变量中的每一个移位多少位。
3. 向左或向右移动这些变量的方向。

这可以用少于 32 位的二进制编码。例如，在前面显示的示例代码中，只有w和x变量生成输出，可以二进制编码为 1001。变量 w 向右移动 11 位，可以二进制编码为 01011 0，其中最低有效位，0，代表正确的方向。变量 x 向右移动 19 位，可以二进制编码为 10011 1，其中最低有效位 1 表示向左方向。这种表示将占用 4 位 + 4×6 位 = 28 位。当然，我们需要确保选择变量的 4 位不具有以下值：0000、0001、0010、0100 和 1000，因为它们会选择一个或没有变量进行异或。 

使用这个简单的更新将增加 PRNG 算法实现的小复杂性。它仍然会使 ML 模型只学习一个可能的序列，其中大约 1600 万个不同的序列是用相同的算法和不同的种子生成的。好像机器学习只会学习算法的种子，而不是算法本身。请注意，此更新的目的是使算法对 ML 攻击更具弹性，但结果 PRNG 的其他属性，例如周期性，还有待研究。

六，结论

这篇文章讨论了 xorshift128 PRNG 的工作原理以及如何构建一个机器学习模型，该模型可以从 PRNG 的“随机”生成的数字中学习，从而以 100% 的准确度预测它们。这意味着，如果 ML 模型可以访问从此 PRNG 生成的任何四个结果数，它可以生成确切的序列而无需访问种子。我们还研究了如何设计一个最能代表这个 PRNG 的 NN 模型。以下是从这篇文章中学到的一些教训：

1. 尽管 xorshift128 PRNG 在人类看来似乎不遵循任何模式，但机器学习可用于预测算法的输出，因为 PRNG 仍然遵循隐藏模式。
2.  应用深度学习来预测 PRNG 输出需要了解特定底层算法的设计。
3. 大型复杂的机器学习模型不一定会获得比简单模型更高的准确性。
4. 简单的神经网络 (NN) 模型可以轻松学习 XOR 函数。

本文中概述的用于训练和测试模型的 Python 代码以Jupyter笔记本的形式在此存储库中共享。请注意，此代码基于[1]中的帖子中共享的旧版本代码，并在此帖子中解释了更改。这样做是为了保持相同的数据和其他参数不变，以便进行公平比较。