Press "Enter" to skip to content

神经网络与随机数的安全性分析(下)

 

写在前面的话

 

在《神经网络与随机数的安全性分析(上)》中,我们对随机数发生器(RNG)的安全方面进行了讨论,后续内容我们将在《神经网络与随机数的安全性分析(下)》中与大家继续讨论这一方面的内容。

 

继续我们的话题

 

书接上文,既然我们已经知道了随机数生成器(RNG)的一些矛盾点,这就导致了很多由通用原语构造出来的动态随机数生成器(RNG)出现。这种随机数生成操作需要重复地对一个固定的输出列表来进行反复操作,这意味着我们平时在随机数生成器上做的事情还远远不够。按位运算(将两个数字转换成二进制表示,并对其进行移位或以其他方式进行转换)与模运算和群论等知识的结合,乍看之下似乎是能够创建出看似无法预测的随机数。比如说,大家可以简单看看3701687786、458299110、2500872618和3633119408有什幺共同之处幺?实际上,它们是我Xorshift128实现的前四个输出,但据我所知,它们或多或少都有一定的关联。即便是它们没有更加安全的密码学保证或严格的数学保证,即使它们跟序列中其他两百多万个相邻的数字看似无关,但实际上它们都是可预测的。

 

这并非不可能,只是有些困难罢了。因为从数学意义上来说,这些函数通常是可逆的,它们的压缩位特性使它们成为了SAT解析器的目标。然而,对于大多数真实世界里的应用程来说序,可预测性也因一些相互关联的因素而或多或少地变得不太可行了。比如说:

 

·编码 – 现在各种各样的应用程序都会使用RNG,它们都有关于编码的各种方案。有些是制作六位数双因素认证令牌,有些则是输出32个字符的十六进制会话令牌。另外,在应用程序封闭源代码的情况下,这种编码的性质就不一定很清楚了。除此之外,我们也无法得知如何提高特定随机数的熵。

 

·转换 – 另一个问题是其他熵保持变化也是有可能的,位顺序可能只是由于某种原因而颠倒,或者开发人员决定用“TIMROX”或其他什幺来异或输出。或者它只是乘以2。

 

·连续性 – 以上两种假设都假设你能在算法的输出中获得完美的效果,但其实这并不常见,因为通常一个应用程序的随机输出被不同的互斥用户组使用,你不会看到另一个用户的会话或双因素身份验证令牌。

 

这些潜在的问题是非常重要的,但它们并不是我认为最困难的部分,因为我们可以让一个神经网络首先取学习这些问题的关键核心点。所以我决定从这里开始,即我上面提到的Xorshift128 拥有128位状态和32位输出,但如果不查看状态的话,我们如何才能进行攻击呢?

 

数学方法论

 

在思考了一段时间后,这些问题最终在我的大脑中凝结成了有用的东西。下面给大家看一个函数F:statet-1->(statet,outputt),这也就意味着当前状态跟之前是确定的了。因此,我们可以尽可能多地去采用这种方法。比如说,F:statet-4->(outputt-3,outputt-2,outputt-1,outputt,statet)。这里有两个有意思的地方:

 

首先,我们有充分的理由相信,通过这个函数输出的每个状态正好可以与一组的四个输出对齐。很明显,在输出和状态之间没有一对一的关系,因为对于给定的步骤,输出是32位的,而状态是128位的。所以我们需要的最小输出数量是4,如果我们想唯一地映射这些输出。我们还需要更多吗?如果RNG设计良好,可能不会。

 

其次,如果你接受我的观点,即状态和输出序列是唯一联系的,那幺你根本不需要考虑状态了。也就是说,如果你愿意相信Xorshift128的后续4个32位输出被唯一地映射到给定的128位状态,那幺你根本不需要考虑状态。每个4位数字的唯一序列在整个2**128位状态中只会出现一次,因此如果你能知道它们,并且能够预测这种状态的话,那你就可以很容易地预测出下一个数字了。

 

经过上述思考,接下来需要弄清楚的就是如何让神经网络来学习上述功能。也就是说,F:(outputt-4,outputt-3,outputt-2,outputt-1)->(outputt),它只能预测Xorshift128 给定的前四个输出的输出结果。这就非常有意思了:

大量的数据 – 我可以相对容易地生成2万亿个训练示例,而且数据中没有噪音。
均匀的数据分布 – 所有的数据也相对均匀地分布在问题空间中。这意味着过度拟合的可能性相对较小,因为输入和输出具有比较复杂的关系。
模型设计非常简单 – 几乎任何两个比特之间都可能发生一些复杂和不可预测的比特变化。还有一种隐藏状态,我们想通过序列来了解,它很好地映射到了LSTM。所以我们不需要在模型设计上有任何根本性的突破,至少乍一看是这样。

接下来,我打算把Xorshift128的每一个32位输出转换成它的二进制表示,即每个数字将被转换成一个32位的列表,而且我也知道这是几乎所有RNG代码都使用的底层表示法。另外,每一个训练示例理论上都是独立于前面4个数字之外的所有内容的,所以我们将把每个输出的列表分成这些数据的各个步长,即1,2,3,4,5,6,7,8,9变成[[1,2,3,4],[5]],([2,3,4,5],[6])。然后,将每个单独的数字转换成二进制。具体如下所示,不过在本例中,我将把它们转换为4位数字,这样更易于阅读。

 

x1 = [[0,0,0,1],[0,0,1,0],[0,0,1,1],[0,1,0,0]] #[1,2,3,4]
y1 = [0,1,0,1] #5
x2 = [[0,0,1,0],[0,0,1,1],[0,1,0,0],[0,1,0,1]] #[2,3,4,5]
y2 = [0,1,1,0] #6

 

在机器学习术语中,我们想把这个长度为N的序列分成几个张量:32×4输入张量和32×1输出张量。现在,我们需要编写一些高性能的numpy代码,在多维张量上执行数据重塑操作。

 

接下来,我们可以使用一个LSTM来捕获基于状态的依赖关系,几个密集的网络足以覆盖所有的数据变换操作,然后用32位的最终数据层完成我们的任务:

 

model.add(LSTM(units=1024,activation='relu',input_shape=(4,32,),return_sequences=False,))
for depth in range(5):
model.add(Dense(512,activation='relu'))
model.add(Dense(32))

 

下面的结果足以证明我们的想法:

 

 

这个模型实际上需要几次才能成功,之前的运行达到了75%到95%之间的峰值。

 

为此,我还专门给大家提供了一个针对Xorshift128算法的预测工具,感兴趣的同学可以下载下来使用一下。除此之外,这实际上是我第一次建立任何类型的新模型,所以我希望社区的广大同学们能够帮助我继续完善这款工具的源代码,以更好地提升其性能和预测准确率。

 

RngPredictor

 

在安装好tensorflow之后,然后把该项目的源代码克隆至本地,你就可以直接运行predictor.py脚本了。该工具的GitHub代码库地址如下:

 

GitHub传送门: https://github.com/airza/RngPredictor

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注