为什么沙-3的产量只有产量的一半？

Question

对于SHA-3哈希函数族，输出大小d总是被选择为d=c/2，即只占D1的一半。这有什么道理呢？

天真地说，我认为d=c更有意义，因为

• 碰撞阻力似乎是\min(d/2, c/2)和
• 图像前的强度似乎是\min(d, c)。

因此，选择d=c将使对容量的攻击等同于对输出的攻击。我遗漏了什么？

Answer 1

为什么SHA-3的输出容量只有SHA-3的一半？

因为碰撞攻击并不是唯一感兴趣的攻击；我们还期望，对于预图像(和第二个预图像)攻击，最好的攻击不会比蛮力更好(对n-bit哈希函数进行预期的-bit哈希计算)。

对于SHA-3，我们有以下替代方法：

• 选择大量的初始图像A_1, A_2, ..., A_k，并计算给SHA-3 \alpha_1, \alpha_2, ..., \alpha_k的中间状态。
• 选择大量的最终图像B_1, B_2, ..., B_k，并利用Keccak置换是可逆的事实，根据已知的最终状态(输出目标值)计算将导致最终状态的所需的中间状态；这些中间状态是\beta_1, \beta_2, ..., \beta_k。
• 搜索\alpha_i，\beta_j中间状态以找到在其容量位中一致的一对\alpha_x, \beta_y；调用其速率位的xor C

如果我们找到这样的一对，那么消息A_x C B_y的哈希就是目标值。

要有很好的概率找到这样的一对，我们需要有j \approx 2^{c/2}。

因此，要使这种方法不像蛮力方法那么简单，就需要c \ge 2n。

Answer 2

除了碰撞和预图像攻击之外，还存在长度扩展攻击的问题(我认为这是SHA3这种属性的“真实”原因)。

如果您有一个散列函数H，那么就很容易将H(k,m)作为m的MAC来处理，其中包含秘密密钥k。不幸的是，如果您使用的是上一代哈希函数(SHA1，SHA2)，这不会导致安全的MAC。

长度扩展攻击的发生正是因为哈希函数输出它的entire内部状态。长度扩展攻击背后的思想是:如果m是m'的前缀，那么在计算H(k,m')时，输出H(k,m)作为内部状态出现。事实上，由于H(k,m)在某一点上是整个内部状态，那么如果您知道H(k,m) --即使您不知道k，也可以计算D11！这违反了您希望从MAC中获得的安全属性(学习m的MAC不应该帮助您预测不同m'的MAC，即使m是m'的前缀)。(在这里，我正在讨论长度填充的问题，这些问题对我所勾画的攻击并没有明显的障碍。)

在SHA3比赛中，大多数提交材料都是为了抵抗长扩展攻击而设计的.这样做的方法是使用所谓的“宽管”结构:简单地使内部状态大于输出。换句话说，哈希应该只在计算结束时输出其内部状态的一部分。如果这样做，那么H(k,m)将不会包含计算H(k,m')所需的一切，这将阻止长度扩展攻击。