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

阅读量192003

|

发布时间 : 2020-11-16 10:30:19

x
译文声明

本文是翻译文章,文章原作者 airza,文章来源:airza.net

原文地址:https://www.airza.net/2020/11/09/everyone-talks-about-insecure-randomness-but-nobody-does-anything-about-it.html

译文仅供参考,具体内容表达以及含义原文为准。

 

写在前面的话

伟大的冯·诺依曼曾经说过,任何一个考虑用数学方法来生成随机数的人,脑壳都不太好使。在这篇文章中,我将使用一个神经网络来破解随机噪声,针对Xorshift128的预测位准确率可高达95%。
在此之前,我曾对客户端电子邮件令牌生成时所使用的安全代码进行过审查。老实说,我不太记得之前那些代码长啥样了,但大概意思如下:

"""gotta make a token and send it to the client!"""
very_random_number = get_random_number()
two_factor_token = convert_representation(very_random_number)
send_email("Your two factor authentication token is:"
+two_factor_token,user_email)
save_token_to_user(user_id,two_factor_token)

类似上面的这种代码增强了大部分互联网应用的安全性,如果用户想要重置他们的密码,他们就要输入自己的电子邮箱。接下来,我们将生成一个秘密代码并将其发送到用户的电子邮箱中。当用户点击了邮箱中的链接之后,也就验证了他们身份的合法性。有的时候,当用户尝试登录网上银行时,我们还会给他们发送类似的数字文本代码,而这种随机数与用户之间的关联也是基于Cookie的身份验证的主要部分。

但是,这种代码真的安全吗?没错,这需要看情况来定。当然了,我们也可以去攻击电子邮件组件,因为有的时候电子邮件并不会对发送的信息进行加密。或者说,我们也可以选择去攻击数据之间的某些关联性,因为令牌和电子邮件也可能是由攻击者控制的数据或其他东西派生出来的。在这里,随机数生成的质量也很重要,至少在理论上是这样的:一些随机数生成器是可预测的,而另一些则很难被攻击。如果我们能预测到生成的随机数,那麻烦可就大了,因为我们只需要触发将邮件发送给用户,然后以某种方式预测出生成的随机数,那用户就凉凉了。从另一方面来说,即使我们能够“预测”出随机数,剩下的事情也没那么简单,因为我们还需要了解convert_representation代表的是什么。

我认为机器学习在这方面可以给我们提供很大的帮助。事实上,这个想法早就在我的脑海里萦绕了好几年了。但是到目前为止,我还没有看到任何已有的文献能够证明这种想法是可行的,而且也没有人真正知道该如何去下手。最后,多亏了Phil Brass Weird Ideas基金会的慷慨资助,我才能够有好几个礼拜的时间能够有条不紊地去思考这个问题。

实际上,我所使用的方法其实比较简单,我将在接下来的文章中跟大家讨论如何在计算机中生成随机数字,然后讨论如何将随机性的概念转化为一个可学习的问题。除此之外,我还会尝试去解决随机数目前所面临的安全问题,然后给大家提供一个路线图,并说明如何继续缩小我当前进度与可用攻击之间的距离。

 

随机数当前的安全现状

在我看来,计算机这种“不人不鬼”的东西就是一个捉摸不透的“生物”。尽管我们可以通过各种各样的方式和条件来对计算机的行为进行严格限制,但有的时候我们又会去要求计算机的行为变化无常,因为我们人类不具备这样的能力,所以我们会要求计算机来帮我们去选择一个比数字更加疯狂的数字,也就是一个看似完全“随机”的数字。比如说,通过调用Xorshift128,这个算法允许我们选择一个介于0到40亿之间的数字(确切地说是2的32次方),当然了,如果让我们自己去选择,我们选出来的数字没有理由是绝对随机的,而且肯定会偶尔有相同的数字。不过这个算法令人吃惊的是,在遇到随机模式的重复数字之前,我们可以调用这个函数2的128次方次。

这里就存在一个问题了,别忘了文章开头的第一句话说过,噢不对,应该是冯·诺依曼提到过:编程是一门艺术,你能准确地告诉它你想让它做什么,或多或少地提前告诉它你想让它产生什么样的随机的东西,但是这两种方法首先都违背了程序的目的,而且在编程级别上也提出了非常非常大的逻辑性挑战。当然了,我们普通人可没那么多时间和精力去做40亿次某件事情,即使你做了,把这些数字全部写下来也是浪费时间浪费资源的事情。另一方面来说,如果只循环几个可用的数字,这就更不可行了,这样何来的随机性可言?如果只循环使用0到2的32次方之间的几百个整数,那么实际上也并没有提供太多的随机性。

