原像攻擊
 |
原像攻擊（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）.
