与抗碰撞性有何不同？是否有任何已知的原像攻击被认为可行？
#1 楼
耐原像性是可以考虑的哈希函数的最基本属性。这意味着：对于散列函数的输出空间中给定的$ h $，很难找到$ H（x）= h $的任何消息$ x $。（请注意，这里和下面的定义很难正式定义，但可以通过查看带有安全性参数$ n $的哈希函数族来正规化（通常哈希输出大小），然后说“硬=没有多项式$ P $，因此可以针对家庭的所有功能及时完成$ P（n）$”。对于实际用途，我们通常只看一个单一哈希函数，并且满足“ hard =”要求的时间/成本比任何假设的攻击者都可以投资«更多，最好对要完成的工作进行一些估算。）
具有此属性的函数是也称为单向函数（尽管此术语也用于具有此属性的非哈希函数，例如非对称加密原语）。
相关属性是第二个原像电阻：
对于给定的消息$ x_1 $很难找到第二条消息$ x_2 \ neq x_1 $且$ H（x_1）= H（x_2）$。
没有原像抵抗的功能通常也不是第二条耐原像：给定一条消息$ x_1 $，计算$ h：= H（x_1）$，然后从$ h $获得原像$ x_2 $，则通常有$ x_1 \ neq x_2 $和$ H（x_1）= H（x_2）$。 （“通常”的例外是，该函数本质上是（对于有趣消息的空间而言）是内射的，并且原像查找器将始终返回唯一的有趣原像。该函数将是第二原像并且具有防碰撞功能，但是仍然是一个非常差的散列函数。通常，有趣消息的空间比散列空间大，因此在实践中不会出现这种情况。）
抗冲突性甚至更难，我们仍然想要最常用的哈希函数：
很难找到带有$ H（x_1）= H（x_2）$的消息$ x_1 \ neq x_2 $。
当然，来自（第二次）原像攻击我们还会发生碰撞攻击。另一个方向并不容易，尽管对散列散乱函数的某些碰撞攻击似乎可以扩展为几乎与第二个原图像攻击一样有用（即，我们发现碰撞的大部分内容都可以由攻击者任意修复） 。
此外，哈希函数也有通用的生日攻击（甚至适用于随机预言），需要$ O（\ sqrt N）$才能有很大的机会击中重复项，其中$ N $是函数输出空间的大小，对第二个原像和原像电阻进行类似的通用蛮力攻击大约需要$ O（N）$个查询（这对于$ O（N）$是不可行的）
我不知道通常的哈希函数没有实际的映像前攻击（请在其他答案中添加它们，或作为注释），例如，对于MD5，则要具有抗碰撞性几乎完全破裂，SHA-1开始出现裂缝（2017年，来自Goog的研究小组le产生了两个相冲突的文档）。
一个人如何利用这种不足？这在很大程度上取决于在更高级别的协议中使用哈希函数（或在其之上构建的算法）。在某些协议中，仅直接使用其他属性，但是如上所述，缺少原像抵抗力也总是会导致缺少第二原像和碰撞抵抗力。例如，在签名方案中，我们通常首先对消息进行哈希处理，然后（第二次）前映像攻击允许创建第二条消息，该消息具有与第一个相同的哈希值，即适合相同签名的地方。
需要本身具有原像抵抗性的示例是密码的哈希，或者通常是密码与攻击者已知的盐一起哈希。 （实际上，这里的消息空间通常很小，以至于使用通用的快速哈希函数对它进行暴力搜索变得可行，这就是为什么使用慢速哈希函数进行密码哈希的原因。）
评论
$ \ begingroup $
没有已知的针对MD5或SHA-1的原像（或第二原像）攻击。理论上，对MD4的原像攻击（复杂度为$ 2 ^ {102} $），对MD2也有攻击（$ 2 ^ {73} $）。
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
2011年11月12日15:10
$ \ begingroup $
时间戳记RFC 3161需要具有前映像抵抗能力，将时间戳记与哈希树结合使用（如ERS中一样）为“多目标前映像攻击”提供了可能性，您可以在其中为任何哈希值找到一个前映像相当大的一组哈希值，这比较容易（对于大小为$ O（\ sqrt {N}）$的哈希值集，降低到$ O（\ sqrt {N}）$）。
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
2011年11月12日15:14
$ \ begingroup $
从2017年开始成功对SHA-1进行碰撞攻击：security.googleblog.com/2017/02/…
$ \ endgroup $
–乔纳森·克罗斯（Jonathan Cross）
18 Mar 12 '18 at 11:39
#2 楼
碰撞攻击是指找到产生相同结果的两个输入的能力，但该结果无法提前知道。在典型情况下（例如，攻击MD5），只有相对少量的特定输入会产生冲突。防碰撞性显然意味着碰撞攻击是困难的（对于“困难”的某种定义，从“没有比强力知道更好的攻击”到“已知的攻击实际上是不可行的”）。前映像攻击使您能够创建产生指定结果的输入。可行的映像前攻击基本上意味着（作为冷冻散列）算法几乎完全失效。本质上，[edit：可能]可以更彻底地破坏它的唯一攻击是第二次原像攻击。但是，基本上都意味着您所拥有的根本不再是加密哈希函数-加密哈希的全部意义在于它是单向函数，但是任何一种前映像攻击都意味着它现在是两个双向攻击。
冲突攻击可以在相对少量的特定情况下使用（例如，签名证书），但不如前映像或第二前映像攻击那么全面。
我不知道对当前流行的任何哈希（例如SHA-1，SHA-256）进行可行的原像攻击。再说一次，如果存在甚至在远程可行的原像攻击，他们将（或者肯定应该）非常迅速地失去知名度。为了进行比较，由于可行的碰撞攻击，MD5通常被认为是过时的，但根本没有任何原像攻击。即使这并不是真的可行，但SHA-1上已知的碰撞攻击仍然足够，大多数人建议不要继续使用它（2017年编辑：并且有充分的理由-SHA-1上的碰撞攻击现在完全可行）。
针对许多较旧的哈希函数（例如SNEFRU）进行了预映像攻击（例如，对三遍SNEFRU进行了第二次预映像攻击，其复杂性为233次操作，这意味着（例如）从磁盘读取原始消息可能会花费大量时间。好的攻击是相当不寻常的：可以说，一旦对特定算法的合理可行的攻击被人们知道，大多数人（用户和研究人员都如此）往往会朝着更大更好的方向发展。 />
评论
$ \ begingroup $
我认为（第一）原像攻击通常比第二原像攻击更具破坏性，因为（通常）原像攻击很容易扩展到第二原像攻击，但反之则不然。
$ \ endgroup $
–PaŭloEbermann
2011年11月12日15:15
$ \ begingroup $
@PaŭloEbermann：也许-实际上，谈论哪一个更具破坏性，就像在争论死于断头台还是开除枪支更糟。无论哪种方式，您都死定了（匆忙中）。为了更清楚一点，我还是会对其进行编辑。
$ \ endgroup $
–杰里·科芬（Jerry Coffin）
2011年11月12日15:20
$ \ begingroup $
您是否有声称的Snefru 2nd preimage攻击复杂性的参考？
$ \ endgroup $
–森林
19年2月13日在8:36
#3 楼
通常，密码的哈希值（大多数情况下是反复迭代和加盐）存储在数据库中，而不是密码中。如果用户登录，则将计算哈希并将其与存储的哈希值进行比较。这样，可以看到哈希数据库的用户不会直接看到密码，但是此属性在很大程度上取决于哈希是否可以抵抗图像前攻击，如其他答复所述。有了理想的哈希，除了攻击者随后以脱机方式尝试自己输入密码或查阅预先计算的哈希表以及使这种攻击变得更加困难之外，没有任何有关密码泄漏的信息，完成加盐和迭代步骤。 br />还可以在硬币翻转协议中使用散列：假设玩家1和2想要在不位于同一位置的情况下翻转硬币，并假定它们具有一些安全的通信通道。一种实现方法是，玩家1挑选一个较大的$ n $（从一些预先安排的固定但较大的范围内），然后将其哈希值发送给玩家2。玩家2然后猜测$ n $是奇数还是偶数，如果他是对的，则赢得掷硬币的机会。为了验证正确性，玩家1向他发送了数字$ n $，而玩家2可以验证其哈希值是否与他之前收到的哈希值匹配。现在，如果散列不具有前映像抗性，则玩家2可以从散列中计算出$ n $并知道而不是猜测。如果散列不是抗冲突的，那么玩家1可以找到（也许）在正确范围内的奇数$ n $和偶数$ m $，并且散列相同，因此他可以在显示阶段生成其他数字，具体取决于根据对方的选择，玩家1可能会作弊。
正如Paulo所提到的，当您考虑数字签名（例如因此，将取决于散列的应用程序需要满足的条件，但是由于散列的用途非常广泛，因此我们需要一个标准散列，以使其具有尽可能多的散列。例如。因为它们也用在密码随机性生成器中，所以输出也应该看起来尽可能地随机，并且输出应该具有尽可能接近的均匀分布范围。
评论
重要的是要注意，您得到的答案都不会是“原像抵抗”的“定义”。那是因为对于给定的哈希函数，它没有一个很好的代码（您可以在哈希函数系列中对其进行定义，但是我怀疑这里有人会这样做）。@Fixee：感谢您的评论。我据此在答案中添加了一个注释-可以这样说吗，它太草率，甚至是很明显的错误吗？
@PaŭloEbermann您添加的评论解决了该问题，但这并不完全正确。恐怕要指出为什么这个（细微的）问题很难解决，所以此注释框可能需要更多的空间。如果您有兴趣，请参阅Rogaway论文中有关此主题的介绍（cs.ucdavis.edu/~rogaway/papers/ignorance.pdf）。
@Fixee：感谢您的链接，我正在阅读。但这似乎主要是关于抗碰撞性，并且我认为相同的问题并不适用于原像抵抗（我们不希望对任何散列使用原像（这总是很容易的，但是对于给定的原像）。 （但是我发现我错误地解释了您的“哈希函数族”。）
@Fixee：我想我们想要一个算法的存在（或我们的知识，与本文一起去），对于每个$ d $（或至少很大一部分），输出一个合适的$ m $，而不是一个单独的算法每个$ d $（这当然是微不足道的）。我认为这里不需要钥匙。 （我们应该将此讨论移到聊天室吗？）