破解 HMAC-MD5 需要多少次試驗？
我知道您可以
2^64通過使用生日悖論的試驗在 MD5 中找到碰撞。現在每個人都在說 HMAC-MD5 明顯更安全。我如何量化這種安全性？我的問題是需要多少次試驗才能在 HMAC-MD5 中找到碰撞？
您可以在 MD5 中以比 $ 2^{64} $ MD5的評價。如果您知道密鑰，您可以對 HMAC-MD5 執行相同的操作，這使得它不適合不尋常的應用程序，例如承諾。
但是 HMAC-MD5 的標準安全猜想是它是一個偽隨機函式族，假設攻擊者不知道密鑰。對手編寫的任何將函式作為參數並在其選擇的任意消息上將其評估為預言機的程序都不會有太大的不同，無論您是否在統一隨機選擇的密鑰下提供（a）HMAC-MD5，或（ b) 函式的統一隨機選擇。
f0_memo = {} def f0(x): if x not in f0_memo: f0_memo[x] = os.urandom(16) return f0_memo[x] k = os.urandom(32) def f1(x): return hmac_md5(k, x) def distinguisher(prf): y0 = prf('hello world') y1 = prf('query query quite contrary how does your crypto grow') ... return 1 if i_predict_it_was_f1 else 0 # Then the probability that distinguisher(f0) = 1 is not much different # from the probability that distinguisher(f1) = 1.形式上，我們定義了隨機算法的PRF 優勢 $ D $ 區分函式族 $ f_k $ （例如， $ \operatorname{HMAC-MD5}_k $ ) 從均勻隨機變為： $$ \begin{equation*} \operatorname{Adv}^{\operatorname{PRF}}f(D) = \lvert\Pr[D(f_k) = 1] - \Pr[D(u) = 1]\rvert, \end{equation*} $$ 在哪裡 $ k $ 是家庭的統一隨機密鑰 $ f_k $ ， 和 $ u $ 是均勻隨機函式。我們推測對於任何區分算法 $ D $ , $ \operatorname{Adv}^{\operatorname{PRF}}{\operatorname{HMAC-MD5}}(D) $ 足夠小，我們不擔心任何人都可以利用它，只要計算成本 $ D $ 在合理範圍內——少於 $ 2^{128} $ 位操作，例如。這種形式主義稍後會派上用場，但讓我們先看看區分策略。
讓我們假設 $ k $ 長度為 256 位。對於 MD5，它可能長達 512 位並填充整個塊，或者在技術上更長，但是使用填充或超過 HMAC 中的塊的密鑰存在問題，而 256 位對於嚴重的安全性來說是完全足夠的。
你可以嘗試猜測 $ k $ 並查看是否在某些消息中評估 oracle $ x $ 產量 $ \operatorname{HMAC-MD5}k(x) $ ， 但是這裡有 $ 2^{256} $ 的可能性 $ k $ ，使得該策略在計算上是不可能的——儘管形式上我們可以得出結論，存在一個區分器 $ D $ 只查詢一次預言機，這樣 $ \operatorname{Adv}^{\operatorname{PRF}}{\operatorname{HMAC-MD5}}(D) = c/2^{256} $ ， 在哪裡 $ c $ 是次數 $ D $ 有能力計算 HMAC-MD5。*
碰撞怎麼辦？ 如果您在 $ 2^{64} $ 不同的輸入，你可能會發現碰撞。對於統一隨機密鑰下的 HMAC-MD5和統一隨機函式來說都是如此，因此先驗地發現衝突不會通過單獨區分 PRF 來破壞 PRF 的安全性。 但是，MD5也有這樣的性質，如果 $ x_0 \ne x_1 $ 在 MD5 下碰撞，與 $ \operatorname{MD5}(x_0) = \operatorname{MD5}(x_1) $ , 那麼也這樣做 $ x_0 \mathbin\Vert y $ 和 $ x_1 \mathbin\Vert y $ 對於任何常見的後綴 $ y $ ， 只要 $ x_0 $ 和 $ x_1 $ 有相同的長度。
因此，如果您以驚人的速度查詢 oracle $ q = 2^{64} $ 輸入，很有可能你會發現碰撞 $ x_0 \ne x_1 $ ; 然後判斷 oracle 是 HMAC-MD5 還是統一隨機函式，選擇一個後綴 $ y $ ，比如說一個有趣的貓影片的單個零位或 GIF，然後在另外兩個輸入處查詢預言機： $ x_0 \mathbin\Vert y $ 和 $ x_1 \mathbin\Vert y $ . 如果它們仍然發生碰撞，則有壓倒性的證據支持 HMAC-MD5，而不是統一的隨機函式。† 特別是，條件機率 $ x_0 \mathbin\Vert y $ 和 $ x_0 \mathbin\Vert y $ 對於 HMAC-MD5，collides 為 1，並且 $ 2^{-128} $ 為均勻隨機函式。對於任意數量的查詢 $ q $ 用這個區分符，根據生日悖論，$$ \Pr[D(\operatorname{HMAC-MD5}_k) = 1] \approx q^2!/2^{128}. $$
事實證明，這種針對任何迭代散列函式的 HMAC通用攻擊是對 HMAC-MD5 的 PRF 安全性的最著名攻擊。（在統一隨機函式上，HMAC-MD5 與“HMAC”還有其他區別，但這對於下面的 MAC 之類的應用來說並不重要，而且它們的面積時間成本非常大，遠遠超過 $ 2^{128} $ .) 所以 HMAC-MD5 的安全猜想是$$ \operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) \leq q^2!/2^{128} + c/2^{256} $$對於任何隨機算法 $ D $ 最多做 $ q $ 最多具有面積時間成本的查詢 $ c $ . 而且因為 $ 2^{256} $ 是一個非常大的分母，你沒有足夠的零錢在你的口袋裡嘎嘎作響，買不起一台足夠大的電腦，足夠長的時間來影響它，所以我們可能會完全跳過這個術語並稱它為 $ q^2!/2^{128} $ .‡
在應用程序中使用 HMAC-MD5 怎麼樣，例如作為消息驗證碼？ 事實證明，任何偽隨機函式族都是很好的消息驗證碼。消息身份驗證程式碼的安全目標是不可偽造性：如果在查詢預言機以了解身份驗證器之後，對手獲勝 $ q $ 根據他們選擇的消息，他們可以在以前未發送到 oracle的消息上偽造身份驗證器。
def forger(mac): y0 = mac('hello world') y1 = mac('The Magic Words are Lightning Sloth Race') ... return (authenticator, 'another message')如果偽造者獲勝的機率可以忽略不計，則 MAC 是安全的，我們正式將其定義為隨機算法的MAC 優勢 $ F $ 在偽造認證器時：$$ \operatorname{Adv}^{\operatorname{MAC}}_f(F) = \Pr[(a, m) = F(f_k), f_k(m) = a], $$對於任何隨機算法 $ F $ 返回一條它沒有發送到預言機的消息。如上所述，偽造者可以送出 $ 2^{64} $ 向 oracle 查詢並可能發現衝突 $ x_0 \ne x_1 $ ; 然後查詢 oracle 以找到身份驗證器 $ x_0 \mathbin\Vert y $ , 並將其偽造為消息的身份驗證器 $ x_1 \mathbin\Vert y $ . 這是唯一的方法嗎？我們可以直接研究偽造 HMAC-MD5 的策略，但是如果我們接受 HMAC-MD5 的 PRF 安全性，使用上面的形式，可以更簡單地理解 HMAC-MD5 的 MAC 安全性。
假設我們有一個成功的偽造子程序，並且成功的機率 $ p $ . 然後我們可以定義一個區分器：
def make_distinguisher(forger): def distinguisher(f): a, m = forger(f) return 1 if f(m) == a else 0 return distinguisher如果 $ f $ 是統一隨機密鑰下的HMAC-MD5，偽造者成功，區分者有機率返回1 $ p $ . 如果 $ f $ 是均勻隨機函式，區分器以機率返回 1 $ 1/2^{128} $ ，因為任何固定的 128 位字元串的機率 $ a $ 等於 $ f(m) $ 什麼時候 $ f $ 是均勻隨機函式 $ 1/2^{128} $ . 所以我們有 $$ \begin{align*} \Pr[D(f_k) = 1] &= p = \operatorname{Adv}^{\operatorname{MAC}}{\operatorname{HMAC-MD5}}(F), \ \Pr[D(u) = 1] &= 1/2^{128}, \end{align*} $$ 我們從中發現$$ \operatorname{Adv}^{\operatorname{PRF}}{\operatorname{HMAC-MD5}}(D) = \lvert\operatorname{Adv}^{\operatorname{MAC}}{\operatorname{HMAC-MD5}}(F) - 1/2^{128}\rvert. $$ 但是 HMAC-MD5 的安全猜想是 $ \operatorname{Adv}^{\operatorname{PRF}}{\operatorname{HMAC-MD5}}(D) $ 對於任何區分器來說都非常小 $ D $ . 我們可以用它來推測偽造機率也必須非常小：$$ \operatorname{Adv}^{\operatorname{MAC}}{\operatorname{HMAC-MD5}}(F) \leq \operatorname{Adv}^{\operatorname{PRF}}{\operatorname{HMAC-MD5}}(D) + 1/2^{128}. $$
那麼，查找 HMAC-MD5 衝突的成本是多少？ 在不知道密鑰的情況下，攻擊者可以在大約 $ 2^{64} $ 生日悖論的審判。有了密鑰的知識，這是一個客廳把戲，但如果你告訴對手你的密鑰，你就違反了 HMAC-MD5 的安全契約。我建議在附近的任何應用程序中避免使用 HMAC-MD5 $ 2^{64} $ 消息在一個鍵下！我還建議不要告訴對手你的密鑰。
如果 $ D $ 嘗試 1000 個密鑰，顯然比只嘗試 1 個成功的機會更高，但是嘗試 1000 個密鑰的成本更高，無論是在一台電腦上順序嘗試還是在一千台電腦上並行嘗試。注意多目標*攻擊 $ n $ 一次目標可能比 $ n $ 單獨的單目標攻擊，但對於 256 位密鑰，差異對於所有可以想像的目標數量都無關緊要 $ n $ 在人類存在中。但要小心使用帶有 128 位密鑰的 HMAC-MD5！
†當然，完全相同的策略將任何迭代雜湊函式與統一隨機函式區分開來，但不會區分兩個不同的迭代雜湊函式！它也可以是 HMAC-HAVAL128 或其他任何具有 128 位狀態的東西。這不是偽隨機函式族的安全聲明所關心的問題，它只是將所討論的族（HMAC-MD5）與相同域和共域的統一隨機函式區分開來。
‡聽起來成本可能很高 $ c $ 儲存預言機的所有輸出以在它們之間搜尋衝突，但實際上沖突搜尋可以通過使用Pollard 的可忽略不計的額外計算和儲存來完成 $ \rho $ ，並且，如果預言機允許，可以使用van Oorschot-Wiener 算法並行化以更快地執行（以相同的總成本）。