消息偽造和頻寬中的 GMAC 與 HMAC
Saarinen 在他的作品GCM、GHASH 和 Weak Keys中說：
GHASH 算法屬於廣泛研究的一類Wegman-Carter 多項式通用雜湊。這些算法的已知安全界限（this和this）表明 $ n $ -bit 標籤會給 $ 2^{−n/2} $ 防偽安全。
可以說，通用雜湊為了方便而犧牲了一些通信頻寬，因為傳統的基於雜湊的 MAC 旨在達到資訊論 $ 2^{−n} $ 防止消息偽造。
- 通用雜湊提供了什麼便利？
- 通訊增加多少 GHASH？
- 為什麼不應該使用資訊論綁定的 HMAC 而應該使用較小的 HMAC？
- 由於 GHASH 最多提供 $ 2^{64} $ TLS 1.3 中的防偽安全性，這是無法更改的標準，是否有任何其他套件可以提供資訊理論上的防偽安全性。
注意：他還說
在本文中，我們進一步證明這不僅是安全下限，也是上限。（對於通用雜湊）
Saarinen 在他的作品GCM、GHASH 和 Weak Keys中這樣說；
這篇論文不是很清楚，並且導致許多人對通用雜湊驗證器感到遺憾的困惑。
這篇論文——你引用的手稿和FSE 2012 的會議論文——包含誤導性聲明和錯誤歸因；描述了僅適用於標準安全廣告中安全使用範圍之外的攻擊；並提出了一種既不會提高偽造機率也不會解決 GCM 在安全性或性能方面的任何實際問題的補救措施。
這篇論文沒有指出 GCM 的三個主要現實缺點：截斷標籤的危險，因為 $ O(\ell/2^n) $ 偽造機率中的術語而不是 $ O(1/2^n) $ 為了 $ n $ - 長度最多為消息的位標記 $ \ell $ ; 使用分組密碼產生的偽造機率的二次項（它被錯誤地歸因於通用散列）；以及軟體中恆定時間 GHASH 評估（以及 AES 評估）的高昂成本，這會導致通過時間洩露秘密。
> > GHASH 算法屬於廣泛研究的一類Wegman-Carter 多項式通用雜湊。這些算法的已知安全界限（this和this）表明 $ n $ -bit 標籤會給 $ 2^{−n/2} $ 防偽安全。 > > > 可以說，通用雜湊為了方便而犧牲了一些通信頻寬，因為傳統的基於雜湊的 MAC 旨在達到資訊論 $ 2^{−n} $ 防止消息偽造。 > > >
這些陳述充其量都是誤導性的，如果從字面上看，這些陳述都是錯誤的。
通用雜湊都不是$$ 1 $$（免付費牆：(a) , (b)）也不是 Carter-Wegman 驗證多條消息的方法$$ 2 $$( paywall-free ) 給出偽造機率的二次項，或 ’ $ 2^{-n/2} $ security’，措辭過於圓滑，無法將攻擊者提供的離線計算與受應用程序頻寬限制的線上偽造區分開來$$ 3 $$，並且它掩蓋了中間塊大小與可能截斷的標籤大小。正如 Shoup 最初建議的那樣，它使用了 AES 或 DES 之類的排列$$ 4 $$——導致二次項出現：使用函式而不是排列，二次項消失。
通用雜湊實際上可以達到最佳界限 $ 2^{-n} $ 關於偽造機率 $ n $ 位標記。事實上，吉爾伯特、麥克威廉斯和斯隆在 1974 年的歷史上第一個鑑定人$$ 5 $$( paywall-free )，在通用散列的概念被卡特和韋格曼在 1979 年命名之前發布，通過使用與消息一樣長的密鑰實現了這種偽造約束。
卡特和韋格曼的創新$$ 2 $$以偽造機率的線性成本將密鑰壓縮到恆定大小，並通過一次性加密每個驗證器來隱藏通用雜湊的結構，從而將驗證器擴展到多個消息。1996年Shoup的貢獻$$ 4 $$是在每個消息的 nonce 上使用 DES 來生成 pad，並證明如果發送者發送不超過 $ \sqrt{2^n!/\ell,} $ 長度的消息 $ \ell $ 那麼之後偽造者的成功機率 $ f $ 嘗試受限於 $ 2 f \ell/2^n $ （定理 2）。
細節。
GHASH 是一個函式族 $ H_r\colon {0,1}^* \to \operatorname{GF}(2^{128}) $ 為了 $ r \in \operatorname{GF}(2^{128}) $ 在位串上定義 $ m $ 通過將其解釋為一個序列，適當地填充 $ (m_1, m_2, \ldots, m_\ell) $ 的元素 $ \operatorname{GF}(2^{128}) $ , 並給予$$ H_r(m) = m_1 r^\ell + m_2 r^{\ell - 1} + \dots + m_\ell r. $$ 換句話說，我們解釋一個消息 $ m $ 作為一次多項式 $ \ell $ 常數項為零，並在該點進行評估 $ r $ . （GHASH 是密碼學中的幾個多項式評估雜湊之一；Poly1305 是另一種流行的雜湊，在素數域上 $ \mathbb Z/(2^{130} - 5)\mathbb Z $ .)
GHASH 是一個通用雜湊族，或者更準確地說，GHASH 具有差異機率 $ \Pr[H_r(x) - H_r(y) = \delta] $ 被約束 $ \ell/2^{128} $ 對於任何 $ \delta $ 和任何消息 $ x $ 和 $ y $ 高達 $ \ell $ 塊。證明：解決方案 $ r $ 至 $ H_r(x) - H_r(y) = \delta $ 是多項式的根 $ x(r) - y(r) - \delta $ 在 $ r $ . 這個多項式最多有次數 $ \ell $ , 所以它至多有 $ \ell $ 根源於 $ 2^{128} $ 中的可能值 $ \operatorname{GF}(2^{128}) $ .
一次性驗證器 $ m \mapsto H_r(m) + s $ 對於獨立均勻隨機 $ r, s \in \operatorname{GF}(2^{128}) $ 關於最多的消息 $ \ell $ 塊的偽造機率為 $ \ell/2^{128} $ . 證明：對於任何 $ m \ne m’ $ , $ a $ ， 和 $ a’ $ , 對於獨立的均勻隨機 $ r, s $ ,
$$ \begin{align} \Pr&[H_r(m’) + s = a’ \mid H_r(m) + s = a] \ &= \Pr[H_r(m’) + a - H_r(m) = a’] \ &= \Pr[H_r(m’) - H_r(m) = a’ - a] \ &\leq \ell/2^{128}. \end{align} $$
一個試圖達到 $ f $ 在所有嘗試中，偽造單次偽造的成功機率再高不過了 $ f \ell/2^{128} $ . 請注意，這裡沒有二次項。只有差分機率的界限和獨立性 $ r $ 和 $ s $ ，計算到這個分析中——你可以使用任何其他具有有限差分機率的雜湊族來證明類似的偽造機率界。例如，一次性驗證器 $ m \mapsto m_1 r_1 + m_2 r_2 + \dots + m_\ell r_\ell + s $ 使用消息長度鍵 $ r = (r_1, r_2, \ldots, r_\ell) $ 會給出一個界限 $ f/2^{128} $ , 沒有因子 $ \ell $ .
為了驗證許多消息，卡特和韋格曼建議$$ 2 $$使用統一的隨機密鑰 $ r $ 具有獨立均勻隨機 $ s_1, s_2, \dots, s_q $ 驗證每個最多 $ q $ 消息 $ m_i $ 和 $ m_i \mapsto H_r(m_i) + s_i $ . 他們證明了偽造的機率仍然是 $ f \ell/2^{128} $ . 請注意，偽造機率中仍然沒有二次項 $ f \ell/2^{128} $ 卡特和韋格曼的方法，它甚至與數量無關 $ q $ 發送的消息。
當 Shoup 選擇時，二次項出現了$$ 4 $$生成 $ s_i $ 由排列 $ \operatorname{DES}_k(i) $ . 關於用置換代替函式的標準引理增加了 $ q’(q’ - 1)/2^{n - 1} $ 到偽造機率界，其中 $ q’ $ 是對排列的呼叫次數，在 AES-GCM 中是 $ 1 + (1 + \ell) (q + f) $ . 有更好的界限$$ 6 $$$$ 7 $$，但關鍵是使用 DES 或 AES 之類的排列有二次成本。
最近的方案，如 NaCl crypto_secretbox_xsalsa20poly1305 取消了排列和Carter-Wegman 方法，而是簡單地生成 $ r $ 和 $ s $ 正如 Lange 所建議的，每條消息都由 PRF 獨立$$ 8 $$. 但是讓我們回到 GHASH 和 GCM。
- 通用雜湊提供了什麼便利？
通用散列的評估成本非常低——比分組密碼、偽隨機函式，尤其是抗衝突散列便宜得多。 通過預計算評估多項式時可達到的並行性沒有固有限制 $ (r, r^2, \dots, r^t) $ 如果你能表演 $ t $ 向量單元中的同時乘法。GHASH 在軟體中尤其困難，因為它是根據二進製欄位定義的，具有一種奇怪的位排序$$ 9 $$，但還有其他對軟體更友好的通用雜湊，例如 Poly1305，它可以在軟體中每個字節一個週期內執行。
- 通訊增加多少 GHASH？
GCM/GMAC 添加一個 128 位標籤。因為偽造機率是 $ O(\ell/2^n) $ 而不是 $ O(1/2^n) $ , 你應該避免過多地截斷標籤$$ 10 $$. 例如，如果您接受最大 16 MB 的消息或 $ 2^{20} $ 塊，則單個 32 位標籤的偽造機率為 $ 2^{-12} $ 而不是 $ 2^{-32} $ 如您所願。請注意，截斷標記不會影響二次項 $ O(q^2!/2^b) $ 由於使用了一個 $ b $ -位排列而不是 $ b $ -bit 功能：塊大小和標籤大小成本分別縮放。
- 為什麼不應該使用資訊論綁定的 HMAC 而應該使用較小的 HMAC？
畝。
上面的界限是資訊論的。 HMAC 模型有一個相應的資訊論界限$$ m \mapsto f\bigl((k \oplus \mathrm{opad}) \mathbin| f((k \oplus \mathrm{ipad}) \mathbin| m)\bigr) $$具有均勻隨機函式 $ f $ ，或者對於 Merkle – Damgård 雜湊 $ f $ 具有均勻隨機壓縮函式，它涉及到碰撞機率 $ m \mapsto f((k \oplus \mathrm{ipad}) \mathbin| m) $ .
但是你需要選擇一個實際的 $ f $ 做一個實用的系統。 通用雜湊通過極其便宜的選擇為我們提供了強有力的保證；對於 HMAC，我們通常使用像 SHA-256 這樣的推測性抗碰撞函式，對於我們在這個應用程序中甚至不關心的推測安全性（抗碰撞性），計算這些函式的成本要高出幾個數量級。
但是讓我們假設您選擇了一個可比較的函式來使用一個 256 位密鑰，該密鑰提供一個 128 位標籤，可能是一個沒有抗碰撞性的函式：MD5。碰巧的是，HMAC-MD5 之後並沒有提供太多的安全性 $ 2^{64} $ 消息要麼$$ 11 $$. 哎呀。
（MD5 的抗碰撞性被破壞的事實在這裡無關緊要；相關的是 128 位雜湊大小。對 HMAC 的相同通用攻擊在以下情況下起作用 $ f $ 是一個隨機預言機，根據定義它是抗碰撞的。）
HMAC-MD5 優於AES -GMAC（它是帶有空密文的 AES-GCM）或 Poly1305-AES（另一個帶有 AES 的 Carter-Wegman-Shoup MAC）的優勢：HMAC-MD5 不需要nonce，而 AES-GMAC 和 Poly1305-AES 可以；HMAC-MD5 不僅可以用作 MAC，還可以用作長輸入短輸出 PRF，而 GMAC 和 Poly1305-AES 則不能。但是你也可以從一個通用散列和一個短輸入短輸出 PRF 中設計一個好的、快速、非連續的長輸入短輸出 PRF$$ 12 $$. 例如，AES-GCM-SIV 就是這樣做的（並且也修復了 GHASH 中的位順序）。
- 由於 GHASH 最多提供 $ 2^{64} $ TLS 1.3 中的防偽安全性，這是無法更改的標準，是否有任何其他套件可以提供資訊理論上的防偽安全性。
您可以使用 ChaCha20-Poly1305。這避免了使用分組密碼的偽造機率的二次成本，並且不會在軟體實現中出現速度和安全性之間的衝突。
CCM 密碼套件都具有與 GCM 相同的缺點 $ O(q^2!/2^b) $ 在使用置換而不是函式的偽造機率中 $ b $ 位，他們需要 $ \ell $ AES 呼叫，而不是每條消息 1 個 AES 呼叫，僅用於身份驗證。他們比 GCM 的優勢是 $ O(1/2^n) $ 代替 $ O(\ell/2^n) $ 在偽造機率中，一些硬體具有專用的 AES 電路，這些電路可能比軟體執行得更快，以評估 ChaCha20 或 Poly1305。