N位HMAC的安全性
假設我使用的是 128 位 HMAC。需要多少操作才能找到*“非安全”*消息。生日攻擊可能嗎？
簡短的回答是： $ 2^{128} $ 操作，沒有已知的生日式攻擊。
**答案很長：**當 HMAC首次發佈時，它附帶了一個安全證明，專為Merkle-Damgård等迭代結構量身定制。在 MD 散列函式（MD4、MD5 和整個 SHA 系列都是 MD 散列函式）中，要散列的數據由具有壓縮函式的塊處理：壓縮函式將塊和目前狀態（狀態是具有 128 位輸出的函式的 128 位值），並產生新狀態（將用作處理下一個塊的輸入）。最終狀態是函式輸出。
原始證明聲稱，如果壓縮函式是 PRF（即塊值的選擇“選擇”壓縮函式，就好像在將狀態作為輸入並產生相應輸出的函式中隨機地一樣）並且雜湊函式是衝突的-抵抗（以“弱”的方式；它不需要抵抗各種衝突），那麼 HMAC 是安全的。該證明達到了 $ 2^{n/2} $ 壓縮函式的呼叫（對於具有 $ n $ 位輸出）。後來，Bellare 發布了一個新的安全證明，它消除了弱碰撞阻力的條件，並將經過驗證的安全性提高到 $ 2^{n} $ .
現在是細則：安全證明只有在 PRF 假設成立時才有效。然而，如果 PRF 假設成立，那麼在 MD 構造中使用該壓縮函式的雜湊函式必然能夠抵抗高達 $ 2^{n/2} $ . 因此，如果一個類似 MD 的散列函式被證明不具有抗碰撞性 $ 2^{n/2} $ , 那麼這意味著它的底層壓縮函式並不像它應該的那樣 PRF。尤其是對於 MD4、MD5、SHA-0 和 SHA-1，情況確實如此。對於這些函式，PRF 假設不成立，因此 HMAC 安全證明不適用於 HMAC/MD4、HMAC/MD5、HMAC/SHA-0 和 HMAC/SHA-1。這並不意味著我們知道將碰撞攻擊轉變為對 HMAC 的攻擊的方法。確實沒有已知的攻擊速度比 $ 2^{128} $ 在 HMAC/MD5 上。然而，對 HMAC/MD4存在已知的偽造攻擊。請注意，此攻擊有成本 $ 2^{58} $ ，這是相當多的（並解釋了為什麼從未實際展示過攻擊），而 MD4 對沖突的抵抗力本身為零（與簡單地對兩條消息進行散列以驗證它是否有效相比，產生衝突所需的時間更少）。
此外，所有這些證明都是針對類似 MD 的結構，並不直接應用於非 MD 函式。然而，可以說 HMAC 被定義為它的兩個嵌套散列函式呼叫，正是為了克服 MD 構造的一些缺點。因此，“沒有理由”為什麼非 MD 散列函式在 HMAC 中表現不佳。當在 HMAC 中使用時，大多數SHA-3 候選包括聲明和/或雜湊函式的安全性證明。