超越 AES-GCM-SIV 中的生日綁定安全性
AES-GCM-SIV與原始 GCM 一樣採用 96 位隨機數。RFC 聲明*“建議將此方案與隨機選擇的隨機數一起使用”*。它使用基於 AES 的 PRF使用隨機 nonce生成每個消息的加密和 MAC 子密鑰，並 聲稱這種構造提供了超出生日限制的安全性：
本文件中定義的 AEAD 為每個 nonce 計算新的 AES 密鑰。這允許在給定密鑰下加密大量明文。如果沒有這一步，AES-GCM-SIV 加密將像其他標準模式（例如，AES-GCM、AES-CCM
$$ RFC3610 $$, 和 AES-SIV$$ RFC5297 $$）。這意味著當整體加密了 2^64 個塊時，試圖破壞方案機密性的顯著對手具有 1/2 的優勢。因此，為了將對手的優勢限制在 2^-32，總共最多可以加密 2^48 個塊。相比之下，通過從每個 nonce 派生新密鑰，可以使用 AES-GCM-SIV 加密更多數量的消息和塊。
但是，使用 96 位隨機數時，您會超過 $ 2^{-32} $ 僅在之後發生碰撞的機會 $ 2^{32} $ 消息，這就是NIST SP 800-38D使用隨機隨機數限制 AES-GCM 的原因 $ 2^{32} $ 消息。如果一個隨機數在 AES-GCM-SIV 中發生衝突，那麼 PRF 構造將派生相同的加密和 MAC 子密鑰，因此我們仍然存在衝突。AES-GCM-SIV 是抗誤用認證加密 (MRAE)，但與所有 MRAE 方案一樣，它在隨機數重用情況下仍然會洩漏資訊（明文的平等），並且在這種情況下不是 IND-CPA 安全的。
我最初認為超出生日限制的安全性僅指可加密的塊總數的限制，而不是消息。但是，上面的引用明確表示 AES-GCM-SIV 可以加密*“大量消息”* ，而安全考慮中的後面引用聲稱您可以加密
2^61 messages, where each plaintext is at most 16 KiB.up to 256 uses of the same nonce and key但是，生成後 $ 2^{61} $ 96 位隨機 nonce，我們預計大約有 3,355,443 個 nonce 衝突。我認為（從參考資料）聲稱沒有特定的nonce 值會重複超過 256 次。然而，對於那些約 340 萬條具有衝突隨機數的消息，仍然會有一些潛在的機密性損失。我不確定如何解釋這些界限。如果碰撞隨機數的總數很大，將任何特定隨機數限制為最多 256 次的相關性是什麼？我是否正確假設如果您真的想要 IND-CPA 安全性（具有防誤用性），那麼 AES-GCM-SIV 被限制為最大值 $ 2^{32} $ 消息？
AES-GCM-SIV 是抗誤用認證加密 (MRAE)，但與所有 MRAE 方案一樣，它在隨機數重用情況下仍然會洩漏資訊（明文的平等），並且在這種情況下不是 IND-CPA 安全的。
這是它的癥結所在。 在 nonce 重用的情況下，AES-GCM-SIV 無法提供 IND-CPA。 來自 RFC 8452（第 12 頁）：
We stress that nonce misuse-resistant schemes guarantee that if a nonce repeats, then the only security loss is that identical plaintexts will produce identical ciphertexts.我不確定如何解釋這些界限。
這些並不限制對手的 IND-CPA 優勢。它們是mrAE遊戲中對手優勢的界限。 mrAE 遊戲在原始 GCM-SIV 論文的附錄 A 中定義。對手有兩個神諭：
- 加密（隨機數、廣告、消息）
- 解密（隨機數、廣告、密文）
對手的目標是區分：
- oracles 在統一隨機密鑰下計算 AES-GCM-SIV，來自
- 神諭回歸
- 加密查詢中正確長度的統一隨機密文，以及
- 所有解密查詢無條件失敗。
我們假設攻擊者永遠不會重複加密查詢，並且永遠不會將加密查詢的答案作為解密查詢送出。RFC 中報告的界限對對手提出了額外的假設，例如，要求每個送出給加密預言機的 nonce 被獨立地隨機選擇。（在實踐中，這個假設反映了一個系統，其中對手並沒有真正選擇隨機數；合法使用者選擇了它。）
你引用的界限大致告訴你，對手除了辨識重複的明文之外還能做更多的事情的機率——例如，他們不能偽造消息，除了平等之外，他們無法了解任何關於消息的資訊。 這些界限是“超出生日界限”的，因為安全概念以揭示消息相等性不是問題為前提，並且它們通過為每條消息派生一個新密鑰來工作（順便說一下，這在軟體 AES 中非常昂貴）所以你’沒有使用每個鍵的固定 128 位排列。相反，即使假設消息不重複，對手對抗AES-SIV ( RFC 5297 ) 的優勢也受到 128 位生日界限的限制。
如果碰撞隨機數的總數很大，將任何特定隨機數限制為最多 256 次的相關性是什麼？
如果一個隨機數在許多消息中重複使用，那麼對手優勢的界限基本上不會比 AES-SIV 更好，它受到 128 位生日界限的限制——對於 $ q $ 具有相同隨機數的查詢，優勢界具有 $ q^2!/2^{128} $ 術語（實際上 $ L q^2!/2^{128} $ 對於 AES-GCM-SIV，其中 $ L $ 是 16 字節塊中的最大消息長度）。在大量重用之後，您可能會在 POLYVAL 中遇到標籤衝突（位反轉的 GHASH），這將導致重複的 AES-CTR 密鑰流和各種不好的事情發生。
但是，如果任何特定 nonce 的重用次數受到限制，那麼對手因標籤衝突的可能性而產生的優勢就足夠小了，這無關緊要。
同樣，這假設消息不會重複，或者您不關心洩漏消息相等性。
我是否正確假設如果您真的想要 IND-CPA 安全性（具有防誤用性），那麼 AES-GCM-SIV 被限制為最大值 $ 2^{32} $ 消息？
是的。
假設對手被給予預言機加密（廣告，消息）和解密（廣告，密文）隨機密碼，並允許重複查詢。這是一個將 AES-GCM-SIV 預言機（在內部隨機選擇隨機數，在加密查詢中統一隨機選擇）與統一隨機預言機的對手：只需一遍又一遍地向加密預言機送出相同的（廣告，消息）對並檢查重複的密文——AES-GCM-SIV 內部的隨機數衝突很可能在均勻隨機預言機中的密文沖突之前很久就發生，因此這個對手獲得了優勢 $ {\approx}q^2!/2^{96} $ 後 $ q $ 查詢，或 $ {\approx}2^{-32} $ 後 $ 2^{32} $ 查詢。
如果您嘗試在傳統的 IND-CPA 優勢而不是 mrAE 優勢上設置界限，您將遇到您發現的 nonce 衝突問題。 IND-CPA 無法繞過生日界限：對於相同的消息（和 AD），nonce 衝突意味著加密函式的所有輸入都是相同的，因此密文必須相同，從而顯示重複的消息。如果這是一個問題，當然生日限制仍然適用；AES-GCM-SIV 沒有繞過它的魔法。
有一種方法可以繞過 128 位生日，以提高安全性：擁有更大的生日空間！ Daence ( implementations ) 使用 24 字節標籤而不是 16 字節標籤，因此它可以：
- 提供更簡單的介面（沒有單獨的 nonce 參數），
- 讓您使用公共或秘密隨機數——確定性或隨機性，根據你的需要任意大小！——只需將它們放入相關的數據或消息中，以及
- 為更大量的消息和大量數據設置更嚴格的優勢界限。
例如，您可以使用緊湊的 16 位序列號，如果您只發送 $ 2^{16} $ 每個密鑰的消息，或長期非同步應用程序中的 128 位隨機 UUID，只需將其放入關聯的數據或消息中即可。當然，如果你的隨機數發生衝突，仍然沒有魔法可以防止消息相等性洩漏。但是，您可以通過為您的應用程序使用足夠大的統一隨機隨機數，或在沒有危險的線上互動式協議中使用順序隨機數（RFC 8452 明確建議不要使用 AES-GCM-SIV！）來使隨機數衝突的機率可以忽略不計狀態回滾，或兩者的組合。
獎勵：在原語（Poly1305 和 Salsa20 或 ChaCha）之上的程式碼佔用量要小得多，並且不會因為每條消息派生新的 AES 密鑰而對 AES-GCM-SIV 等軟體實現造成嚴重懲罰。
Daence、AES-SIV 和 AES-GCM-SIV 優勢界限的比較，對於許多消息大小，在確定性（“誤用”）、隨機和順序設置（原始碼）中。
（披露：我設計了丹斯。）