耐预成像但不耐二次成像？

#1 楼

加密散列函数$ f：\ {0,1 \} ^ {*} \ to \ {0,1 \} ^ n $具有三个属性：（1）前像电阻，（2）第二前像电阻，和（ 3）抗碰撞性。甚至更进一步，这些属性形成了一个层次结构，其中每个属性都隐含了一个属性，即，耐碰撞功能也具有第二原像抗性，而第二抗原图像的功能也具有原像抗性（条件为$ f $）。

在（3）⇒（2）的情况下，不难理解为什么：如果对手找不到任何冲突消息对，那么他们肯定在以下情况下找不到冲突消息：其中一条消息是固定的。

但是（2）⇒（1）确实比较棘手。对于某些直觉，请考虑不具有抗前图像功能的第二抗前图像功能的哈希函数$ f $（通过访问前图像查找Oracle进行建模）。假设您获得了$ m_1 $；那么您可以计算$ H（m_1）$并向oracle查询$ H（m_1）$的原像。然后，oracle将返回一个$ m_2 $，这样$ H（m_1）= H（m_2）$。

这几乎是第二个原像。唯一的问题是$ m_1 \ ne m_2 $。直观地，假设$ f $将无限多的输入映射到有限数量的输出，则“应该”很有可能$ m_1 \ ne m_2 $。对于所有现实生活中的散列函数来说，情况几乎都是这样，因此具有第二个原图像抗性的散列函数应不缺少原像抗性。

但是，可以定义“病理”散列函数具有完美的，可证明的第二原像电阻，但没有原像电阻。 《应用密码学手册》第9章给出的示例是：

$$ f（x）=
\ begin {cases}
0 || x和\ text {if} x \ text {是} n \ text {位长} \\
1 || g（x）和\ text {otherwise}
\ end {cases} $$

其中$ g（x）$是抗碰撞的哈希函数。在这种情况下，对于以$ 0 $开头的摘要，找到原像很简单（实际上，这只是身份函数），但是由于没有可能的第二原像，因此这种情况证明可以抵抗第二原像。换句话说，该$ f $在$ n $位输入空间中是双射的。

为了更精确地说明何时（2）⇒（1），Rogaway和Shrimpton提出了一个理论值上面的“密码哈希函数基础”中列出的三个属性之间的各种关系的分析。本质上，他们的分析将哈希函数视为具有有限的固定长度域，即$ f：\ {0,1 \} ^ m \ to \ {0,1 \} ^ n $，其中它们显示


“常规含义”，如含义（3）⇒（2）；从本质上讲，它们是无条件意义上的“真实”含义，而
是“临时含义”，例如（2）⇒（1）的含义；这些实际上是有条件的，取决于$ f $压缩消息空间的量（随着消息空间相对于摘要空间变大，在概率意义上的含义“更强”）。

因此，如果哈希函数将消息空间压缩到足够的程度，则临时含义实际上是正确的。 （它们提供的“足够”示例是将256位消息哈希压缩为128位的哈希。）因此，仅当所讨论的函数充分压缩其输入时，第二原像电阻才意味着原像电阻。对于保留长度，扩展长度或低压缩的功能，第二原像电阻不一定意味着原像电阻（如第8页的作者所述，大约在页面的中间）。

鉴于上述算法，在给定原像预言机的情况下找到第二个原像时，这应该很直观。如果将6位输入扩展为256位，则预映像预兆实际上不太可能找到第二个预映像。无论如何，这不是一个正式的论据，但它是一个很好的启发式方法。


现在，回到现实生活。鉴于上述使用原像预言机查找第二张原像的算法，我不希望任何现实的哈希函数都受到原像攻击，而不会受到第二张原像攻击，尤其是因为真实的哈希函数通常可以很好地压缩数据。 br />另一方面，我个人并不知道有任何历史上使用过的非玩具式密码散列函数，该函数具有二次原图像攻击但没有原图像攻击。通常，抗碰撞性是密码分析人员首先要攻击的东西，因为它（在某种意义上）是“最难满足”的特性。但是，如果发现哈希函数因冲突而被破坏，则密码分析人员通常会直接使用：映像前攻击。因此，我不知道您将试图找到这样的哈希函数有多大运气。

您可以在哈希函数休息室查看一些历史性的哈希函数；它显然自2008年以来就没有进行过更新，但仍包含一些有用的信息。我浏览了几次攻击，发现大部分是碰撞和原像攻击，但是您可能会遇到更多的运气。

#2 楼

Kelsey和Schneier在其工作于$ 2 $ n $的$ n $位散列函数的第二个原像中，提供了以下内容：


对所有$ n $-具有Damgard-Merkle增强和$ n $位中间状态的位迭代哈希函数，从而允许为大约$ k \ times2 ^ {n / 2 + 1}的$ 2 ^ k $ -message-block消息找到第二个原像。 + 2 ^ {n-k + 1} $工作


，而不是预期的$ 2 ^ n $工作。这牢固地存在于理论攻击的范围内，但满足了作为二次原图像攻击（而不是原图像攻击）的条件，并且适用于SHA3之前的所有常用哈希函数。

他们提供的示例：可以找到在$ 2 ^ {106} $工作中用SHA1处理的$ 2 ^ {60} $字节消息的第二个前映像，而不是$ 2 ^ {160} $。这是SHA1可以处理的最大消息；如果我们选择一个更合理但仍然较大的消息，例如在4TB磁盘上使用SHA1哈希，或大约$ 2 ^ {38} $个消息块，则查找第二个前映像的工作大约为$ 38 \ times 2 ^ {{ 160/2} + 1} + 2 ^ {160-38 + 1} \ approx 2 ^ {123} $。

感谢Reid提供指向哈希函数休息室的指针，在这里我找到了本文。