什麼是多目標攻擊？
究竟什麼是多目標攻擊？攻擊如何在不同的密碼方案（分組密碼、散列函式、橢圓曲線）上發揮作用？如何避免？
多目標攻擊是一次對密碼系統的多個使用者的攻擊。
攻擊者可能會滿足於破壞一個使用者——例如，如果一個網路中有一千名人權活動家受到威權國家的攻擊，那麼闖入一名活動家的 Signal 聊天可能就足以破壞整個網路。
此外，國家情報機構的目標可能比一個激進主義網路多得多——可能有一個環保激進主義網路、一個反腐敗激進主義網路、外國情報網路、不同的政府部門等等——這符合國家利益闖入其中任何一個。
當然，實際上可能只有一個人類使用者擁有許多密鑰——例如，一千個（比方說）用不同的 AES 密鑰加密的 HTML 文件，這些密鑰源自具有 HKDF-SHA256 的主密鑰，因此攻擊者擁有相同的密文
<!DOCTYPE html>\n許多不同鍵下的明文。更一般地說，多目標攻擊是對密碼系統的許多實例的攻擊：在相同密碼下具有已知明文/密文對的許多密鑰，具有相同離散對數庫的許多組元素，相同簽名方案的許多公鑰，等等多目標攻擊者可能會利用許多不同的批次優勢——您詢問了分組密碼，但值得注意的是幾個不同的設置，因為它們的質量差異會導致大量的安全性差異：
對於雜湊函式 $ H $ , 對手可能有雜湊 $ H(k_1), $ $ H(k_2), $ $ \dotsc, $ $ H(k_t) $ 為了 $ t $ 不同的未知目標鍵 $ k_1, k_2, \dotsc, k_t $ . 目標是恢復任何一個 $ k_i $ . 範例 $ H $ :
- AES 在 CTR 模式下對已知文件頭： $ k \mapsto \operatorname{AES}_k(0). $
- TLS 記錄上 HMAC-SHA256 下的消息驗證碼： $ k \mapsto \operatorname{HMAC-SHA256}_k(\text{‘250 OK’}). $
- 衍生加密貨幣地址的助記詞： $ \mathit{seedphrase} \mapsto \operatorname{X25519}(\operatorname{HKDF-SHA256}(\mathit{seedphrase}), \underline 9). $最好的通用多目標原像搜尋算法——Oechslin 彩虹表和 Rivest 特徵點的並行版本——具有與 $ 2^\lambda!/t $ 的評價 $ H $ 在哪裡 $ \lambda $ 或多或少的大小 $ k_i $ .
即：通用原像搜尋打破第一個的成本 $ t $ 目標是 $ 1/t $ 破壞一個特定目標的通用原像搜尋的成本。 有一千名激進分子作為目標？如果您批量攻擊它們，那麼破壞其中一個的成本將比您嘗試單獨攻擊它們少一千倍。它仍然會花費 $ 2^\lambda $ 找到所有目標鍵，但您通常不需要等待那麼長時間。
這些算法是如何工作的？
您可能會將多目標“加速”視為填充雜湊表，然後替換候選鍵的
ht單目標測試，該候選鍵也可以在“O(1)”時間內執行，但測試H(k) == h``H(k) in ht$ t $ 鍵。然而，這種簡化的算法實際上並沒有減少對手的面積*時間成本——這通常是成本的一個很好的代理，例如，日元來為機器供電足夠長的時間來找到密鑰——因為對於非常大量的密鑰，它由於記憶體延遲而花費大量時間順序等待通信，而這些拇指本來可以用於並行執行隨機遊走。反而：
- 彩虹桌。 我們在輸入空間上做一個偽隨機遊走併計算一個鏈$$ \sigma_0 \xrightarrow{H} h_0 \xrightarrow{R_1} \sigma_1 \xrightarrow{H} h_1 \xrightarrow{R_2} \cdots \xrightarrow{H} h_\ell, $$使用一系列歸約函式在輸入和雜湊之間交替 $ R_i $ 將散列映射回某個其他輸入，例如生成 128 位候選密鑰或候選 BIP39 密碼。我們儲存起點 $ \sigma_0 $ 和終點 $ h_\ell $ .
實際上，我們不會只這樣做一次。我們對大量並行執行此操作 $ p $ 隨機選擇的起點。我們還計算鏈中的終點，從 $ H(k_i) $ 好像它是 $ 1, 2, \dotsc, \ell $ 從最後的迭代：
$$ \begin{align*} \sigma_{1,0} \xrightarrow{H} h_{1,0} \xrightarrow{R_1} \sigma_{1,1} \xrightarrow{H} h_{1,1} \xrightarrow{R_2} \cdots &\xrightarrow{H} h_{1,\ell}, \ \sigma_{2,0} \xrightarrow{H} h_{2,0} \xrightarrow{R_1} \sigma_{2,1} \xrightarrow{H} h_{2,1} \xrightarrow{R_2} \cdots &\xrightarrow{H} h_{2,\ell}, \ \vdots \ \sigma_{p,0} \xrightarrow{H} h_{p,0} \xrightarrow{R_1} \sigma_{p,1} \xrightarrow{H} h_{p,1} \xrightarrow{R_2} \cdots &\xrightarrow{H} h_{p,\ell}; \ H(k_1) \xrightarrow{R_1} R_1(H(k_1)) \xrightarrow{H} \cdots &\xrightarrow{H} h’{1,1}, \ H(k_1) \xrightarrow{R_2} R_2(H(k_1)) \xrightarrow{H} \cdots &\xrightarrow{H} h’{1,2}, \ \vdots \ H(k_1) \xrightarrow{R_\ell} R_\ell(H(k_t)) &\xrightarrow{H} h’{1,\ell}; \ \vdots \ H(k_t) \xrightarrow{R_1} R_1(H(k_t)) \xrightarrow{H} \cdots &\xrightarrow{H} h’{t,1}, \ H(k_t) \xrightarrow{R_2} R_2(H(k_t)) \xrightarrow{H} \cdots &\xrightarrow{H} h’{t,2}, \ \vdots \ H(k_t) \xrightarrow{R\ell} R_\ell(H(k_t)) &\xrightarrow{H} h’_{t,\ell}. \end{align*} $$
然後我們對所有的結束點進行排序—— $ h_{j,\ell} $ 和 $ h’{i,r} $ ——尋找它們之間的碰撞。如果我們發現碰撞 $ h{j,\ell} = h’{i,r} $ , 然後我們可以重新開始 $ h{j,0} $ 並向前計算 $ \ell - r $ 尋找候選輸入的步驟 $ \sigma_{j,\nu} $ 如果 $ H(\sigma_{j,\nu}) = H(k_i) $ . （當然， $ H(\sigma_{j,\nu}) $ 結果可能不是 $ H(k_i) $ 如果兩個隨機遊走碰巧暫時發生碰撞，但誤報應該是相當罕見的。）
批處理優勢的出現部分是因為在排序步驟中，我們有效地同時測試了來自 $ p $ 平行鏈反對 $ t $ 目標雜湊（有一些誤報率），成本約為 $ (p + \ell t)^{1.5} $ 排序一個 $ (p + \ell t) $ -元素數組而不是成本 $ \ell\cdot p\cdot t $ 測試所有 $ \ell\cdot p $ 直接對所有人進行猜測 $ t $ 散列（誤報率為零）。什麼時候 $ p \geq t^2 $ ，成本的淨減少是一個因素 $ t $ .
- 顯著點。 我們在關鍵空間中選擇易於辨識的小點子空間，例如前 23 位為 的點
10100011110110001010，稱它們為區分點。再次，我們將並行執行許多獨立的偽隨機遊走，但不是在恰好之後停止 $ \ell $ 迭代，當我們找到一個顯著點時，我們將停止。上 $ p $ 並行機器，我們選擇起點 $ h_j $ 從密鑰空間中均勻隨機地迭代計算 $ H(h_j), $ $ H(H(h_j)), $ $ \dotsc, $ $ H^\nu(h_j) $ , 直到 $ H^\nu(h_j) $ 是一個顯著點，在這種情況下我們儲存 $ h_j $ 和 $ H^\nu(h_j) $ ， 或者 $ \nu $ 超出限制 $ \ell $ , 在這種情況下，我們把它扔掉並從一個不同的地方重新開始 $ h_j $ :
$$ h_j \xrightarrow{H} H(h_j) \xrightarrow{H} H^2(h_j) \xrightarrow{H} \cdots \xrightarrow{H} H^\nu(h_j). $$
我們還迭代計算 $ H(H(k_i)) $ , $ H(H(H(k_i))) $ 等，對於每個 $ i $ , 直到我們找到一個顯著點 $ H^\mu(k_i) $ . 然後我們排序 $ H^\mu(k_i) $ 和 $ h_{j,\nu} $ , 如果發生碰撞 $ H^\mu(k_i) = H^\nu(h_j) $ , 我們從頭開始 $ h_j $ 並迭代 $ H $ 直到我們找到候選人 $ k_i $ :$$ h_j \xrightarrow{H} \cdots \xrightarrow{H} H^{\nu-\mu}(h_j) \stackrel?= k_i \xrightarrow{H} H(k_i) \xrightarrow{H} \dotsc \xrightarrow{H} H^\nu(h_j) = H^\mu(k_i). $$ 當然，這也可能是因為碰撞 $ H $ 其他地方導致兩條鏈從 $ h_j $ 和 $ H(k_i) $ 虛假合併，所以有一些誤報率。
同樣，批處理優勢的出現部分是因為在排序步驟中，我們有效地同時測試了 $ p $ 平行鏈反對 $ t $ 以成本為目標雜湊 $ (p + t)^{1.5} $ 而不是 $ \ell\cdot p\cdot t $ ，由於碰撞引起的一些誤報率 $ H $ .
（使用歸約函式擴展特徵點以使該技術適用於例如密碼空間作為練習留給讀者。）有關預期成本和成功機率的詳細分析，請參閱Oechslin 的論文和Wiener 的論文（免費付費）。（據我所知，傑出點技術首先出現在Quisquater 和 Descailles 在 CRYPTO 1987 的摘要中以及在 EUROCRYPT 1989的後續論文中，但它通常歸功於 Rivest。）
作為使用者或密碼系統設計者，您可以使用哪些對策？ 標準的兩個選項是：
- 製作 $ \lambda $ 如此之大，以至於一個因素 $ t $ 沒關係。 不要將 AES-128 用於 128 位安全級別 - 使用 AES-256。 （更好的是，使用 ChaCha 這樣您就可以在很大程度上忘記旁道攻擊。）一般來說，始終確保密鑰材料的最窄管道是 256 位寬。
- 分隔輸入空間。例如，對您的密碼散列加鹽，這樣就不用散列了 $ H(p_1), $ $ H(p_2), $ $ \dotsc, $ $ H(p_t) $ 對於秘密密碼 $ p_1, p_2, \dotsc, p_t $ , 對手將有鹽漬雜湊 $ H_{\sigma_1}(p_1), $ $ H_{\sigma_2}(p_2), $ $ \dotsc, $ $ H_{\sigma_t}(p_t) $ ，這阻礙了彩虹表和區分點算法的批量優勢。
這也可以應用於分組密碼，例如隨機選擇的初始化向量，但有一些成本：額外的數據傳輸、隨機化的有限塊大小、隨機選擇的 IV 內的隱含密鑰、錯過檢測重放攻擊或隨機數濫用的機會等*。*
輸入空間分離也不會讓對手更難找到你的密鑰，所以你個人沒有動力選擇輸入空間分離的密碼系統；它只會讓對手更難找到任何人的鑰匙。相比之下，使用 256 位密鑰可為您和整個群體提供對暴力破解的免疫力。
但通用密鑰搜尋並不是多目標攻擊可能相關的唯一設置。以下是其他一些：
- 對於帶有生成器的 DLOG 組 $ g $ —例如，RFC 3526 Group #14或 Curve25519 或 secp256k1 — 對手可能擁有權力 $ g^{x_1}, $ $ g^{x_2}, $ $ \dotsc, $ $ g^{x_t} $ 為了 $ t $ 不同的未知目標指數 $ x_1, x_2, \dotsc, x_t $ . 目標是恢復任何一個 $ x_i $ .
當然，這可以通過雜湊函式下的任何通用原像搜尋來解決 $ H\colon x \mapsto g^x $ ，但有更便宜的算法成本 $ O(\sqrt q) $ 在哪裡 $ q $ 是階數的最大素數 $ g $ ——波拉德的組合 $ \rho $ 和 Pohlig-Hellman 和 Pollard 的袋鼠，如果知道更多關於 $ x_i $ ，以及其他替代方案，如嬰兒步/巨人步。對於特定的群體，可能會有比通用算法更快的速度，比如 Pollard 中的橢圓曲線否定映射 $ \rho $ .
找到第一個的成本 $ t $ 目標離散日誌不能比找到一個目標離散日誌便宜得多！ 為什麼？修復單個目標 $ h = g^x $ , 並選擇 $ g^{r_1}, $ $ g^{r_2} $ , $ \dotsc, $ $ g^{r_t} $ 對於均勻隨機指數 $ r_i $ ; 然後應用多目標攻擊$$ (h g^{r_1}, h g^{r_2}, \dotsc, h g^{r_t}) $$去尋找 $ \log_g (h g^{r_i}) $ 對於一些 $ i $ , 弄清楚什麼 $ i $ 最壞的情況是通過線性列表搜尋，最後返回$$ \log_g (h g^{r_i}) - r_i = \log_g (h g^{r_i}!/g^{r_i}) = \log_g h. $$ 因此，單目標 DLOG 不會比多目標 DLOG 攻擊更昂貴，因為這顯示瞭如何使用多目標 DLOG 攻擊來執行單目標 DLOG 攻擊，而額外成本基本上可以忽略不計。換句話說，擁有多個可能的目標並不能降低 DLOG 攻擊的成本，因為它可以降低通用密鑰搜尋的成本。
**這就是為什麼，例如，Curve25519 應該被認為具有“128 位安全級別”而 AES-128 不應該：**在現實世界的多目標設置中，打破第一個安全級別的成本 $ t $ 目標Curve25519鍵還在左右 $ 2^{128} $ - 與破壞一個目標 Curve25519 鍵的成本相同 - 而破壞第一個目標的成本 $ t $ 目標 AES 密鑰僅 $ 2^{128}!/t $ .
另一方面，找到所有 $ t $ 並行目標 $ \rho $ : 雖然是 $ O(\sqrt q) $ 對於任意數量的目標中的第一個，它是 $ O(\sqrt{tq}) $ 對於所有_ $ t $ 目標而不是 $ O(t\sqrt q) $ 對於重複的單目標攻擊 $ t $ 次——也就是說，多目標攻擊找到所有 $ t $ 鍵是一個因素 $ \sqrt t $ 比便宜 $ t $ 獨立的單目標攻擊。預計算也可能有一個優勢：對於有限域，最好的 DLOG 算法會考慮到昂貴的與目標無關的預計算，然後可以完成一次，然後一遍又一遍地重複使用以快速攻擊同一組中的許多目標，從而導致像logjam這樣的攻擊。情報機構可以使用它來實時攔截 TLS 對話。
- 對於 Diffie-Hellman 函式 $ f(n, P) $ 帶標準基點 $ B $ —例如，RFC 3526 Group #14 或 X25519 下的 FFDH — 攻擊者可能擁有公鑰 $ f(n_1, B), $ $ f(n_2, B), $ $ \dotsc, $ $ f(n_t, B) $ ， 為了 $ t $ 不同的未知DH秘密 $ n_1, n_2, \dotsc, n_t $ , 連同 oracles 為 $ P \mapsto H(f(n_i, P)) $ 通過聲稱擁有公鑰 $ P $ 並嘗試與 $ i^{\mathit{th}} $ 使用者。目標是恢復任何一個 $ H(f(n_i, f(n_j, B))) $ 使用者使用的共享密鑰 $ i $ 和使用者 $ j $ 進行私人談話。
當然，當 $ f(n, P) = [n]P $ 在一個加法編寫的組中，這可以通過任何通用 DLOG 算法來解決。但是預言機提供了可以被利用的額外資訊——Lim-Lee 主動小型子群攻擊，如果這些點 $ P $ 生活在一組複合秩序中，Cheon的強DH攻擊如果密鑰推導函式 $ H $ 是身份。這些本身並沒有提供批次優勢，但它們證明了 DH 問題與 DLOG 問題在性質上是不同的，因此原則上它可能承認 DLOG 沒有的批次優勢。
- 對於簽名方案，目標是偽造消息/簽名對 $ (m, \sigma) $ 根據任何_ $ t $ 公鑰 $ A_1, A_2, \dotsc, A_t $ . 故事取決於密碼系統的細節；例如，請參閱多目標設置中的 Schnorr 簽名分析。例如，EdDSA 選擇的對策是將公鑰與消息一起散列，以限制多目標籤名偽造的途徑。