事後將 Nonce-misuse-resistance 方案應用於 AES-GCM 以進行深度防禦？
這是上一個關於從 AEAD 密碼中加密 IV/MAC 結果的問題的後續內容。
我有一個我正在開發的系統需要使用標準（NIST/FIPS）加密，至少對於它的主要安全層。這將完全按照指示使用 AES-256/GCM。我還將定期重新鍵入密鑰，重新鍵入時間間隔約為兩分鐘。
不過，這個系統中的隨機隨機數只有 64 位。（在內部，通過添加消息大小和其他位，它們將被填充到 GCM 的 96 位，但協議中僅使用 64 個隨機位。）每兩分鐘重新設置密鑰使得使用相同密鑰的 nonce 重用非常不可能，但是我仍然不介意添加一些緩解措施以增加額外的邊際和深度防禦。
這是一個最小狀態系統，因此有狀態的 nonce 重用阻力方案是有問題的。（無論如何，有狀態的隨機數生成是一種槍。）這也是一個基於數據包的系統而不是流協議，因此無法保證可靠的消息傳遞，使得有狀態的棘輪方案難以實現且笨重。它基於數據包的性質也意味著理論上重新鍵入可能會失敗多次，可能會延長密鑰的生命週期……這也是我想在這裡增加一些額外餘量的部分原因。
所以我正在研究是否有任何方法可以在事後應用 nonce-reuse/misuse resistance 緩解。（我知道 SIV 模式，但它們不是標準的，所以我不能使用它們。）
這是我的想法：
- 以無聊的標準方式使用 AES256/GCM 加密：Nonce + Plaintext -> Auth Tag, Ciphertext。
- 將 64 位隨機數與 64 位身份驗證標籤連接起來，並在 ECB 模式下使用 AES256 加密（它只有一個塊）。（這是兩個 ECB 加密中的第一個。）
- 使用此加密的 nonce+auth 標籤初始化另一個密碼。
- 再次加密加密的 nonce+auth 標籤，並在消息中包含這個最終的 AES(AES(Nonce+Auth Tag))。
- 使用我們在步驟 3 中初始化的另一個密碼加密 AES256/GCM 的密文輸出。
（解密基本上是 4、3、5、2、1。）
將 nonce 和 auth 標籤加密在一起（步驟 2）將它們混合在一起，並產生一個 128 位的組合標籤，該標籤同時依賴於 nonce 和消息內容。這使得僅通過觀察 nonce 欄位來檢測重複的 nonce 是不可能的。
但是正如其他人在我之前的文章中指出的那樣，重複的 nonce 仍然會導致相同的 GCM (CTR) 密鑰流。這意味著攻擊者可以對消息進行異或運算，並通過查找結果與已知明文匹配或具有低熵的情況來查找重複的隨機數。
對此的緩解措施在第 5 步中。依賴於 auth 標籤和 nonce 的密鑰用於再次加密密文，使得不可能只對消息進行 XOR 來查找重複的 nonce。
（請注意，具有重複隨機數和明文的消息將產生完全相同的加密最終消息，但這不是什麼大問題。它只表明發送了相同的消息。它不允許任何東西被解密。它也是極不可能。）
我的最後一個問題是關於這個二級密碼的強度要求，以減輕這種影響。出於性能原因，用於此緩解步驟的此密碼應該非常快，而且似乎不需要那麼強大。這裡唯一的目標是讓攻擊者儲存大量消息並將它們異或以查找隨機數衝突（使用相同的密鑰）是不切實際的。假設我們的二級密碼的強度為 $ 2^{64} $ 位。每個密鑰都是隨機的，明文是密文，所以我可以攻擊它的唯一方法是尋找衝突。這意味著做 $ 2^{128} $ 每個消息對的操作，因為對於我的攻擊中的每次迭代，我必須做 $ 2^{64} $ 對另一條消息進行相應的迭代以檢查攻擊是否成功。像 4 輪 AES-128 或 8 輪 Speck 這樣非常弱且非常快的東西可能就足夠了……？
所以搜尋碰撞的時間複雜度似乎是 $ 2^{2N} $ 其中 N 是二級密碼的相對強度，空間複雜度似乎是 $ M*2^{32} $ 其中 M 是消息的平均大小，並且 $ 2^{32} $ 由於 64 位隨機數和生日限制。為一個 $ 2^{64} $ 難度二級密碼和 1400 字節平均消息 $ 2^{128} $ 時間和大約 6TB 的空間。這當然忽略了定期重新鍵入。一旦重新鍵入，您必須重新開始。
回到認證話題：既然AES256/GCM在這個系統中提供了“真正的安全”，它可以是認證中考慮的事情。作為沒有“官方”安全形色的附加協議細節，可以忽略這種深度防禦。
我想我的問題是我的方案是否足夠強大，值得花費幾個 CPU 週期來應用。這真的會減少意外的隨機數重用嗎？如果我是攻擊者，我想不出一種方法來檢測此方案中的 nonce 重用（除了重複的純文字和 nonce 的情況），但是任何人都可以設計一個他們自己無法破解的加密方案，對嗎？
編輯：我們在部落格上寫了這個並且也有一個GitHub 執行緒。
編輯#2：
為了回應 Squeamish Ossifrage 的更標準和概念上更清晰但不幸的是他們在下面發布的太慢的構造，我想到了一種更簡單的方法來解釋我的並可能將兩者聯繫起來。
要加密消息，我會：
t, c = AES-GCM(i, k, m) a = AES-ECB(k, i | t) (one block) C = AES-ECB(a, c) (multiple blocks) T = AES-ECB(k, a) (one block) i = 64-bit nonce/IV k = 256-bit AES-256 session key m = plaintext t = 64 bits of AES-GCM authentication tag c = AES-GCM ciphertext (inner ciphertext) a = outer key for final ECB step C = final ciphertext T = final "combined tag"解密留給讀者作為練習。這很明顯。
這非常快（每個核心 1.3-1.4GiB/秒）。我還可以看到：
- AES-ECB 加密 (i | t) 產生一個加密的 128 位結果，即使i重複，每條消息都會有所不同。除非您可以破壞 AES，否則它也是不透明的。
- AES-ECB 使用依賴於原始消息的臨時密鑰加密 GCM 密文根本不會削弱 GCM，並且不適合對消息進行異或處理，因為 AES-ECB 不是異或 OTP。
- AES-ECB 加密 (i | t) 第二次隱藏內部臨時密鑰確實隱藏了這個密鑰，除非你能破解 AES。
也許這更清楚。除非我完全遺漏了某些東西，否則這確實可以防止 IV 重用，而且我看不出它如何以任何方式削弱標準 AES-GCM 加密……除非你能破壞 AES。如果你能破解 AES，你基本上可以攻擊整個世界經濟。玩得開心。
這不是標準的，但是對於頻繁重新加密的短消息，使用帶有 64 位隨機數和標籤的 AES256-GCM 是可以的。該系統將大約每分鐘或每兩分鐘重新鍵入一次。我認為 FIPS/NSA 只能查看GCM的使用方式，而將其視為“協議細節”而忽略。這裡的目標是通過完全消除 IV 使用的風險（在可能的無狀態系統中）來加強 FIPS 之外的這一點，同時仍然能夠連結到符合 FIPS 的庫並通過能夠說出主要安全性來通過集合我們的系統基於標準原語。
- AES-GCM 偽造機率為 $ qL/2^\tau $ 在哪裡 $ q $ 是消息的數量， $ L $ 是 128 位塊中的最大消息長度，並且 $ \tau $ 是標籤的長度。
在這裡，您已將其截斷為 64 位，而不是 128 位，因此如果您允許最長 16 兆字節的消息，則單次嘗試後的偽造機率已經存在 $ 1/2^{44} $ 當你可能希望它更接近 $ 1/2^{100} $ . 如果它可以節省大量的傳輸或儲存成本，那麼這對您的應用程序來說可能是可以接受的——但您仍然要為 128 位標籤付費，因此它實際上並沒有節省任何成本。
- 您所描述的方案承認選擇明文區分器具有以下優勢 $ q^2!/2^{64} $ 在哪裡 $ q $ 是具有相同隨機數的消息數。具體來說，如果 64 位截斷 $ t $ 的 AES-GCM 身份驗證標籤在兩條消息之間發生衝突，根據生日悖論，這發生的機率約為 $ q^2!/2^{64} $ ，然後是派生密鑰 $ a $ 也會發生碰撞，並且對手可以判斷兩個消息中的各個塊何時相同。
這比人們預期的確定性認證密碼的安全性要差得多。例如，AES-SIV 將優勢限制在大約 $ q^2!/2^{128} $ 反而。
無法為您的方案證明更好的界限，所以我不建議使用它！