原像攻击
 |
原像攻击（Preimage attack）是密码学中的一种破译手段，用于密码散列函数上寻找含有特定哈希值的消息。一个密码散列函数应抵御对其原像的攻击。
在攻击情形下存在两种原像抗性：
- 原像抗性：对于所有预设输出，从计算角度应无法找到符合输入哈希的输出。例如，给定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.0 1.1 1.2 1.3 1.4 Rogaway, P.; Shrimpton, T. Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance (PDF). Fast Software Encryption (2004) (Springer-Verlag). [17 November 2012]. （原始内容存档 (PDF)于2013-12-05）.
- ^ 存档副本 (PDF). [2018-08-09]. （原始内容存档 (PDF)于2021-01-11）.
- ^ Bruce Morton, Clayton Smith. Why We Need to Move to SHA-2. CA Security Council. 30 January 2014 [2018-08-09]. （原始内容存档于2021-01-12）.
- ^ MD5 and Perspectives. 1 January 2009 [2018-08-09]. （原始内容存档于2020-11-09）.
- ^ Google Online Security Blog: Announcing the first SHA1 collision. Google. [2017-02-23]. （原始内容存档于2017-04-24）.
- ^ 存档副本. [2018-08-09]. （原始内容存档于2021-02-13）.
