給定雜湊函式的安全性
我們有一條消息表示 $ M $ . 讓我們假設我們有一個抗碰撞的散列函式 $ h_0 $ 帶輸出長度 $ n $ . 然後我們考慮另外兩個獨立（不同）的雜湊函式 $ h_1 $ 和 $ h_2 $ , 輸出長度 $ n/2 $ . 例如，我們可以選擇 SHA-256 $ h_0 $ ，以及帶有截斷輸出（128 位）的 SHA-256 $ h_1 $ 和 $ h_2 $ . 注意 $ h_1 $ 和 $ h_2 $ 通過域分離獲得，即 $ h_1=\operatorname{lsb}{128}(\mathrm{SHA256}(M| 1)) $ 和 $ h_2=\operatorname{lsb}{128}(\mathrm{SHA256}(M|2)) $ .
我們現在考慮雜湊函式 $ h_3 $ :
$$ h_3(M)=h_1(h_0(M)) | h_2(h_0(M)) $$ 我已經讀過，當消息很長時，應用在同一條消息上的兩個獨立散列函式的串聯不會增加安全性。以上怎麼辦 $ h_3 $ 功能，與 $ h_0 $ ? 在抗碰撞性和抗二次原像性方面。
$ h_3 $ 最多與碰撞和第二原像抗性一樣 $ h_0 $ .
證明：
假設我們有一個碰撞 $ h_0 $ ，也就是說，我們知道 $ x\neq y $ 和 $ h_0(x)=h_0(y)=h $ . 現在觀察 $ h_3(x)=h_3(y) $ 如下：
$$ h_3(x)=h_1(h_0(x))\parallel h_2(h_0(x))=h_1(h)\parallel h_2(h)=h_1(h_0(y))\parallel h_2(h_0(y))=h_3(y) $$
既然我們已經確定了 $ h_3 $ 再安全不過了 $ h_0 $ ，讓我們看看“下限”。讓 $ c_i $ 是布爾變數，指示雜湊函式上的衝突 $ h_i $ 是已知的。那麼以下成立：
$$ c_3\rightarrow c_0\oplus(c_1\land c_2) $$ （和 $ \oplus $ 表示異或） 那是， $ h_3 $ 至少與 $ h_0 $ 或( $ h_1 $ 和 $ h_2 $ ）。這假設雜湊函式之間沒有細微的相互作用，這將有助於結構引導衝突搜尋。
假設我們在 $ h_3 $ ，也就是我們知道 $ x\neq y $ 這樣 $ h_3(x)=h_3(y) $ . $ h_3(x)=h_3(y) $ 暗示 $ h_1(h_0(x))=h_1(h_0(y)) $ 和 $ h_2(h_0(x))=h_2(h_0(y)) $ （通過簡單的分解），所以我們會發現碰撞 $ h_1 $ 與價值觀 $ h_0(x) $ 和 $ h_0(y) $ 和碰撞 $ h_2 $ 具有相同的值。這假設 $ h_0(x)\neq h_0(y) $ 被允許稱為適當的碰撞。如果不是這種情況，我們會發現碰撞 $ h_0 $ 反而。所以我們有 $ c_0\oplus (c_1\land c_2) $ 是真的，從 $ c_3 $ 是真的。
實際上，發現碰撞的右側比散列函式上的正常碰撞更有價值。因為我們在兩個雜湊函式上都發現了碰撞，相當於在兩個雜湊函式上發現了碰撞 $ h’(M)=h_1(M)\parallel h_2(M) $ 在問題中給出的約束條件下 $ n/2 $ 位安全。
那麼以上所有的意思是什麼？
- 如果你能打破 $ h_0 $ 你可以打破 $ h_3 $ .
- 如果你能打破 $ h_3 $ 你可以打破 $ h’ $ 或者 $ h_0 $ .
- 如果要麼 $ h_1 $ 或者 $ h_2 $ 是一個排列，然後打破 $ h_3 $ 和打破一樣難 $ h_0 $ .
- 如果你能打破 $ h’ $ 你可以輕易打破 $ h_1 $ 和 $ h_2 $ .
- 兩次“正常”碰撞 $ h_1,h_2 $ 很可能不足以打破 $ h’ $ .
- 發生碰撞 $ h’ $ 很可能不會產生碰撞 $ h_3 $ （因為您仍然需要找到關於 $ h_0 $ ).
- 如果 $ h_0,h_1,h_2 $ 缺乏結構性弱點， $ 2^{n/2} $ 操作需要打破 $ h_3 $ （這是預期值）。
外行的閱讀提示：“如果你能打破 x 那麼你可以$$ logical formula involving breaks of $y_i$ $$” 需要雙方都否定，然後雙方需要交換安全聲明。那是“如果$$ negated logical formula $$是安全的，所以 x"。