HMAC 摘要在 RSA / ECDSA 簽名中有意義嗎？
當 MD5 和 SHA1 被破壞時，每次都會爭先恐後地升級軟體和證書以刪除有問題的算法。但是，在每種情況下，每個散列函式的 HMAC 變體都沒有受到影響。事實上，除非我遺漏了什麼，否則 HMAC-MD5 在技術上仍然是安全的。
在使用 RSA 或 ECDSA 對靜態數據進行簽名的情況下，性能不是關鍵因素，為了避免將來出現類似情況，使用 HMAC-SHA256 而不是普通 SHA256 作為摘要函式是否有意義？
像這樣的東西： $ s = k \mathbin\Vert S(k \mathbin\Vert H(m,k)) $ 在哪裡 $ S $ 是一些非對稱簽名操作，例如 RSA 或 ECDSA， $ k $ 是隨機生成的密鑰， $ H $ 是 HMAC-SHA256。
如果我們將 HMAC 視為消息身份驗證程式碼或 PRF，這不太有意義：MAC 或 PRF 的安全屬性假定偽造者不知道密鑰，但您已將密鑰給了他們 $ k $ 在簽名中。但是你有正確的直覺，這裡有些東西。
而在簽名方案方面 $ H(m) $ 需要 $ H $ 為了抗碰撞，隨機簽名方案 $ H(r, m) $ 需要 $ H $ 僅具有增強的目標抗碰撞性 eTCR的更為適度的特性，即使 MD5 仍可能表現出這種特性。 所以是的，面對像 MD5 和 SHA-1 這樣的散列的非密鑰衝突攻擊****，你的建議似乎確實提高了安全性。
顯然，如果您希望與使用 ECDSA 且無法修改的現有系統兼容，那麼這個想法對您沒有幫助。但是像 EdDSA 這樣的現代簽名方案將其用作設計的一部分，並且您始終可以調整現有的簽名方案來使用它——NIST 甚至在NIST SP 800-106，數字簽名的隨機散列中對其進行了標準化。HMAC 也可能用於此目的。
如果您想了解更多詳細資訊，這裡有很多歷史，所以請係好安全帶，笨蛋們，來一段故事時間吧！
早期歷史：拉賓簽名和散列的重要性。 歷史上第一個安全簽名方案，歸功於 Michael O. Rabin$$ 1 $$, 將公鑰作為一對 $ (n, b) $ 整數和消息上的簽名 $ m $ 成為一對 $ (s, u) $ 整數的 $ s $ 和一個位串 $ u $ 這樣$$ s\cdot(s + b) \equiv H(m, u) \pmod n. $$ 簽名者當然知道秘密因素 $ p $ 和 $ q $ 的 $ n = pq $ , 根據平方根模的計算 $ n $ 很便宜，特別是如果 $ p \equiv q \equiv 3 \pmod 4 $ . 散列和隨機化有兩個目的，Rabin 明確表示：
- 允許簽名者改變 $ u $ 直到 $ H(m, u) $ 完全承認方程的解 $ s $ .
- 降低簽名者意外揭示不同平方根的機率 $ s \ne s’ $ 的一個公共平方，這將揭示因式分解 $ n $ .
我們還可以添加一個 Rabin 可能覺得太明顯而無法說明的屬性：
- 壓縮長消息並破壞任何結構，例如整數完全平方，其整數平方根可用於偽造簽名。
目前尚不清楚是否考慮了利用碰撞的主動攻擊，但前提是 $ H $ 是抗碰撞的，假設合適的參數大小，Rabin 的方案在選擇消息攻擊下存在不可偽造性的現代標準（EUF-CMA）今天仍然是安全的。實際上， $ H $ 甚至可能不需要抗碰撞，但直到十年後的 Schnorr 才有人注意到這一點尚不清楚。在拉賓之後不久，休·C·威廉姆斯$$ 2 $$( paywall-free ) 展示瞭如何通過調整確定性地有效地計算平方類型簽名 $ p \equiv 3 \pmod 8 $ 和 $ q \equiv 7 \pmod 8 $ ，消除了為達到目的（1）而進行隨機化的需要。
散列、抗碰撞和離散對數簽名。 Taher Elgamal 最初在他的離散對數類型簽名方案中似乎已經失去了雜湊的重要性$$ 3 $$，因此很容易被破解——公鑰下的簽名 $ y $ 在一條消息上 $ m $ 是一對 $ (r, s) $ 整數使得$$ a^m \equiv y^r r^s \pmod p, $$例如，它承認微不足道的偽造 $ (0, 0) $ 在消息上 $ m = 0 $ 對於任何公鑰。( $ p $ 是標準模數和 $ a $ 是某個子群的標準生成器 $ \mathbb Z/p\mathbb Z $ .)
然而，並不是每個人都忽視了散列，到 80 年代後期，抗衝突散列的重要性已經浮出水面：在 Claus P. Schnorr 的離散對數類型簽名方案中$$ 4 $$, 其中公鑰下的簽名 $ v $ 在一條消息上 $ m $ 是一對 $ (e, y) $ 這樣$$ e = H(a^y v^e \bmod p, m), $$ Schnorr 觀察到雜湊函式 $ H $ 如果它是隨機的，則不必是抗碰撞的，因此可能是具有抗碰撞散列的 Elgamal 的天真組合的長度的一半，對於相同的安全性。**
NSA——嗯，我的意思是NIST——認識到數字簽名標準 FIPS 186 中**固定散列中抗碰撞性的重要性，但小心翼翼地做出了與 Schnorr 的每一個好的設計決定相反的事情$$ 5 $$因為害怕侵犯專利，包括散列的隨機化。當然，他們還使 DSA 在製作簽名時容易受到不良 RNG 的攻擊，而同時代密碼學家的強烈反對被 NIST 隨便置之不理。$$ 6 $$.
可證明的安全性和行業標準化：RSA-PSS 和 RSA, Inc. 早期的 RSA 標準化（如 PKCS#1 v1.5）使用一種特殊的方式將消息散列塞入 $ \mathbb Z/n\mathbb Z $ ——具體來說，進入一個極小的稀疏子空間 $ \mathbb Z/n\mathbb Z $ 這對於計算難度的學習是無用的 $ e^{\mathit{th}} $ 的均勻隨機元素的根 $ \mathbb Z/n\mathbb Z $ ，這是 RSA 問題，可能比 RSASSA-PKCS1-v1_5 問題更深入地研究。
1996 年，Mihir Bellare 和 Phil Rogaway$$ 7 $$研究了 RSA 和 Rabin 類型簽名方案的安全性，它更類似於現代的“可證明安全性”框架——展示瞭如何使用偽造者作為其他廉價算法中的子程序來計算 $ e^{\mathit{th}} $ 根模 $ n $ , 或因子 $ n $ 在平方型方案的情況下。他們能夠證明，如果 $ H $ 涵蓋整個 $ \mathbb Z/n\mathbb Z $ , 然後偽造簽名 $ s $ 滿足簽名方程$$ s^e \equiv H(m) \pmod n $$稱為 RSA-FDH，可用於計算 $ e^{\mathit{th}} $ 根模 $ n $ .
然而，Bellare 和 Rogaway 對他們證明的特定定理並不滿意，因為在您簽署大量消息的情況下，適度成功機率的高成本意味著沒有任何意義。所以他們考慮了一種隨機變體，一種機率簽名方案或 PSS，帶有簽名方程$$ s^e \equiv \bigl[r \mathbin| H(r \mathbin| m)\bigr] \pmod n, $$大致。PSS 中的隨機化使他們能夠輕鬆地證明一個更強的定理。* 他們還在他們的 IEEE P1363 提案中觀察到$$ 8 $$使用 $ H(r \mathbin| m) $ 似乎沒有依靠抗碰撞性 $ H $ . 但實際上標準化的東西改為使用 $ H(r \mathbin| H(m)) $ , 這很容易受到碰撞 $ H $ . 特別是，這在 2000 年的 IEEE P1363 中被標準化（免費；§12.1.2 ‘EMSA2’，第 60-61 頁）和 RSA, Inc.在 2002 年的 PKCS #1 v2.1 中（§9.1’ EMSA-PSS’，第 33-36 頁）。
巧合的是，我敢肯定，這與 NSA 向 RSA, Inc. 捐贈 1000 萬美元的時間差不多，以鼓勵他們將非常優秀的 Dual_EC_DRBG 部署給他們的 BSAFE 客戶$$ 9 $$. 不久之後——從公共記錄中不清楚確切的時間，但幾乎可以肯定不遲於 2007 年——美國和以色列政府利用了 MD5 碰撞攻擊$$ 10 $$在針對伊朗的國際工業破壞事件中偽造程式碼簽名證書上的簽名。哎呀。
規範化和標準化碰撞恢復能力。 1989 年，Moni Naor 和 Moti Yung 引入了通用單向雜湊函式或UOWHF$$ 11 $$形式化人們對數字簽名的隨機散列的期望：如果對手送出 $ m $ 前面，然後給出 $ r $ , 很難找到 $ m’ \ne m $ 這樣 $ H(r, m’) = H(r, m) $ ——本質上是第二原像抵抗的受限情況。1997 年，Bellare 和 Rogaway 進行了出色的創新，為這個概念賦予了一個更明顯和更容易記住的名稱，即目標碰撞阻力或TCR$$ 12 $$，但儘管品牌更名，但十年來這一概念幾乎沒有受到關注。
然後，在 2000 年代中期，當抗碰撞的基礎在接縫處破裂時，密碼學家開始尋找繞過它的方法，並對 Naor 和 Yung 以及 Bellare 和 Rogaway 的舊捲進行除塵。
- Phil Rogaway 和 Tom Shrimpton 全面研究了密鑰散列函式的各種安全標準概念之間的關係——碰撞抵抗、原像抵抗、第二原像抵抗等——並證明了含義並給出了非含義的反例$$ 13 $$; TCR 在他們的工作中具有“eSec”或“無處不在的第二原像抗性”的特點。
- Shai Halevi 和 Hugo Krawczyk 研究了簽名的隨機化$$ 14 $$，並發明了一種更好的 TCR 版本，稱為增強的目標碰撞阻力或eTCR：如果對手送出 $ m $ 前面，然後給出 $ r $ , 很難找到 $ (r’, m’) \ne (r, m) $ 這樣 $ H(r’, m’) = H(r, m) $ . 這對於隨機化的簽名方案很重要 $ r $ 不像在 PSS 中那樣自然地出現，因此對手有控制它的自由度 - 正如您建議的 HMAC 通過隨機化加強簽名的一般用途一樣。他們提出了一種稱為 RMX 的通用結構$$ 15 $$，向 IETF 送出了一份現已過期的網際網路草案$$ 16 $$，並說服 NIST 將其標準化為NIST SP 800-106。
Bellare 和 Rogaway 觀察到通常的 Merkle-Damgård 結構並不能保證 TCR，這就是 Halevi 和 Krawczyk 提出 RMX 的原因。但是，即使在MD5 和 SHA-1 等中發現了衝突，似乎也沒有太多證據表明它們沒有表現出 eTCR *。*因此，雖然 Merkle-Damgård 結構並不意味著 eTCR，但使用的設計原則 $ H(r \mathbin| m) $ 代替 $ H(m) $ 在簽名中已被 EdDSA 等較新的方案採用$$ 17 $$遵循 Schnorr 在 1989 年的觀察。這似乎不太可能 $ \operatorname{HMAC-}!H_r(m) $ 即使對於 eTCR 也會失敗 $ H = \operatorname{MD5} $ 或者 $ H = \operatorname{SHA1} $ .
結論。 今天，除非有特殊需求，否則只有一種新應用程序應該使用的簽名方案：Ed25519，它在設計上內置了這種碰撞恢復能力。遺留應用程序可能會被 DSA 或 RSASSA-PSS 等簽名方案卡住，這些簽名方案在設計上內置了衝突漏洞，但如果你只是部分卡在遺留系統上——你不能使用新的簽名原語，因為你有審計員對 FIPS 大喊大叫，但您可以以一種新的方式使用傳統簽名原語 — 您可以通過使用 RMX 或 HMAC 或什至使用簡單前綴隨機化它來使其具有抗衝突能力 $ H(r \mathbin| m) $ .
隨機化在這些定理中的作用有點特殊。即使是一點點隨機化，顯然也會影響關於定理的緊密度 $ e^{\mathit{th}} $ 根方案，但不是平方根方案$$ 18 $$，這應該引起一些人對多年來致力於這種單一隨機化的可證明安全文獻的努力，而美國和以色列幾乎同時實際上利用*MD5 中的碰撞來偽造真實標準的簽名破壞伊朗的核計劃。