隨機散列如何擊敗碰撞攻擊？
SEC#1 建議在將 SHA-1 與 ECDSA 結合使用時進行隨機散列；SPHINCS+ 在 WOTS+ 中使用隨機散列來抵禦碰撞攻擊，從而減少簽名大小。
隨機散列如何擊敗碰撞攻擊？有什麼限制？
在基於 Merkle-Damgard 的散列函式（如 MD5、SHA1、SHA2）的隨機散列中，輸入在應用散列之前用鹽預處理。該過程不修改底層雜湊函式，將其用作黑盒，由 Shai Halevi 和 Hugo Krawczyk 於 2007 年提出；
對於基於 MD 的雜湊函式。他們將目標防撞（TCR）定義為：
雜湊函式族 $ {H_r}_r\in R $ （對於一些集合 $ R $ ) 如果沒有有效的攻擊者，則目標是抗碰撞的 $ A $ 可以贏得以下比賽，但機率很小：
- A選擇第一條消息 $ M $ ，然後接收一個隨機值 $ r \in_R R $ ，它需要找到第二條消息 $ M’ \neq M $ 這樣 $ H_r(M_0) = H_r(M) $ . 價值 $ r $ 被稱為散列鍵或鹽。
他們還定義了增強的抗目標碰撞（eTCR），因為像 DSA 這樣的簽名方案不支持對 salt 進行簽名 $ r $ . 為了支持這一點，他們使用放鬆條件來加強操作模式。這個方案是
即使我們僅將基礎簽名應用於 $ H_r(M ) $ 並且不要在鹽上簽名 $ r $ .
遊戲玩法如下；
- A選擇第一條消息 $ M $ ，然後接收一個隨機值 $ r \in_R R $ ，鹽 r，攻擊者可以提供第二條消息 $ M’ $ 和第二種鹽 $ r’ $ ，並且如果它被認為是成功的 $ (r, M ) \neq (r’, M’ ) $ 但 $ H_r (M ) = H_{r’} (M’) $ .
它需要找到第二條消息 $ M’ \neq M $ 這樣 $ H_r(M_0) = H_r(M) $ . 價值 $ r $ 被稱為散列鍵或鹽。
他們定義了兩種方法：
- $$ H_r^c(m_1, \ldots , m_L) \overset{def}{=} H^c(m_1 \oplus r,\ldots, m_L\oplus r). $$該方案是第二原像抗性 (SPR) *下的 TCR 。這適合 RSA 簽名，因為我們可以擴展模數，使得 $ r $ 也可以簽。
- 下面的方案也是 SPR 下的 eCTR *，這對於類似 DSA 的算法很有用，其中籤署了額外的數據， $ r $ ， 不簡單。
$$ \tilde{H_r^c}(M)\overset{def}{=} H_r^c(0|M) = H^c(r, m_1 \oplus r,\ldots, m_L\oplus r). $$
他們設計了他們的方案，使得生成的簽名方案的安全性不依賴於散列函式對離線衝突攻擊的抵抗力。簡而言之，他們將方案的安全性與壓縮函式的第二原像抗性聯繫起來。
實際上，證明依賴於與 SPR 相關的兩個屬性。e-SPR是真實的抗碰撞硬度 $ H_r $ 和 $ \tilde{H_r} $ . 並且，c-SPR，與抗碰撞等級有關*。
**注 1：**有一個網頁顯示瞭如何將這種方法和類似方法輕鬆應用於 NSS 庫和 Firefox。
**注2：**論文的擴展版在這裡（不是https！）