SHA 1 的“單向性”
我最近開始第一次學習雜湊函式，並且我已經經歷並試圖理解 SHA1 過程。
Brilliant 在逐步解釋它方面做得非常出色。
https://brilliant.org/wiki/secure-hashing-algorithms/
據我了解，散列函式旨在抗碰撞並且很難進行反向計算，即使人們知道確切的過程。
雖然我可以看到這個過程，但對於還不太了解密碼學的我來說，這個過程似乎非常隨機——就好像一個醉酒的人被要求對一堆比特進行數學運算。
我真的看不出在 SHA 1 中採取的精確步驟的動機……
- 這些步驟如何使它抗碰撞？
- 是什麼讓“反算”變得困難？
- 為什麼這個過程……它是什麼？為什麼不是其他一些“隨機數學運算”？
SHA-1 與早期的 MD5 和 SHA(-0) 以及後來的 SHA-2 一樣，是根據精心設計的分層設計建構的：
- 外部的Merkle-Damgård，使用基於固定寬度壓縮函式的安全參數建構抗碰撞+原像雜湊。
- Davies-Meyer建構了該壓縮函式，其安全參數基於具有強相關密鑰安全性的塊密碼（消息塊是密鑰）。
- 不平衡 Feistel 輪次的迭代以建構該分組密碼。
- 一種加/輪換/異或(ARX) 策略，有選擇地添加 Shift/AND 以實現分組密碼及其密鑰調度的必要非線性輪函式。
唯一明顯隨意的方面是多個非線性函式在 20 輪後發生變化。這是從 MD5 繼承的一個想法，它對 SHA(-0) 或 SHA-1 沒有太大幫助。它在 SHA-2 中被刪除，有利於結合幾個非線性函式的統一圓形函式。這是一個合理的舉動。
我們可以將基於 Merkle-Damgard(MD) 的散列函式（如 MD4、MD5、SHA-1、SHA-256、SHA-512 和衍生物）視為旋轉分組密碼，其中密鑰是消息，輸入是先前的狀態.
更正式一點，對於 SHA-1，有一個名為 SHACAL 的分組密碼，它以 512 位密鑰和 160 位分組作為輸入。然後 MD 構造在初始值固定的迭代模式中使用這個分組密碼。我們也可以認為這個內部分組密碼是一個壓縮函式；
$$ c:{1,0}^{160}\times{1,0}^{512} \to{1,0}^{160} $$可以看到命名很清楚，輸入空間大於輸出空間。因此，如果沒有一些外部知識，就無法弄清楚實際的輸入消息（這裡是密鑰），因為一些資訊失去了。
同樣從雜湊函式中，我們還要求
- **位依賴：**輸出的每一位依賴於輸入的每一位。
- **雪崩：**輸入中的單個位更改必須隨機更改 ≈ 一半的位。
- **非線性：**防止攻擊線性系統求解技術。
- 是什麼讓“反算”變得困難？
考慮內部塊密碼的最後一次迭代進行雜湊計算，然後給定一個雜湊值，即使輸入其他 160 位，也必須找到 512 位。換句話說，您需要破解分組密碼。顯然，您不能搜尋 512 位。即使您發現一些弱點，您的問題也將是壓縮。壓縮不是簡單的修整，它需要仔細考慮的算術決策。簡而言之，非線性和壓縮。
這也稱為原像攻擊
- 給定一個雜湊值 $ h $ 找消息 $ m $ 這樣 $ h=\operatorname{Hash}(m) $
並要求 $ \mathcal{O}(2^n) $ 用於 n 位輸出雜湊函式。
- 這些步驟如何使它抗碰撞？
在抗碰撞性中，應該很難找到兩個不同的資訊 $ m $ 和 $ m’ $ 這樣 $ \operatorname{Hash}(m) = \operatorname{Hash}(m) $ 對於計算有界的對手。
由於鴿巢原則，雜湊衝突是不可避免的。使用生日悖論，我們會發現與 50% 後的碰撞 $ \sqrt{n} $ 嘗試。經典碰撞攻擊有 $ \mathcal{O}(2^{n/2}) $ 複雜。
因此，必要條件之一是輸出大小、位相關性、雪崩和非線性是其他一些必要條件。我們可以說沒有充分條件，因為攻擊類型沒有限制。
而且，事實證明 SHA-1 具有相同前綴衝突攻擊
- 為什麼這個過程……它是什麼？為什麼不是其他一些“隨機數學運算”？
密碼結構不依賴於隨機過程或選擇。我們需要評估提供的安全性。我們需要根據安全要求來分析建構。而且，相反的情況已經通過例子證明了。
例如; 經過多年關於 NSA 修改 DES S-Box 的爭論，經過Coppersmith精心設計的研究，我們知道我們不能通過選擇 S-box 來使 DES 更安全，實際上，它會變得不那麼安全或損壞。
SHA 1 的“單向性”
一個小筆記;
我們知道，如果有一個單向函式，那麼 $ \mathcal{P}\neq \mathcal{NP} $ . 因此，研究人員要麼還沒有展示出一個，要麼根本不存在。