现在,让我们暂时抛开随机性的问题,我们来从编程的角度去考虑它。我们可以将随机数发生器(RNG)定义为可以输出一系列数字的东西。为了确保它们尽可能的随机,我们还将引入一些新的东西,比如说“状态”。当“状态”被传递到这个RNG函数中时,除了输出一个随机数之外,它还将输出一个新的“状态”。接下来,我们可以把这个输出的“状态”重新传递给RNG,然后继续生成下一个随机数,然后又拿到一个新的“状态”,如此反复,最终得到我们想要的随机数字。

随机数发生器(RNG)是由冯·诺依曼(Von Neumann)在20世纪40年代的某个时候发明的,因此RNG的标准相对来说还是有点古老了。其中,需要对N位数进行平方计算,然后计算的结果中取N/2个中间数字作为输出以及下一次迭代的“状态”平方。举个简单的例子,我们取n=2,其工作原理如下:我们从43开始,平方得到1849,然后去中间的两个数字得到结果为84。此时,数字84就是我们的新“状态”,接下来继续取该“状态”的平方,得到7056,取中间值得到05,然后继续输出新的“状态”。接下来得到的就是25,这里我们标记为0025,给到我们的新“状态”为2,然后继续计算得到0004,这里就被标记成了0,以此类推…

大家看,这里我们好像进入了一个死循环。0的平方当然是0,这就好像不那么随机了。事实上,不管你从哪个数字开始,这种行为都是很糟糕的。下表列出了所有状态/输出,表明向循环方向退化的趋势是不可避免的:

对于“状态”为4位数的版本,性能更好,相关伪代码如下:

def von_neumann_generator(state):
	"""The version with a 4 digit state/output
	not to be confused with the one above, that
	has two."""

	#e.g. 1234**2->1522756
	square = state**2 

	#1522756 -> 01522756
	formattedSquare = "%08d" % square

	#01522756 -> 5227
	next_state = output = int(formattedSquare[2:6])
	return (next_state,output)
state = 1234
for i in range(20):
	state,output = von_neumann_generator(state)
	print(output)

在上面的例子中,您可以看到状态和输出是相同的,但是没有特别的原因必须这样做。例如,我们可以将状态设置为内部四个数字,输出为外部四个数字:

def much_better_von_neumann_generator(state):
	square = state**2 # e.g. 1234**2->1522756
	formattedSquare = "%08d"%square
	output = int(formattedSquare[0:2]+formattedSquare[6:])
	next_state = int(formattedSquare[2:6])
	return (next_state,output)
state = 1234
for i in range(40):
	state,output = much_better_von_neumann_generator(state)
	print(output)

虽然这个RNG还不是最安全的状态,但随机数的输出和“状态”之间的关系已经很难去预测了。然而,它们在某种因果意义上显然是相互关联的。现在,我们已经逐渐开始看到RNG设计中的一些关键矛盾点了:

不可预测性–增加输出/状态中的位数会增加输出的不可预测性。有时设计不太成熟的算法(如上面的算法)最终会退化为某种不安全的低随机性状态,但在计算机中使用的大多数算法在返回到原始状态之前,会以某种顺序简单地迭代整个状态。比如说,我们可以通过计算位数来验证生成的随机数是均匀分布的,这里就不得不提到加密安全的伪随机数发生器(CSPRNGS)。

性能–不幸的是,CSPRNGs非常慢。而高性能RNG相比来说则更为常见,几乎每个网站都在不断地向访问或登录的用户发送一系列随机数字,而在网络游戏中,它们更是无处不在。因此,仅仅使用CSPRNG并不一定是正确的。也就是说,现在使用的高性能算法比我上面演示的算法要好得多。

政治方面-这就不适合在这里详细讨论了,有些地方的当局会要求开发人员使用他们所定义的所谓的“超级安全”的RNG标准,但实际上这些标准都是存在后门的。这一点大家心里清楚就好了,毕竟之前也被曝光过。

 

后话

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

本文翻译自airza.net 原文链接。如若转载请注明出处。
分享到:微信
+11赞
收藏
WisFree
分享到:微信

发表评论

内容需知
  • 投稿须知
  • 转载须知
  • 官网QQ群8:819797106
  • 官网QQ群3:830462644(已满)
  • 官网QQ群2:814450983(已满)
  • 官网QQ群1:702511263(已满)
合作单位
  • 安全客
  • 安全客
Copyright © 北京奇虎科技有限公司 360网络攻防实验室 安全客 All Rights Reserved 京ICP备08010314号-66