神经网络可以破解哈希算法吗?

信息安全 哈希 机器学习 人工智能
2021-08-25 02:49:41

我一直在阅读一些关于神经网络的文章,以及它们逼近许多复杂函数的能力。

难道神经网络不能破解像 SHA256 这样的散列算法吗?

例如,假设我们想要训练我们的网络来破解 8 个经过哈希处理的字符串。由于我们知道输入和预期输出,因此我们可以遍历所有排列并训练网络。从技术上讲,网络是否能够破解大量映射回 8 个字符的字符串的 SHA256 哈希?这是以前做过的吗?

4个回答

不。

神经网络是模式匹配器。它们是非常好的模式匹配器,但模式匹配器也一样。不比他们打算模仿的生物大脑更先进。更彻底,更不知疲倦,但不是更复杂。

模式必须在那里才能被发现。数据中必须存在偏差才能梳理出来。但是加密哈希是经过明确且极其精心设计的,以消除输出中的任何偏差。没有一个位比任何其他位更有可能,没有一个输出更可能与任何给定的输入相关。如果发现这样的相关性,散列将被认为是“损坏的”并且新算法将取而代之。

散列函数的缺陷之前已经被发现,但从未借助神经网络。取而代之的是对某些数学原理的仔细应用。

从不同的角度:
您可以将其简化为开放问题“是否存在用于整数分解的有效算法”。如果存在这样的算法,NN 可以通过引导证明搜索发现它,这可能会被用来破坏所有的安全性。

更新给出你的评论:

我知道这在计算上是不可行的。我只是想知道理论上是否可行(根据 tylerl 似乎不是)

是的,给定无限的时间和无限的能量,神经网络可以破解 SHA256但是(我认为这是@tylerl 的重点)因为散列函数没有可辨别的模式,神经网络无法比通过计算每个的散列来构建查找表的天真蛮力做得更好可能的字符串。这种查找表的条目(~ 2 256)比地球上的原子(~ 2 166)要多 - 所以至少以我们目前的技术水平,在内存中保存或存储这样的表是“不可能的”在任何磁盘上。同样,为了让你的神经网络表现得比掷骰子好得多,你需要的神经元数量也可能超过地球上的原子数量。

所以是的,它在计算上是不可行的,但在理论上仍然是可能的。事实上,一般来说,密码学确实可以在理论上暴力破解某些东西,但是当我们可以证明这样做需要比宇宙的生命周期更多的时间和比包含在其中的更多能量时,我们会说“足够好太阳。


我认为反驳的理由是:

由于我们知道输入和预期输出,因此我们可以通过所有排列并训练网络。

1)这与查找表有根本不同吗?

2) SHA256 的输出空间为 2 256,输入空间基本上是无限的。作为参考,自大爆炸以来的时间估计为 50 亿年,也就是大约 1.577 x 10 27纳秒,也就是大约 2 90 ns。因此,假设每次训练迭代需要 1 ns,您将需要2166个宇宙年龄来训练您的神经网络。

这里的重点是 SHA256 有 2 256个可能的输出,而 2 256是一个非常非常非常大的数字。

“神经网络可以成为散列函数的‘反函数’吗?” 或许。没有数学证据表明任何给定的散列函数,无论是 SHA 还是其他任何散列函数,都缺乏域和图像之间的模式。正如其他回答者指出的那样,哈希函数是明确设计的,因此没有已知的保留质量。如果存在某种模式,那么理论上神经网络可以找到它,但我确信它之前已经尝试过并且 SHA 仍然存在,所以我们可以假设它们不成功。我可能会提到,您必须为每个散列函数单独证明这种“缺乏模式”。

我将“反函数”放在引号中,因为散列函数需要是满射的(但是满射性通常没有被正式证明),因此可以将两个数字映射到同一个数字,因此没有真正的逆。然而,逆函数不一定是真正的函数,因为它可以返回一组数字或描述一组数字的函数。散列函数的强力逆函数将简单地返回域(例如自然数),而更复杂的逆函数将返回域的实子集。

训练神经网络实际上会很有趣:NN 返回一个函数作为输出。该函数在图像中有一些可以近似的密度,密度越低,奖励越高。现在要训练 NN,您将输入 f(x) 并检查 x <- { g(c) | c <- |N} 而 g 是 NN 作为输出返回的函数。