使用多台计算机进行更快的蛮力

信息安全 加密 AES 蛮力 钥匙
2021-08-28 03:45:36

我最近看了 Mr. Robot 并且不能停止思考为什么解密使用 256 位密钥的 AES 加密加密的文件如此困难。
让我们说找到密钥的唯一方法是通过蛮力。
我们不能设置一台计算机从第一个可能的键开始暴力破解,另一台从最后一个可能的键开始,也许有几台计算机尝试中间的键吗?
这不会大大减少时间吗?

3个回答

当然这是可能的,但它并没有真正的帮助。可能性的数量太大了。

考虑一个256位密钥有 2256 个可能的值。那是 12✕10 76,或 12 后跟 76 个零。如果我们慷慨地假设一台计算机每秒可以测试一万亿个(即 10 12)个可能的密钥,并且我们有一万亿台计算机(我们从哪里得到它们?)执行密钥搜索,则需要 12✕10 76 / (10 12 ✕10 12 ) 秒来搜索整个键空间。那是 12✕10 52秒。由于一个世纪只有 3,155,760,000 秒,因此尝试所有可能的密钥大约需要 4✕10 43个世纪。有 50 到 50 的机会在一半的时间内找到钥匙。

这就是加密的设计方式。可能性的数量太大而无法及时破解,这对人类来说很有趣。

我曾经计算过这个。假设 AES 只能使用蛮力破解。显然,我们需要一个计数器,它从 0 计数到 2 256-1,平均而言它需要计数到 2 255运行此计数器需要能量。需要多少能量?

事实证明,这里有一个热力学极限,即朗道尔原理。在给定的温度下,设置一个位(1位熵)所需的能量最少,因为如果我们不花费那么多能量,我们实际上可以降低系统的熵,这在热力学上是不可能的。它消耗的能量为 kT ln 2,其中 k 是玻尔兹曼常数 (1.38×10 -23 J/K),T 是以开尔文为单位的温度。显然,我们希望以尽可能经济的方式做到这一点,所以让我们以 3 开尔文进行计算,这大致是宇宙背景辐射的温度。如果不花费比翻转位更多的能量来冷却系统,我们将无法获得比这更酷的效果!这将翻转一点的能量成本固定在 2.87×10 -23 焦/比特。

现在,我们需要多少位翻转?答案会很多,所以为了让能量保持在人类可以理解的范围内,我想简化这个问题。与其解决 AES-256,不如假设我们正在解决 AES-192,它只需要数到 2 191那么我们需要多少位翻转呢?如果我们用正常的二进制计数,我们可能需要在计数器的每个增量中翻转多个位。计算起来很烦人,所以假设我们可以用格雷码来做这个计数器,每次增量只会翻转一位。

以 2.87×10 -23 J/bit将计数器递增 2 191次会产生 9×10 34 J。这是很多能量。事实上,如果我访问我最喜欢的 Wikipedia 页面之一,Order of Magnitude(能量),我们会看到我们的太阳每年发出的能量是 1.2×10 34 J。没错。仅运行将成为 AES 破坏过程核心的计数器就需要将近十年的太阳能量输出的总和。所有的。

现在,如果我们重新审视最初的 AES-256 问题,能源成本会增加 2 64因此,该计数器将需要 1.6×10 54 J。再次查看数量级(能量),我们发现银河系中的总可见质量能量为 4×10 58 J。因此,如果你要转换 0.004星系总质量能量的百分比(即使用 E=mc 2将所有质量转换为能量),您可以运行一个可以从 0 计数到 2 255的计数器。

这就是为什么人们永远不会强行使用现代加密算法的原因。所要求的能量数量实际上处于“宇宙热寂”的水平。

这不仅是可能的,人们实际上已经成功地做到了这一点。但只有非常短的键。

2002 年, distributed.net通过使用分布式计算机网络成功破解了 64 位 RC5 加密。这些电脑大多是由志愿者拥有的消费级个人电脑,他们在后台安装了一个程序来破解密钥。这是RSA 密钥挑战的一部分- RSA 实验室的竞赛,旨在解密使用比您在现实世界中使用的密钥短得多的密钥加密的消息。

“经过四年多的努力、数十万参与者和数百万 cpu 小时的工作,Distributed.net 已经暴力破解了 RSA Security 的 64 位加密挑战的关键”

他们在 2003 年开始了另一个赢得 RSA 72 位挑战的项目。13 年后,他们仍在计算,甚至没有测试 4% 的密钥空间

请记住,这些是极其简化的 RSA 版本。现实世界中 RSA-RC5 的推荐密钥长度至少为128 位。每增加一个位,计算时间就会增加一倍,因此这些分布式方法距离攻击任何现实世界的加密还有很长的路要走。