有多少简单的操作对全人类来说是安全遥不可及的?

信息安全 密码学 研究 理论
2021-08-20 22:52:30

密码原语通常断言一些安全级别,作为发起攻击的操作数。例如,散列函数为碰撞攻击、原像攻击和第二原像攻击提供不同的安全级别。根据这些,为不同的原语派生了“安全”密钥大小。

对于安全密钥大小和估计未来执行计算能力的许多不同方法有许多不同的建议。例如,www.keylength.com 结合了很多这些建议。

然而,我正在寻找的是在可预见的未来显然被视为全人类无法企及的简单操作的数量——或者实际上,仍然是可信的最低值。

很明显,2^256 个简单的操作是永远达不到的。也很明显,可以达到 2^64 次简单操作,因为它已经是。许多建议似乎将 2^128 计算为一个可以安全使用 30 年或更长时间的数字。所以我正在寻找的值可能在 2^128 和 2^256 之间。2^160 或 2^192 可能是安全的遥不可及。

但我想要可以很容易推理的具体论点。我很想看到基于简单物理定律或与宇宙具体常数的关系的论点。例如,可以使用朗道尔原理。

注意:实际使用的简单操作与此处无关 - 它们可能是量子计算机上的操作,或哈希调用,或其他任何东西。

4个回答

作为起点,我们将考虑每个基本操作都意味着最小的能量消耗;兰道尔原理将该极限设定为 0.0178 eV,即 2.85×10 -21 J。另一方面,太阳系的总质量,如果全部转换为能量,将产生大约 1.8×10 47 J(实际上是根据此页面,您将从太阳的质量中得到什么,但太阳在太阳系总质量中占据了狮子的份额)。这意味着大约 6.32×10 68个基本计算的硬限制,即大约 2 225.2(我认为这种计算已经由 Schneier 在“应用密码学”中提出。)

当然,这是一个非常极端的情况,特别是,我们不知道如何将质量转化为能量——核裂变和聚变只将一小部分可用质量转化为能量。

让我们看一个更世俗的观点。假设使用现有技术,每个基本操作都必须以某种方式暗示至少一个逻辑门的切换,这似乎是公平的。单个CMOS栅极的开关功率约为C×V 2,其中C是栅极负载电容,V是栅极工作的电压。到 2011 年,非常高端的栅极将能够在 0.5 V 的电压和几飞法拉的负载电容下运行(“femto”的意思是 10 -15)。这导致每次操作的最低能耗不低于 10 -15 J。目前世界总能耗约为 500 EJ (5×10 20J)每年(或者这篇文章这么说)。假设地球的总能量生产转移到一次计算十年,我们得到的极限是 5×10 36,接近 2 122

然后你必须考虑技术进步。鉴于当前生态问题和石油峰值的趋势,未来几年的能源总产量应该不会增加太多(比如说到 2040 年不会超过 2 倍——这已经是生态学家的噩梦了)。另一方面,集成电路的设计也有技术进步。摩尔定律指出,每两年可以在给定芯片表面上安装两倍数量的晶体管。一个非常乐观的观点是,晶体管数量的翻倍可以在恒定能耗的情况下完成,这将转化为每两年将基本操作的能源成本减半。这将导致总计2 138在 2040 年——这是一次为期十年的计算,它调动了整个地球的所有资源。

所以“128 位对未来几十年来说绰绰有余”的普遍智慧并没有消失(这完全取决于你认为什么是“安全”遥不可及的,但我自己的偏执水平对于 128 位来说是相当平静的“只要”)。

关于量子计算机的说明:一个 QC 在一次“操作”中可以做很多事情。通常的表现是 QC 执行“同时执行多个计算,我们在最后过滤掉这些计算”。这个断言在许多细节上是错误的,但它仍然包含一些事实:QC 应该能够在2 n/2 个基本量子操作中攻击n位对称密码术(例如,使用n位密钥的对称加密) 。因此经典的技巧是:考虑到量子计算机(如果它们曾经存在的话),将密钥长度加倍。因此 AES 具有 256 位密钥,SHA-512 ...(AES 的 256 位密钥并非旨在防止假设的量子计算机,但这就是如今 256 位密钥的合理性)。

注意:实际使用的简单操作与此处无关 - 它们可能是量子计算机上的操作,或哈希调用,或其他任何东西。

嗯,一台量子计算机是没有人能告诉你“在可预见的未来显然被认为是全人类无法企及的简单操作的数量”的原因。根据定义,量子计算机执行与“实际简单操作”相反的操作;它允许人们通过量子诡计绕过大部分“简单操作”空间。一旦存在绕过部分简单操作空间的计算机,那么您关于“空间需要多大”的问题就会变得不可预测地无关紧要。

无论如何,这就是理论。我们还没有达到量子计算机可以做我们认为它们应该做的事情的未来水平。虽然我很乐意说这样的量子计算机确实存在并且不存在于某个地方的盒子中。

最近要在此处添加的可能与该问题相关的一件事是,朗道尔原理可能实际上并不成立:

http://phys.org/news/2016-07-refutes- Famous-physical.html

他们测量了“或”门(这显然是一个逻辑上不可逆的门)运行期间耗散的能量,并表明逻辑运算可以以低至 kBT ln2 预期极限的 5% 的能量执行。 . Nature Communications 文章的结论是,以零能量消耗操作计算机没有基本限制和可逆逻辑。

为什么花了这么长时间才发现这一点?部分原因是该实验必须达到超凡的灵敏度,才能证明可以突破朗道尔极限:超过 10 到 21 焦耳,其中 1 焦耳是把苹果举到离地 1 米以上所需的能量。这是非常少量的能量。

尽管我非常喜欢@thomas-pornin 的回答,但我认为必须指出的第一个假设存在问题。

Laundauer 原理仅适用于不可逆操作。

与某些人可能假设的相反,可逆计算已经可以实现。这些操作在量子计算机和同态加密系统中很常见。

更具体地说,给定的哈希算法可以使用像 XOR 这样的操作来混合两位并破坏关于哪个是 1 和哪个是 0 的信息,但是像 Fredkin Gate 中的 CNOT (wiki)是产生 XOR 结果的可逆等价物和一个区分控制位。如果保留该数据,则可以自由地反转操作。如果它被销毁而只留下 XOR,则适用 Landauer 原理。

正如其他人所指出的那样,量子计算正在改变事物,但那是因为它使用 CNOT 门而不是与量子位的 XOR,留下控制位以保持量子叠加状态并执行操作,而不会花费 Landauer 破坏它的成本。

因此,如果输出状态被折叠,那么散列的位(例如)以能量成本被破坏,以匹配已知输出,除了探测每个位的值之外,不需要额外的成本来计算输入。

最低限度,这应该至少需要哈希中的位数,以及至少输入数据中的位数。对于给定的哈希算法,计算一个块的摘要可能需要比数据本身更多的 XOR/CNOT 操作,这些都必须加起来。

对于1 Gigabit的 SHA-256 (wiki) ,即 256 位的输出散列、1 Gb 的输入,以及 512 位块的每个 32 位部分的 16 次和/加/异或操作,再加上 8 个 32 位相加折叠当前值;或 33Kbits。

如果你有 ~2Terabits 的数据存储在 qubits 中,并且每比特 ~10 -15 J 来设置问题和询问状态,你可以反转那个哈希。

嗯,不完全相反。您可以找到产生该输出哈希的所有 1 千兆位大小的输入的集合,并开始花费更多每位来选择其中一个。

根据安全需要,碰撞可能就足够了。

(编辑)最近,研究人员发表了一种不可逆的原始操作,要求小于引用的限制,这意味着原始计算存在错误。