GCM（或 GHASH）是否僅提供針對偽造的 64 位安全性？
在最近的評論中，有人對我的回答表示懷疑，聲稱 GCM 需要 $ 2^{128} $ 成功的偽造。懷疑是需要取平方根，這意味著安全性將是 $ 2^{64} $ .
所以當然我立即檢查了相關的安全定理（推論 4）：
$$ \mathbf{Adv}^{\text{auth}}_{\operatorname{GCM}[\operatorname{Perm}(n),\tau]}(\mathcal A)\leq \frac{0.5(\sigma+q+q’+1)^2}{2^n}+\frac{q’(\ell_A+1)}{2^\tau} $$
和 $ \sigma $ 是以塊為單位的總明文大小， $ q $ 是加密查詢的總數， $ q’ $ 是解密查詢的總數， $ n $ 是基礎排列的位大小， $ \ell_A $ 是塊中的最大認證輸入長度，並且 $ \tau $ 是以位為單位的標籤大小。
現在我們可以清楚地看到執行 $ 2^{n/2}=2^{64} $ 查詢產生了足夠強大的休息優勢。
現在我的問題是：
當談到“n 位安全”或“需求”時 $ 2^n $ 中斷操作”，我們通常談論“線上”安全性嗎，即可以完成對預言機的查詢和成本 $ 1 $ 還是沒有可用的預言機的“離線”安全性，或者我們是否需要根據情況做出這個決定？
TL;DR：GCM 是否提供 64 位或 128 位安全性？
片語“128 位安全性”有點花言巧語，以涵蓋線上/離線區別——明確公式的目的是根據線上和離線成本的限制來量化偽造機率。 線上成本取決於您的應用程序的可擴展性；離線成本僅取決於對手願意為破解密碼術支付多少費用。
首先，我們可以畫出漸近增長曲線：
- 由於 PRF/PRP 轉換引理**，偽造機率界限在線上查詢的數量中呈*****二次增長，包括驗證合法消息和驗證嘗試的偽造，並且在塊*的大小上呈指數下降。
- 由於 GHASH 的一次性偽造機率，偽造機率界隨著線上查詢中偽造的塊數量***線性***增長，並且在標籤大小上呈指數下降。
- 偽造的可能性也會隨著對手離線工作以破壞 AES 所能承受的任何優勢而增加。 請注意，對手可以離線做的唯一工作是破壞 AES——AES-GCM 中沒有其他任何東西承認離線工作的優勢。如果您想要“128 位安全級別”，請確保使用 AES-256，而不是 AES-128。
作為為學術會議撰寫論文的密碼學家，您可能會停在這裡，這就是 McGrew 和 Viega 在發表 GCM 時所做的$$ 1 $$，顯然在岩田、大橋和峰松重新評估的隨機數散列分析中存在錯誤$$ 2 $$. 旁注：如果必須使用 AES-GCM，請使用通過計數選擇的 96 位隨機數。 （你選擇了關於通過計數選擇 96 位隨機數的定理；粗心的路人可能會錯誤地踩到其他隨機數大小或隨機選擇的隨機數的耙子，這就是岩田-大橋-峰松論文的大部分內容。）
作為在標準中提供建議的標準化者，您希望給出使用限制的具體界限。例如，NIST SP800-38D$$ 3 $$（存檔以防美國聯邦政府再次自焚以抗議其總司令）僅嚴格限制使用隨機選擇的隨機數或長度不是 96 位的消息的數量——具體而言，在 §8.3 中，它禁止處理超過 $ 2^{32} $ 消息。 旁注：我是否提到您應該使用通過計數選擇的 96 位隨機數？
奇怪的是，這是NIST SP800-38D 規定的*唯一限制。*提到的唯一其他限制是“合理限制” $ 2^{64} $ 塊已通過身份驗證，除了參考第 8.3 節之外，沒有提及該限制的原因。
作為應用程序開發人員或協議設計人員，您需要為願意處理的數據量選擇實際數字，這將讓您計算特定的界限。所以讓我們這樣做。
$$ \begin{equation} \begin{array}{llll} \text{max bytes ($16\cdot \ell_A$)} & \text{messages ($q$)} & \text{forgeries ($q’$)} & \text{bound} & \text{bound*} \ \hline \text{one block: $16$} & 1 & 1 & 2^{-124} & 2^{-127} \ \hline \text{IP packet: $2^{11}$} & 2^{32} & 1 & 2^{-50} & 2^{-120} \ & 2^{32} & 2^{32} & 2^{-48} & 2^{-88} \ & 2^{32} & 2^{40} & 2^{-34} & 2^{-80} \ & 2^{32} & 2^{50} & 2^{-14} & 2^{-70} \ & 2^{32} & 2^{60} & 33(?) & 2^{-14} \ \hline \text{IP packet: $2^{11}$} & 2^{48} & 1 & 2^{-18} & 2^{-120} \ & 2^{48} & 2^{48} & 2^{-16} & 2^{-72} \ & 2^{48} & 2^{56} & 1/4 & 2^{-64} \ & 2^{48} & 2^{60} & 33(?) & 2^{-14} \ \hline \text{megabyte: $2^{20}$} & 2^{32} & 1 & 2^{-32} & 2^{-111} \ & 2^{32} & 2^{32} & 2^{-30} & 2^{-79} \ & 2^{32} & 2^{40} & 2^{-16} & 2^{-72} \ & 2^{32} & 2^{50} & 9(?) & 2^{-50} \ & 2^{32} & 2^{60} & 2^{24}(?) & 2^{12102521}(?) \end{array} \end{equation} $$
我們如何解釋這一點？
- 單個塊的單個消息和單個偽造嘗試的最簡單情況的偽造機率接近 $ 2^{-128} $ 正如我們所希望的那樣。
- 一次偽造嘗試的行顯示了偽造者單次嘗試的成功機率。但請記住，它是二次而非線性縮放的，因為我們使用隨機排列 AES 來選擇散列密鑰，而不是隨機函式。
- 您應該假設攻擊者至少可以發送與合法使用者一樣多的消息，因此我沒有顯示介於 1 和合法消息數量之間的任何偽造嘗試次數。事實上，你真的應該假設對手可以發送比合法使用者*更多的消息；*對手將使您的可用頻寬飽和。
- 對於在正常使用中驗證數十億個 IP 數據包的應用程序，您引用的 Iwata-Ohashi-Minematsu 界限表明，對手必須嘗試數万億次偽造，才能成功找到一個偽造的機率高於一個-in-a-百萬 （ $ 2^{-20} $ )，並且必須以超過千分之一的價格送出千萬億美元。
- 界限在某一點之後崩潰：機率大於 1 的界限是無用的。幸運的是，替代方程式。(22) 的$$ 2 $$來自 Dan Bernstein 的更嚴格的 PRF/PRP 切換引理$$ 4 $$，顯示在 ‘bound*’ 列中，提供更好的可信度並適用於大量消息：$$ \biggl[\frac{q’ (\ell_A + 1)}{2^\tau}\biggr] \cdot \delta_n(\sigma + q + q’ + 1), $$在哪裡$$ \delta_n(a) = \biggl(1 - \frac{a - 1}{2^n}\biggr)^{-a/2}. $$
- 請記住，這僅適用於您使用通過 AES-GCM 計數選擇的 96 位隨機數。 如果您隨機選擇 nonce，或使用 96 位以外的 nonce *，*則上述數字會變得更糟，因為存在 nonce 衝突的機會。
這不是您可以使用身份驗證器做的最好的事情 $ H_r(m) + s $ 建立在一個通用雜湊家族之上 $ H $ 像 GHASH 或 Poly1305。GCM 使用 Carter-Wegman-Shoup 結構$$ 5 $$$$ 6 $$, 重用 $ r $ 並導出 $ s = \operatorname{AES}_k(n) $ 從一個隨機數 $ n $ . 您可以跳過 Carter-Wegman 結構並推導出 $ (r, s) = F_k(n) $ 對於一些偽隨機函式族 $ F_k $ 正如 Tanja Lange 所建議的，每條消息都像 XSalsa20$$ 7 $$. 這就是 NaCl 所做的，它提供了通常更好的界限 $ 8 q’ \ell_A/2^{106} $ 關於所有未破解 XSalsa20 的攻擊者的偽造機率——請注意，這與消息數量無關 $ q $ 由您的應用程序進行身份驗證。
此外，XSalsa20（和 XChaCha）可以處理隨機選擇的隨機數，並且在軟體中速度更快，並且不會引發定時側通道攻擊。因此，當我們這樣做時，請考慮使用
crypto_secretbox_xsalsa20poly1305而不是 AES-GCM。 （填寫上面的相應表格作為練習留給讀者。）