密碼學/中間相遇攻擊

一種極其專業的攻擊，中間相遇攻擊是一種已知明文攻擊，它隻影響特定型別的加密方法 - 那些透過使用一個或多個“輪次”的普通對稱加密演算法來實現更高安全性的方法。 3DES 就是這種複合系統的一個例子。

但是，為了解釋這種攻擊，讓我們從一個更簡單的系統開始，定義如下：兩個密碼系統，分別表示為 $encrypt_{\alpha }$ 和 $encrypt_{\beta }$ （其逆函式分別為 $decrypt_{\alpha }$ 和 $decrypt_{\beta }$ ）被簡單地組合起來（透過先應用一個，然後應用另一個）來形成一個複合密碼系統。每個系統都接受一個 64 位金鑰（用於從 0 到 18446744073709551615 的值），我們可以稱之為 $key_{\alpha }$ 或 $key_{\beta }$ ，具體情況視情況而定。

所以，對於給定的明文，我們可以計算出密文，如下所示：

$cryptotext=encrypt_{\beta }(key_{\beta },encrypt_{\alpha }(key_{\alpha },plaintext))$

相應地：

$plaintext=decrypt_{\alpha }(key_{\alpha },decrypt_{\beta }(key_{\beta },cryptotext))$

現在，鑑於每個系統都有一個 64 位金鑰，用於加密或解密所需的金鑰量為 128 位，因此簡單的分析將假設這與 128 位密碼相同。

但是，如果擁有足夠的儲存空間，可以將這種有效金鑰強度降低到比所使用的兩個金鑰中的較大金鑰大幾位，如下所示。

給定明文/密文對，將 $encrypt_{\alpha }$ 應用於明文，並依次使用每個可能的金鑰，生成 $2^{64}$ 個中間密文 $cryptotext_{1}$ $\rightarrow$ $cryptotext_{n}$ ，其中 $n=2^{64}$
將每個 $n$ 密文儲存在雜湊表中，以便可以透過其密文引用每個密文，並給出用於生成該密文的金鑰。
將 $decrypt_{\beta }$ 應用於密文，依次嘗試每個可能的金鑰，並將中間明文與之前計算的雜湊表進行比較。這將得到一對金鑰（用於兩種演算法中的每一種， $\alpha$ 和 $\beta$ ）。
使用第三階段的兩個金鑰，針對第二對明文/密文測試每個金鑰。如果也匹配，則極有可能擁有訊息的有效金鑰對 - 並非在 $2^{128}$ 次操作中，而是在“僅僅” $2x2^{64}$ 次操作中（儘管由於雜湊表操作，這些操作明顯更長，但並沒有增加任務複雜度超過幾個額外的位）。

這種方法的缺點是儲存空間。假設使用64位金鑰，那麼至少需要 $2^{64}$ 個儲存單位 - 其中每個單位是單個雜湊記錄所佔用的儲存空間。即使使用最小的實現（例如，金鑰 64 位加上 4 位雜湊衝突開銷），如果使用 160GB 硬碟來實現這樣的系統，也需要近十億個硬碟來儲存雜湊表本身。