抗冲突能力高达$ 2 ^ {256} $个操作br />达到$ 2 ^ {256} $操作的原像电阻
达到$ 2 ^ {256} $操作的原像电阻散列函数可以更有效地受到攻击。丹尼尔·伯恩斯坦（Daniel J. Bernstein）撰写了针对所有第二轮SHA-3候选人的量子攻击。但是，在该论文中，所有针对Keccak变体的攻击都针对内部容量为哈希长度两倍的截断哈希，例如具有224位输出的Keccak [r = 1152，c = 448]。 />我的问题是，如果使用Keccak [r = 1088，c = 512]的完整512位哈希输出长度，是否使用Grover算法为量子攻击者提供高达$ 2 ^ {256} $的安全性，还是安全性只限于原像强度的一半，即仅$ 2 ^ {128} $个操作？
#1 楼
除非Keccak具有我所不知道的结构性弱点，否则答案就不会是128还是256！无爪函数”，该函数可通过创建一个大小为$ \ sqrt [3] {2 ^ b} $的表（对于经典的生日攻击，使用$ \ sqrt {2 ^ b} $来有效地工作），然后利用Grover算法找到碰撞。经典生日攻击因此需要$ {\ mathcal O} \ left（\ sqrt {2 ^ b} \ right）$时间和内存，而量子生日攻击只需要$ {\ mathcal O } \ left（\ sqrt [3] {2 ^ b} \ right）$时间和内存。
这意味着要提供针对量子对手的$ b $位安全级别，哈希函数必须至少提供一个$ 3b $位输出。
对于512位Keccak，您的安全级别为$ 170 \ frac {2} {3} $。
#2 楼
简而言之，答案是肯定的，如果使用了Keccak [r = 1088，c = 512]的全部512位哈希输出长度，则可以提供高达2256次针对Grover量子算法的操作的安全性。使用格罗弗的算法，可以用量子计算机在2n / 2的时间内找到n位哈希函数的原像。从某种意义上说，这是通用攻击，它适用于任何n位哈希函数。
对于Keccak [r = 1088，c = 512]的256位输出（或就此而言） （任何256位哈希函数），则量子攻击者可以通用地应用Grover并在时间2128中找到原像。类似地，对于Keccak [r = 1088，c = 512]的完整512位输出，量子攻击者可以应用Grover通常可以在2256年的时间内找到原像。但是，Grover也可以用于恢复c = 512个隐藏位，但是它没有任何优势：它也将花费2256时间。
通常，攻击者可以选择是一般应用Grover还是应用它来找到c隐藏位，然后他会选择最快的选项。
评论
$ \ begingroup $
这正是我的想法，但我想确认一下我没有错过一些关键要闻，为什么事实并非如此。谢谢！
$ \ endgroup $
–可以裸体
2011年8月17日在20:26
#3 楼
首先，让我们在这里弄清楚一些事情。 Grover算法的分析是渐近的，因此执行与您提到的设置一样具体的操作是相当不公平的。Grover算法为您提供了搜索的渐近上限$ O（\ sqrt {N}）$数组大小为$ N $，因此我很难理解如何声明需要$ 2 ^ {512} $运算。对我来说，从分析的角度看，分析似乎是错误的。您应该看到的是Grover算法中的常数因子，为此，我将向您介绍Grover算法的原始论文并在那里计算数学。您会看到，它不会给原像抵抗带来2 ^ {512} $的运算次数，而是给您一个常数倍。
但是，如果要进行渐近分析，则不能具有哈希函数的特定实例化，而是必须考虑一组哈希函数。这是人们容易犯的常见错误。在那种情况下，您所知道的是S. Aaronson关于量子下界的论文的上限是$ O（\ sqrt {N}）$，下界是$ \ Omega（N ^ {1/3}）$。用于碰撞和元素区分性问题。
评论
$ \ begingroup $
Grover的论文描述了一种由量子位和单一运算构建的特定机器。虽然符号$ O（\ sqrt N）$的确表示一组渐近的增长曲线，但是Grover的用于查找原像的算法以及相关的BHT和Ambainis用来查找碰撞的算法也具有具体数量的量子比特来实现该机器和获得成功之前规定的成功概率或预期操作次数的操作。在恒定因素的影响下扫一扫这无济于事。
$ \ endgroup $
–吱吱作响的s骨
19年3月18日在16:45
#4 楼
将散列函数$ H \冒号\ {0,1 \} ^ m \修复为\ {0,1 \} ^ n $，使用容量为$ c $的海绵构建。提高在$ 2 ^ \ lambda $以上的经典或量子计算机上进行通用碰撞和通用原像搜索的成本，选择$ c = n = 2 \ lambda $：容量和哈希长度仅是安全目标的两倍，就不再是。 br />
例如，对于甚至针对量子对手的128位安全级别，只需选择$ c = n = 256 $就可以了。出于谨慎考虑，部分是出于政治原因，原因是在Snowden和Project BULLRUN [1]之后不久，NIST选择了$ c = 2n = 4 \ lambda $，例如SHA3-256的$ c = 512 $，可提供128位安全级别，而性能成本是相当大的（在当时从政治上讲是合理的，但现在在技术上令人遗憾）。相比之下，较新的SHAKE128和SHAKE256还是因为新颖而不受政治关注，并遵循$ c = 2 \ lambda $公式。按照传统的常识，您必须将哈希大小增加一倍或三倍，以保持与经典对手相同的安全性，让我们回顾一下通用攻击的最新技术。
防冲突
密码学家以外的传统看法是，您经典可以做的最好的事情是为随机输入创建一个大的输出表，并希望您最终在生日悖论中发现冲突，这将花费$ O（2 ^ {n / 2}）$时间和$ O（2 ^ {n / 2}）$空间来存储表。但是您不需要存储表-Pollard的$ \ rho $ [2]的一种变体可以在恒定的空间中完成。
因此，最好的通用经典碰撞搜索算法是van Oorschot–Wiener [3]，其成本为$ O（2 ^ {n / 2}）$，可以并行化以提供线性加速，例如，并行化$ O（2 ^ {n / 4}）$种方式并以$ O（2 ^ {n / 2}）$的成本在$ O（2 ^ {n / 4}）$时间内获得答案。对于海绵，相同类型的通用生日攻击可以在$ c $位的隐藏状态下起作用，而代价为$ O（2 ^ {c / 2}）$。广告被告知要花费$ O（2 ^ {n / 3}）$的时间，但这忽略了除时间之外还有其他成本的现实[4]。 Brassard–Høyer–Tapp算法[5]的工作方式是构建一个大小为$ O（2 ^ {n / 3}）$的表，然后对$ O（2 ^ {n / 3}）$个步骤运行Grover算法，其中面积*时间成本$ O（2 ^ {2n / 3}）$，比经典搜索要昂贵得多。可以将Ambainis算法[6]改编为冲突搜索算法，以得到相似的成本$ O（2 ^ {2m / 3}）$。主题还有一些其他变化，但是即使在一个极端不现实的前提下，即量子位操作与位操作一样便宜，并且通信是免费的，它们都没有打破$ O（2 ^ {n / 2}）$的成本壁垒[7]。 ]。对于海绵，相同的通用生日攻击在$ c $位的隐藏状态下起作用，成本为$ O（2 ^ {2c / 3}）$ [8]。
有一个下限$ \ Omega（2 ^ {n / 3}）$表示通用量子算法必须对$ H $ [9]进行查询的次数，因此，如果该领域有所进展，则必须大幅减少存储成本。
最好的通用（海绵）碰撞攻击是今天可以运行的经典算法-量子算法不再引起其他关注。
原像电阻>
密码学家以外的传统看法是，经典的最佳选择是在找到匹配的$ O（2 ^ n）$输入之前尝试它。但是，您可以在并行机[11]上使用Oechslin的rainbow table [10]来节省多个目标的成本，从而在$ O（2 ^ n / t ^的时间内获得$ O（2 ^ n / t）$的成本3）$ H $的顺序评估，如果采用并行的$ t ^ 2 $方法来查找第一个$ t $目标的原像。对于海绵，相同的通用原像攻击适用于以时间$ O（2 ^ c / t ^ 3）$来恢复$ c $位隐藏状态，成本为$ O（2 ^ c / t）$。 >
最好的通用量子原像算法，格罗弗算法[12]，被宣传为花费$ O（2 ^ {n / 2}）$的时间，并且不需要太多的空间，所以面积*时间成本看起来有些吓人，是$ O（2 ^ {n / 2}）$-但是，即使您可以连续地每纳秒对$ H $进行一次评估，而没有时间进行任何其他计算，则要花半个世纪才能得到答案。事实证明，格罗弗不能很好地并行化或没有提供很多批处理优势[13]：花费$ p $倍的精力在$ p $机器上并行运行Grover只能得到$ \ sqrt { p} $加速，因此净成本增加了$ \ sqrt {p} $，对$ t \ ll p $目标的批量攻击仅使$ t ^ {1/4} $加速。对于海绵，相同的通用原像攻击适用于在时间$ O（2 ^ {c / 2}）$中恢复$ c $位隐藏状态，并且并行性和适度的批处理优势成本相似。
对于量子计算机可以实现的原像攻击加速，还有其他一些担忧，但您也应该担心使用经典计算机进行的多目标批量攻击。
没有通用的第二原像攻击比通用的原像攻击更有效，而且碰撞抵抗也意味着第二原像抵抗，因此对此没有太多可说的。
#5 楼
这是有关海绵的量子安全性的最新论文：塌陷的海绵：海绵构造的后量子安全性我们研究基于
的哈希函数的后量子安全性海绵结构。在
后量子设置中，哈希函数的关键属性是崩溃属性（增强了
抗碰撞性）。我们表明，在关于基础嵌段函数的适当假设下，海绵构造正在塌陷（因此抗量子碰撞）。特别是，如果块函数是随机函数或
（不可逆）随机置换，则海绵构造会崩溃。
我认为，考虑到这方面的工作比这里介绍的要好。
评论
$ \ begingroup $
既然这是公认的答案，那么值得一提的是丹尼尔·J·伯恩斯坦（Daniel J. Bernstein）挑战了Brassard，Høyer和Tapp攻击实际上比传统算法更适合碰撞发现的说法。看到这里：cr.yp.to/hash/collisioncost-20090517.pdf
$ \ endgroup $
– hakoja
17年4月19日在12:27
$ \ begingroup $
有一种基于Pollard的$ \ rho $的标准经典攻击，需要$ O（\ sqrt {2 ^ b}）$时间和本质上恒定的内存，并且可以并行化，例如$ O（2 ^ { b / 4}）$种方式可以以$ O（2 ^ {b / 4}）$的时间运行（以相同的能量消耗$ O（2 ^ {b / 2}）$，但速度更快）。迄今为止，所提出的量子碰撞搜索算法均未在该范围上有所改进。
$ \ endgroup $
–吱吱作响的s骨
19-2-28在20:39
$ \ begingroup $
BHT算法的总面积*时间成本当然是$ O（2 ^ {2b / 3}）$，远高于BHT算法获得的$ O（2 ^ {b / 2}）$成本。 $ \ rho $任意速度。换句话说，迄今为止，量子碰撞搜索算法对抗碰撞哈希函数的安全参数的选择没有其他影响，因为已经有更好的经典碰撞搜索算法已经确定了这些参数。
$ \ endgroup $
–吱吱作响的s骨
19年2月28日在20:43
$ \ begingroup $
因此，您是说答案的big-O表示法的指数中缺少一个因子是$ O（2 ^ {b / 3}）$而不是$ O（2 ^ {{\ textbf {2}} b / 3}）$？
$ \ endgroup $
–马腾·博德威斯♦
19年2月28日在21:53
$ \ begingroup $
一旦计算了存储成本，量子面积*时间成本$ O（2 ^ {2b / 3}）$是所要求的平方。经典区域*时间成本$ O（2 ^ {b / 2}）$是要求赔偿的平方根，一旦使用$ \ rho $类型的搜索（而不是表格）消除了不必要的存储成本。
$ \ endgroup $
–吱吱作响的s骨
19-2-28在22:46