Keccak/SHA3 3的安全防范生日攻击

Question

如果我正确理解了它，那么\operatorname{Keccak}的安全性取决于容量c，这意味着我为c=128获得了2^{128}的安全级别(这里我省略了值r，因为我认为它与我的question...but无关，如果我错了，请纠正我)。

但在我发现的每一份出版物(甚至在\operatorname{Keccak}网站上)中，都说安全性不取决于输出长度。我不明白c的价值与生日攻击有什么关系。对于每一个散列函数，我都可以运行生日攻击，而不管哈希函数的内部结构如何，对吗？这意味着对于具有\operatorname{Keccak}实现的c=128，但是输出长度为64位，我可以使用生日悖论在2^{32}步骤之后发现冲突，而不管c的值如何，对吗？

让我们再向前走一步。如何使用c=128和输出长度为1位的Keccak仍然安全？对于实际应用来说，它根本不可能是.

Answer 1

让我们更正一下你的一些数字。容量的大小是预期安全裕度的两倍(针对生日攻击)。这就是扁平海绵、牙套等的概念。

当使用随机海绵作为安全参考时，人们会考虑特定攻击的成功与否。这种成功概率不仅取决于所考虑攻击的性质，还取决于随机海绵的选择参数，即其容量、比特率，以及它是调用随机置换还是随机变换。平面海绵索赔是一种简化，在某种意义上，我们只考虑最坏情况下的成功概率，这是由随机预言区分优势Bertoni等人，Eurocrypt‘08上的上限决定的，它完全取决于随机海绵的容量。因此，它使用一个参数:声称的容量c_{\mathit{claim}}来降低所有攻击的声称成功概率。[来源]

因此，如果您的目标是128位的安全裕度，则需要具有256位的容量。

在这种方法中，设计了一个基于f位的置换b=r+c，并在海绵结构中使用它来构建海绵函数F。此外，我们在F上提出一个平面海绵索赔，其声称的容量等于海绵结构中使用的容量，即c_{\mathit{claim}}=c。换句话说，声明指出对F的最佳攻击必须是泛型攻击。因此，c_{\mathit{claim}}=c意味着对F的任何预期复杂度低于2^{c/2}的攻击都意味着对f的结构区分，因此排列的设计试图避免这种区分。请注意，f的结构区分器的存在并不一定意味着F中的攻击或弱点。例如，对于f的任何区分器，如果其成功概率低于2^{c/2}，则不构成威胁，因为扁平海绵声明没有针对可能发送更多2^{c/2}查询的对手的安全性。[来源]

TL;DR:安全保证金是容量的一半。如果您的目标是128位，则需要256位的容量。

话虽如此，我们还是可以谈谈你的误解。你说得对，如果你取1位的输出长度，你就没有64比特的安全性要求……因为您正在寻找输出中的冲突。

使用\operatorname{Keccak}时，可以检索比特率(r)的全部大小。您还可以扩展此输出，因为这些输出是相关的(因为您基本上总是知道比特率部分的内容)。因此，你不知道的唯一一部分就是能力。如果您能够猜到这部分内容或有冲突，那么输出就会受到影响。

容量是你不知道的状态中唯一的一部分。

当你想要碰撞时，你看起来要么是在容量部分上发生碰撞，要么是在比特率部分上，它通常比容量大……

让a,b是两个输入，c,c_1,c_2是容量部分。当以下情况发生碰撞时：

f(a) \to [\theta \mathbin\| c_1]\\f(b) \to [\theta \mathbin\| c_2]

其中，[\theta \mathbin\| c]是完全状态，而\theta是结果输出(在这里，输出长度很重要)。

另一种寻找碰撞的方法是设法获得：

f(a) \to [\alpha \mathbin\| c]\\f(b) \to [\beta \mathbin\| c]

(容量上的碰撞)，因为这样你就可以拥有(由于简化的海绵结构)：

\begin{align} f(a \mathbin\| 0) & \to [\alpha \mathbin\| c] &\Rightarrow&&& f([\alpha \oplus 0 \mathbin\| c]) \to \theta \\ f(b \mathbin\| \beta \oplus \alpha) & \to [\beta \mathbin\| c] &\Rightarrow&&& f([\beta \oplus \beta \oplus \alpha \mathbin\| c] ) = f([\alpha \mathbin\| c]) \to \theta \end{align}

TL;DR 2:正如@CodeInChaos所说的，碰撞阻力是\min(c/2,n/2)，而预图像电阻是\min(c/2,n)，其中n是输出大小。但是，大多数论文都在\operatorname{Keccak}[1600]上搜索冲突，因此它们通常会声明这种更通用的安全裕度(2^{\mathit{capacity}/2})。