冷戰期間，美國與蘇聯各自發展出自己的密碼。美國政府創造了 DES（Data Encryption Standard），從 1979 到 2005 年被採用為聯邦標準；KGB 則開發了 GOST 28147-89，一個保密到 1990 年、至今仍在使用的演算法。2000 年，美國國家標準暨技術研究院（NIST）選出了 DES 的後繼者 AES（Advanced Encryption Standard）——一個在比利時開發、如今存在於多數電子裝置中的演算法。

AES、DES 與 GOST 28147-89 有個共通點：它們都是區塊密碼——一種把「處理資料區塊的核心演算法」與「處理資料區塊序列的技巧（運作模式）」結合起來的密碼。

本章脈絡#

1. 什麼是區塊密碼——安全目標（偽隨機置換）、區塊大小的取捨、碼本攻擊。
2. 如何建構區塊密碼——輪與輪金鑰、滑動攻擊、SPN 與 Feistel 架構。
3. AES——內部結構、每個操作的必要性、它到底有多安全。
4. 實作 AES——查表式實作與快取時序攻擊、AES 原生指令。
5. 運作模式——ECB、CBC、CTR，以及填充與密文竊取。

常見錯誤#

有兩個關於區塊密碼的攻擊必須知道：1970 年代發現、至今仍在許多密碼分析攻擊中使用的中間相遇攻擊（別與中間人攻擊混淆），以及 2002 年由學術密碼學家發現、之後大致被忽略、十年後又連同數個有漏洞的應用一起被重新發現的填充預言機攻擊。

中間相遇攻擊#

3DES 區塊密碼是 1970 年代 DES 標準的升級版，接收一把 56 × 3 = 168 位元的金鑰（相對 DES 的 56 位元是個改進）。

但 3DES 的安全等級是 112 位元而非 168 位元，原因就是中間相遇攻擊（MitM，meet-in-the-middle）。

3DES 用 DES 的加密與解密函式來加密一個區塊：先用金鑰 K₁ 加密，再用金鑰 K₂ 解密，最後用另一把金鑰 K₃ 加密。

若 K₁ = K₂，前兩次呼叫互相抵銷，3DES 就退化成使用金鑰 K₃ 的單一 DES。

3DES 採用「加密—解密—加密」而非連續加密三次，正是為了讓系統能在必要時用新的 3DES 介面模擬 DES。

為什麼要三重 DES 而不是雙重 DES（也就是 E(K₂, E(K₁, P))）？因為中間相遇攻擊讓雙重 DES 只有單一 DES 的安全性。

攻擊雙重 DES 的流程：

1. 假設你有 P 與 C = E(K₂, E(K₁, P))，以及兩把未知的 56 位元金鑰 K₁、K₂（DES 用 56 位元金鑰，所以雙重 DES 共 112 個金鑰位元）。你建一張有 2^56 筆的鍵—值表，存放 E(K₁, P)，其中 K₁ 是被存的值。
2. 對 K₂ 的全部 2^56 個值，計算 D(K₂, C)，檢查所得的值是否作為索引出現在表中（也就是作為中間值）。
3. 若在表的索引中找到某個中間值，就取出對應的 K₁，並用其他的 P、C 對驗證找到的 (K₁, K₂) 是否正確：用 K₁ 與 K₂ 加密 P，檢查得到的密文是否為給定的 C。

這個方法只用約 2^57 次運算（而非 2^112）就還原了 K₁ 與 K₂：步驟 1 加密 2^56 個區塊，步驟 2 至多解密 2^56 個區塊，總計 2^56 + 2^56 = 2^57。

你還需要儲存 2^56 個各 15 位元組的元素，約 1 EB——這很多，但有一個技巧能讓同樣的攻擊只用微不足道的記憶體就跑起來（見第 6 章）。

你可以用幾乎相同的方式把 MitM 攻擊套用到 3DES，差別只在於第三階段要走過 K₂ 與 K₃ 的全部 2^112 個值。因此整個攻擊在約 2^112 次運算後成功——這就是為什麼 3DES 儘管有 168 位元的金鑰材料，卻只得到 112 位元安全性。

填充預言機攻擊#

本章以 2000 年代最簡單卻也最具毀滅性的攻擊之一作結：填充預言機攻擊（padding oracle attack）。

記得填充會在明文後補上額外位元組以填滿一個區塊。例如 111 位元組的明文是六個 16 位元組區塊後面跟著 15 位元組，為了湊成完整區塊，填充加上一個 01 位元組；110 位元組的明文則加上兩個 02 位元組，依此類推。

填充預言機（padding oracle）是一個「會依 CBC 加密密文中的填充是否有效而有不同行為」的系統。你可以把它看成一個回傳成功或錯誤值的黑箱或 API。填充預言機可能存在於某個遠端主機的服務中——它在收到格式錯誤的密文時送出錯誤訊息。

給定一個填充預言機，攻擊者記錄哪些輸入有有效填充、哪些沒有，並利用這個資訊解密所選的密文值。

攻擊流程（假設你想解密密文區塊 C₂，令 X = D(K, C₂) 為你要找的值，P₂ 為 CBC 解密後所得的區塊）：

如果你挑一個隨機區塊 C₁，把兩區塊密文 C₁ ‖ C₂ 送給預言機，只有在 C₁ ⊕ P₂ = X 以有效填充結尾（單一個 01、兩個 02、三個 03……）時解密才會成功。基於這個觀察：

1. 挑一個隨機區塊 C₁，改變它的最後一個位元組，直到填充預言機接受該密文為有效。通常在有效密文中 C₁[15] ⊕ X[15] = 01，所以你在試過約 128 個 C₁[15] 的值之後就會找到 X[15]。
2. 把 C₁[15] 設成 X[15] ⊕ 02，搜尋能給出正確填充的 C₁[14]，藉此找出 X[14]。當預言機接受該密文時，代表你找到了滿足 C₁[14] ⊕ X[14] = 02 的 C₁[14]。
3. 對全部 16 個位元組重複步驟 1 與 2。

這個攻擊平均對每個位元組需要 128 次預言機查詢，16 個位元組總共約 2000 次查詢就能解出一個區塊。（注意每次查詢都必須使用相同的初始值。）

實務上實作填充預言機攻擊比這裡描述的稍微複雜，因為你得處理步驟 1 中的錯誤猜測：一段密文的填充有效，可能不是因為 P₂ 以單一個 01 結尾，而是因為它以兩個 02 或三個 03 結尾。

但這很容易處理——測試那些修改了更多位元組之密文的有效性即可。

延伸閱讀#

關於區塊密碼可談的還很多，無論是演算法如何運作，或是它們如何被攻擊。

• 建構方式不只 Feistel 與 SPN：區塊密碼 IDEA 與 FOX 使用 Lai–Massey 建構，Threefish 使用 ARX 網路（加法、字元旋轉與 XOR 的組合）。
• 模式也不只 ECB、CBC、CTR：有些模式是沒人用的民俗技法（如 CFB 與 OFB），有些則針對特定應用（如可調整加密的 XTS，或鑑別式加密的 GCM）。
• AES 競賽的其他 14 個演算法：CAST-256、CRYPTON、DEAL、DFC、E2、FROG、HPC、LOKI97、Magenta、MARS、RC6、SAFER+、Serpent、Twofish。建議去查查它們如何運作、如何設計、如何被攻擊、以及速度如何。
• 也值得看看 NSA 的設計（Skipjack，以及較近期的 SIMON 與 SPECK），還有較新的「輕量級」區塊密碼，例如 KATAN、PRESENT 或 PRINCE。