了解分區預言機攻擊對流密碼的影響
昨天我遇到了一些討論分區預言機攻擊的對話，針對經過身份驗證的流密碼（如 ChaCha20 和 Salsa20）以及用於 MAC 的 poly1305。
據我了解（儘管論文有點密集），該漏洞利用需要：
- 互動式客戶端/伺服器，其中消息在從密碼派生的密鑰下加密。
- 加密是“非送出”。
- 伺服器響應指示解密是否成功。
雖然這個討論引起了我的一些擔憂：
- 這些多個關鍵的東西看起來很瘋狂，我總是理解像 ChaCha20-256 這樣的對稱密碼需要搜尋一個 $ 2^{256} $ 單個正確密鑰的位密鑰空間。我讀到您實際上可以使用線性方程計算大約 200,000 個用於解密的有效密鑰。這是真的嗎，如果是這樣我們不應該考慮位強度 $ 2^{256} $ 即使ECDH同意密鑰我們應該？
- 在一個範例本地應用程序中，使用 libsodium 的秘密盒 (Xsalsa20+Poly1305) 和 Argon2 來派生密碼並加密某些文件，如果該文件儲存在沒有其他 API 或資訊的系統上，這是否容易受到這種攻擊? （例如，通過呼叫 libsodium 並觀察 MAC 原語是否成功驗證）或者像這樣的“離線/儲存”文件安全嗎？即像填充預言攻擊一樣，這整個事情是否需要伺服器知道正確的密鑰，因此可以洩露資訊？
- 這只是基於密碼的密鑰的問題嗎？這種攻擊是否也意味著可以減少 ECDHE 同意密鑰的密鑰空間 $ 2^{256}/200k $ 何時與 ChaCha/Salsa 一起使用？
簡而言之，我們可以將其稱為對非送出 AEAD 方案（如 AES-GCM 和 ChaCha20-Poly1305）的加速密碼搜尋，具有低 Oracle 呼叫。如果您的密碼具有良好的強度，那麼您是安全的。
送出加密方案是一種在計算上難以找到一對密鑰和在這兩個密鑰下解密的密文的方案。
由以下游戲定義的目標多密鑰抗碰撞 (TMKCR) 安全性，其中對於給定的目標密鑰集 $ \mathbb{K} \in \mathcal{K} $ 對於隨機對手 $ \mathcal{A} $ 必須產生一個隨機數 $ N^* $ , 關聯數據 $ AD^* $ , 和一個密文 $ C^* $ 這樣 $ \text{AuthDec}_K(N^,AD^,C^*) \neq \perp $ 對所有人 $ K \in \mathcal{K} $ . 優勢定義為
$$ \textbf{Adv}{\text{AEAD},\mathbb{K}}^{tmk-cr} = \Pr \left[ \textsf{TMKCR}{\text{AEAD},\mathbb{K}}^\mathcal{A} \right] \implies \textsf{true} $$
可以看出，如果攻擊者以某種方式對密鑰空間進行分區，那麼他們可以減少 oracle 查詢，這意味著攻擊可以檢測到更少的線上互動。
例如，考慮沒有送出的 AES-GCM，並選擇兩個密鑰和一個任意密文，那麼攻擊者將尋找創建一個有效的標籤，以便在解密期間標籤是有效的$$ 1 $$（注意；AES-GCM 不需要解密來驗證身份驗證標籤，但是，將解密和標籤驗證分開需要傳遞數據，通常出於性能原因，這不是首選）
目的是找回密碼 $ pw $ . 考慮您要測試兩個密碼的成員資格 $ S_1^* = {pw_1,pw_2} $ . 創建兩個密鑰 $ K_1 = PBKDF(salt,pw_1) $ 和 $ K_2 = PBKDF(salt,pw_2) $ （可以通過嗅探找到鹽！），現在使用 Dodis 等人的方法 $$ 1 $$, 構造密文 $ C’ $ 帶有標籤，使其在密鑰下正確解密 $ K_1 $ 和 $ K_2 $ . 現在發送拆分值 $ \hat{V} $ 到伺服器。如果伺服器指示解密成功，則 $ pw \in S_1^* $ . 通過迭代此過程，攻擊者可以在 $ |\mathcal{D}|/2 +1 $ 查詢，而預設的蠻力需要 $ |\mathcal{D}| $ 查詢。此攻擊的度數為 2，如果 $ k $ 度是可能的，那麼這將大大減少查詢量。
使用 SageMath 程式碼，他們能夠找到 $ k=2^{16} $ 非常快速地碰撞密文。他們模擬了他們的自適應分區預言機攻擊，該攻擊構造了拆分大小的密文 $ k $ 對不同的密鑰集進行迭代，直到 oracle 返回有效。此時，攻擊者執行二分查找 $ \log k $ 查詢以找到秘密。
上圖左邊是他們的成功率，右邊是生成時間 $ k $ 路碰撞。
事實證明，Poly1305 上的多鍵碰撞攻擊比 GCM 更難，因為附加了
0x01. 與達到 18 度的 GCM 相比，它們最多只能生成 10 個。這仍然使分區預言機攻擊的速度提高了十倍像 AES-GCM-SIV 這樣的防誤用方案也適用於這種攻擊。
攻擊協議
- 影襪
- 不透明
對策
- 限制密文的長度
- 共享秘密的熵要求
- 使用送出 AEAD 方案，沒有任何標準，但是！
- 使用單一密鑰 Encrypt-then-HMAC（萬歲 HMAC）或 KMAC。
問題
- 這些多個關鍵的東西看起來很瘋狂，我總是理解像 ChaCha20-256 這樣的對稱密碼需要搜尋一個 $ 2^{256} $ 單個正確密鑰的位密鑰空間。我讀到您實際上可以使用線性方程計算大約 200,000 個用於解密的有效密鑰。這是真的嗎，如果是這樣我們不應該考慮位強度 $ 2^{256} $ 即使ECDH同意密鑰我們應該？
首先，一個小的修正。如果密鑰是均勻生成的，那麼平均而言，它不是 $ 2^{256} $ , 少一點。讓 $ k $ 成為攻擊者搜尋的目標密鑰，以測試密鑰的正確性。由於每個鍵都有 $ \Pr[k_i = k] = 1/2^{256} $ 正確，那麼預期的猜測次數是；
$$ \sum_{i=1}^{2^{256}} i \cdot \Pr[k_i = k] = \sum_{i=1}^{2^{256}} i \cdot \frac{1}{2^{256}} = \frac{2^{256} (2^{256} - 1)/2}{2^{256}} = 2^{255} - {\textstyle\frac12}. $$
當然，在搜尋過程中，會有很多誤報keys要被剔除，這並沒有增加多少搜尋時間。
正如我們上面談到的，他們搜尋可能的密碼空間 $ \mathcal{D} $ 在哪裡 $ |\mathcal{D}|= 800000 $ . 該方案的承諾使攻擊者能夠大幅減少預言機呼叫。
如果您使用強密碼或使用 ECDHKE 和 KDF 呼叫生成密碼，那麼您將是安全的。關鍵是人類傾向於使用錯誤的密碼，包括密碼學家。
- 在一個範例本地應用程序中，使用 libsodium 的秘密盒 (Xsalsa20+Poly1305) 和 Argon2 來派生密碼並加密某些文件，如果該文件儲存在沒有其他 API 或資訊的系統上，這是否容易受到這種攻擊? （例如，通過呼叫 libsodium 並觀察 MAC 原語是否成功驗證）或者像這樣的“離線/儲存”文件安全嗎？即像填充預言攻擊一樣，這整個事情是否需要伺服器知道正確的密鑰，因此可以洩露資訊？
這種攻擊需要一個像填充預言攻擊一樣返回值的預言。如果沒有返回，那麼即使是正常的線上密碼猜測攻擊也沒有測試 $ k=1 $ . 他們查看了使用 OPAQUE 和 AEAD 方案的庫，發現其中一些不適用。請參閱發出錯誤列。對 Shadowsocks 的攻擊很有趣，因為攻擊者有一個側通道要測試。
- 這只是基於密碼的密鑰的問題嗎？這種攻擊是否也意味著可以減少 ECDHE 同意密鑰的密鑰空間 $ 2^{256}/200k $ ，當注定要與 ChaCha/Salsa 一起使用時？
如果密鑰是統一隨機生成的，那麼攻擊將不起作用。這是一個密碼搜尋。
