原像攻击

在密码学中，密碼雜湊函數上的原像攻击用于寻找有着特定哈希值的訊息。一个密碼雜湊函數应该抵御对其原像的攻击。

在攻击情形下存在两种原像抗性：

  • 原像抗性：对于所有预设输出，从计算角度应无法找到任何符合输入哈希的输出。例如，给定y，使得很难找到满足h(x) = y的x。[1]
  • 次原像抗性：从计算角度无法找到任何与特定输入值有着相同输出的二次输入值。例如，给定x，使得很难找到满足h(x) = h(x′)的次原像x′ ≠ x。[1]

这些可以与抗碰撞性对比。抗碰撞性是指无法从计算角度找到任何两个哈希值都相同的独特输入x，例如h(x) = h(x′)。[1]

抗碰撞性包含了次原像抗性，[1]但无法保证原像抗性。[1]相反，次原像攻击包含碰撞攻击（详细来说，除了x′，x在一开始就已知）。

应用的原像攻击

根据定义，使用最快方法计算出原像或次原像破解理想的杂凑函数的方法是使用暴力破解法。对于一个n位哈希，此攻击对于典型输出n = 128位的大小有着过高的时间复杂度2n。若这种复杂度最佳且可被被攻击者达到，这种哈希函数就被认为是抗原像的。然而，量子计算机可在√2n = 2n/2内执行原像攻击，也就意味着可进行次原像攻击[2]即碰撞攻击。

通过分析特定杂凑函数可找到对此函数更快原像攻击。学者找到了部分重大的原像攻击，但它们并不实际。若找到了实际的原像攻击，它将极大地影响诸多互联网协议。此例中，“实际”意味着可被攻击者使用可行数量的资源执行。例如，一个花费几万亿与数十年来找出一条哈希值或信息的原像攻击是不实际的；而一个仅花费几千块且只需要几周时间的攻击可能是非常实际的。

所有对MD5与SHA-1[3][4][5]已知的实际或近乎实际的攻击均为碰撞攻击。总之，碰撞攻击相比原像攻击更易进行，碰撞攻击不被任何设定的值（任意两个值均可用于碰撞）所限制。相反，碰撞攻击的时间复杂度为2n/2。

常用解决方案

为提高对原像攻击的抗性，双重散列是一种抵御某种情况攻击者破解了首个哈希的好策略。比特币系统使用双重散列SHA256[6]，一种2000年代减缓哈希破解的常见手段。

另请参阅

参考文献
  • IETF RFC 4270: 网络协议中对加密哈希的攻击
  1. Rogaway, P.; Shrimpton, T. (PDF). Fast Software Encryption (2004) (Springer-Verlag). [17 November 2012].
  2. http://cr.yp.to/hash/quantumsha3-20101112.pdf
  3. Bruce Morton, Clayton Smith. . CA Security Council. 30 January 2014.
  4. . 1 January 2009.
  5. . Google. [2017-02-23]. （原始内容存档于2017-04-24）.
  6. https://en.bitcoin.it/wiki/Block_hashing_algorithm
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.