密码哈希后量子安全吗？

Question

当前的计算机无法破解相当强的哈希密码，例如14个CSPRNG生成的字母数字字符(\approx80位熵)。

Grover的算法适用于我所理解的散列函数(例如在这个答案中)，这意味着如果给定128位的MD5输出，它可以在算法的\sqrt{2^{128}}=2^{64}计算中找到输入(或其中的碰撞)，为计算机提供足够的量子位。如果量子计算机能够足够快地计算MD5 (或者足够便宜，可以构建足够多的副本)，那么无论用户的密码有多强，这都会完全破坏MD5。

然而，要找到通过256位(或更强)哈希函数运行的256位随机密钥，仍然是遥不可及的。

如果哈希函数本身是量子后安全的，例如SHA-512，但输入是密码，怎么办？是否有任何量子算法能够比传统的蛮力搜索更少地找到输入(上面的例子是平均\frac{2^{80}}{2})？Grover的算法(或任何其他适用的量子算法)仅适用于削弱哈希函数本身，还是也可以只搜索合理的输入(A、A、0-9 <=14字符)以减少搜索空间？

明确地说，我理解任何简单的散列函数(即使有像sha-512这样的不必要的长输出)都是存储用户密码和Argon2或类似功能的糟糕方法，但是我认为内存硬度和其他方面可能会使这个问题过于宽泛，或者一个更广泛的答案。

Answer 1

Grover的算法(或任何其他适用的量子算法)仅适用于削弱哈希函数本身，还是也可以只搜索合理的输入(A、A、0-9 <=14字符)以减少搜索空间？

Grover是一种通用的搜索方法--它不知道或不关心函数是如何给出解释输入的。如果您给它一个函数，将输入解释为“(A，A，0-9 <=14字符)”，它将与它一起工作，具有预期的复杂性。

另一方面，相关的问题可能是“使用量子计算机是否具有经济意义，而不是GPU场或一些ASIC？”我建议在接下来的几十年(也就是说，在量子计算机技术经历了几代人之前)，在这种情况下，经典的方法会更快。

造成这种情况的一些原因：

• 量子计算运算的成本可以预计要比相应的经典运算的代价大得多。这是一个不变的因素，当比较两者--然而，如果这个常数因子可能是十亿或一万亿，它真的不应该被忽视。
• 并行化--经典的计算机搜索(如这一次)是完全可并行的( GPU场或一组ASIC将充分利用这些搜索)。相比之下，Grover的算法(或任何类似的Quantum搜索)并不是这样--如果您可以执行n^2连续的操作，那么您确实可以加快O(n)的速度。但是，如果您不能等待那么长时间，并且需要实现多个量子计算机来进行搜索，那么您就无法在它们之间获得n^2的速度。例如，要想以100倍的速度进行搜索，需要10,000倍的量子计算机。
• 密钥搜索的重用。通过经典计算，我们可以生成彩虹表--生成该表需要完全搜索；然而，一旦完成，对各种哈希密码进行重复搜索就很便宜了。相反，运行Grover的算法将对单个密码进行搜索--如果我们想检查另一个哈希，我们必须再次支付全部搜索的费用。当然，你可以在量子计算机上建造彩虹台，但是我不相信你会得到任何量子速度，而且我也没有听说过一个替代方案，你可以提高量子速度。

现在，随着时间的推移，我们可以合理地预期量子计算机的成本会下降(而且下降的速度会比传统计算的相对成本更快)，而且我们可以预期量子计算机会随着时间的推移而变得更快(因此需要更少的并行化)；我只是不认为这两种趋势都会在晚上发生。

明确地说，我理解任何简单的散列函数(即使有像sha-512这样的不必要的长输出)都是存储用户密码和Argon2或类似功能的糟糕方法，但是我认为内存硬度和其他方面可能会使这个问题过于宽泛，或者一个更广泛的答案。

根据我们目前对量子计算机内在的权衡的理解(这可能是相当离谱的)，对于量子计算机来说，记忆的硬功能将是相当痛苦的。计算这样的哈希函数似乎需要一个大的量子内存，而且(据我们所知)这看起来是非常昂贵的1。

Grover的算法是适用的(同样，它不关心哈希函数是什么)；但是，它看起来相当昂贵。

因此，假设我们的猜测是正确的，一个内存硬哈希函数(Argon2)将比简单的哈希函数更能抵抗量子计算。

1：我相信至少有一部分原因是，如果你有一个大的量子存储器，并且访问它作为一个纠缠地址，你最终会对每个单个存储单元(或者至少是每个可能被纠缠地址处理的单个单元)执行操作。相反，对于经典内存，您只需要访问正在寻址的单元格。如果我们讨论的是一个具有1,000,000个可寻址位置的内存，这意味着量子内存可能需要执行与经典情况相比的1000,000倍的操作。