當密碼學家談「硬體」時，他們指的是 ASIC（特定應用積體電路）、PLD（可程式邏輯裝置）與 FPGA（現場可程式邏輯閘陣列）。

• 硬體實作是一個在位元層級實作密碼演算法的電子電路，不能拿來做別的事——也就是專用硬體。
• 軟體實作則只是告訴微處理器該執行哪些指令來跑演算法。這些指令操作位元組或字，再呼叫實作加法、乘法等通用運算的電路片段。

最早的串流密碼以位元為單位運作，正是為了省去複雜的字級運算，從而在當時的目標平台——硬體——上更有效率。

為什麼硬體愛用串流密碼#

串流密碼之所以常用於硬體實作，主要原因是它們比區塊密碼便宜。串流密碼需要的記憶體與邏輯閘都比區塊密碼少，因此在積體電路上佔的面積較小，降低了製造成本。

以閘等效數（gate-equivalents，積體電路的標準面積度量）計算：

也就是說，用區塊密碼做密碼學的成本曾比串流密碼貴上一個數量級。

但今天區塊密碼已不再比串流密碼昂貴。一來現在有跟串流密碼差不多小的硬體友善區塊密碼，二來硬體成本已經大幅下滑。

串流密碼之所以仍常與硬體聯想在一起，只是因為它們曾經是最佳選擇。

第一個標準區塊密碼 DES 是為硬體而非軟體最佳化的。美國政府在 1970 年代將 DES 標準化時，多數目標應用都是硬體實作。因此毫不意外地，DES 的 S-box 都很小，在硬體中以邏輯電路實作時計算飛快，但在軟體中很沒效率。

相對地，現行的 AES 處理位元組，因此在軟體中比 DES 更有效率。

回饋移位暫存器（FSR）#

幾乎所有硬體串流密碼都以某種方式依賴回饋移位暫存器（FSR，feedback shift registers）——從 2G 手機用的 A5/1，到較新的 Grain-128a 都是。

FSR 就是一個配備了更新回饋函式（記為 f）的位元陣列。FSR 的狀態存放在這個陣列（暫存器）中，每次更新都用回饋函式改變狀態值並產生一個輸出位元。

運作規則：若 R₀ 是 FSR 的初始值，下一個狀態 R₁ 定義為 R₀ 左移 1 位元，離開暫存器的那個位元作為輸出回傳，而空出來的位置填入 f(R₀)：

R(t+1) = (Rt << 1) | f(Rt)

其中 | 是邏輯 OR、<< 是位移運算子（如 C 語言）。位移把位元往左推，丟掉最左邊的位元以維持狀態的位元長度，並把最右邊的位元清零；FSR 的更新操作完全相同，只是最右邊的位元不是設為 0，而是設為 f(Rt)。

一個 4 位元 FSR 的例子#

考慮一個 4 位元 FSR，其回饋函式 f 把 4 個位元全部 XOR 起來。從狀態 1100 開始：

1100 → 輸出 1，f(1100) = 1⊕1⊕0⊕0 = 0 → 1000
1000 → 輸出 1，f(1000) = 1⊕0⊕0⊕0 = 1 → 0001
0001 → 輸出 0                        → 0011
0011 → 輸出 0                        → 0110
0110 → 輸出 0                        → 1100

五次迭代後我們回到初始狀態 1100。

我們說這個 FSR 對 1100、1000、0001、0011、0110 這幾個值而言，週期（period）是 5。

因為週期是 5，把暫存器推 10 次會得到同一個 5 位元序列兩次。從 1100 開始推 20 次，輸出位元會是 11000110001100011000——也就是 11000 這個 5 位元序列重複四次。

直覺上，這種重複樣式應該避免，週期越長對安全性越好。

若你打算在串流密碼中使用 FSR，避免使用週期短的，因為那會讓輸出更可預測。

有些類型的 FSR 很容易看出它的週期，有些則幾乎不可能。

這個 4 位元 FSR 另外還有兩個週期為 5 的循環：{0100, 1001, 0010, 0101, 1010} 與 {1111, 1110, 1101, 1011, 0111}。任何給定狀態只能屬於一個狀態循環。這裡有三個各含五個狀態的循環，涵蓋了 4 位元暫存器 2^4 = 16 個可能值中的 15 個。第 16 個值 0000 則是一個週期為 1 的循環——FSR 把 0000 變換成 0000。

線性回饋移位暫存器（LFSR）#

LFSR（linear feedback shift registers）是回饋函式為線性的 FSR——也就是說，該函式是狀態中某些位元的 XOR，就像上一節的 4 位元例子。

記得在密碼學中，線性等同於可預測，並暗示著底層存在一個簡單的數學結構。

如何取得最大週期#

哪些位元被 XOR 在一起，對 LFSR 的週期至關重要，因而也決定了它的密碼學價值。好消息是：我們知道如何挑選位元位置，以保證取得 2^n − 1 的最大週期。

做法：取各位元的索引（最右邊為 1，最左邊為 n），寫出多項式 1 + X + X² + ... + Xⁿ，其中只有當第 i 個位元是回饋函式中被 XOR 的位元之一時，才納入 X^i 這一項。

要成為本原多項式，該多項式必須：

• 不可約（irreducible）：不能被因式分解，也就是不能寫成更小多項式的乘積。例如 X + X³ 就不是不可約的，因為它等於 (1 + X)(X + X²)：

  (1 + X)(X + X²) = X + X² + X² + X³ = X + X³

• 滿足某些其他數學性質——這些性質不用非平凡的數學概念不好解釋，但很容易測試。

n 位元 LFSR 的最大週期是 2^n − 1 而非 2^n，因為全零狀態永遠自我循環。

任意數量的零 XOR 起來都是零，所以從回饋函式進入狀態的新位元永遠是零；全零狀態註定永遠是全零。

兩個對照的例子#

非本原多項式 1 + X + X³ + X⁴（位置 1、3、4 的位元 XOR 在一起）——它可以被分解成 (1 + X³)(1 + X)，因此週期不是最大值。從 0001 開始：

0001 → 0011 → 0111 → 1110 → 1100 → 1000 → 0001

六次更新後回到初始狀態，證明這是一個週期為 6 的循環，而非最大值 15。

本原多項式 1 + X³ + X⁴——週期確實是最大值 15：

0001  0011  0101  1110
0010  0110  1011  1100
0100  1101  0111  1000
1001  1010  1111  0001

狀態走遍除 0000 外所有可能值且不重複，最後才回到起點。

但 LFSR 當串流密碼並不安全#

若 n 是 LFSR 的位元長度，攻擊者只需要 n 個輸出位元就能還原 LFSR 的初始狀態，從而算出所有先前的位元、預測所有未來的位元。

這個攻擊之所以可行，是因為 Berlekamp–Massey 演算法能解出 LFSR 數學結構所定義的方程式，不只找出初始狀態，連回饋多項式都能找出來。

更糟的是，你甚至不需要知道 LFSR 的確切長度——對所有可能的 n 值重複執行 Berlekamp–Massey 演算法，直到命中正確的那個即可。

結論：LFSR 在密碼學上是弱的，因為它們是線性的。 輸出位元與初始狀態位元之間由簡短的方程式關聯，用高中線性代數技巧就能輕鬆解開。

濾波 LFSR#

要緩解 LFSR 的不安全性，你可以在回傳輸出位元之前先讓它們通過一個非線性函式，藉此隱藏其線性——這稱為濾波 LFSR（filtered LFSR）。

這個 g 函式必須是非線性函式——既把位元 XOR 起來，也用邏輯 AND 或 OR 把它們結合。例如 L₁L₂ + L₃L₄ 就是非線性函式（省略了乘號，L₁L₂ 意即 L₁ × L₂，或 C 語法的 L₁ & L₂）。

回饋函式可以直接用 FSR 的位元書寫（如 L₁L₂ + L₃L₄），也可以用等價的多項式記法（1 + XX² + X³X⁴）。

直接記法比較好懂，多項式記法則更適合分析 FSR 的數學性質。

濾波 LFSR 比純 LFSR 強，因為非線性函式挫敗了直截了當的攻擊。但更複雜的攻擊仍能攻破這個系統：

• 代數攻擊（algebraic attacks）：解出從輸出位元推導出的非線性方程組，方程式中的未知數就是 LFSR 狀態的位元。
• 立方攻擊（cube attacks）：計算非線性方程式的導數，把方程組的次數降到 1，再像線性系統一樣有效率地求解。
• 快速相關攻擊（fast correlation attacks）：利用那些「儘管非線性、行為卻傾向於像線性函式」的濾波函式。

這裡的教訓與前面的例子一致：OK 繃補不了槍傷。

在一個已被攻破的演算法上打一層稍強的補丁，並不會讓整體變安全。問題必須從核心解決。

非線性 FSR（NFSR）#

NFSR（nonlinear FSRs）與 LFSR 相似，但回饋函式是非線性的：除了逐位元 XOR，還可以包含逐位元 AND 與 OR 運算。這有利也有弊。

優點：方程式呈指數成長#

非線性回饋函式讓 NFSR 在密碼學上比 LFSR 更強，因為輸出位元以複雜的方式依賴初始秘密狀態，其方程式的大小呈指數成長。

以一個 4 位元 NFSR 為例，初始秘密狀態 (N₁, N₂, N₃, N₄)，回饋函式為 N₁ + N₂ + N₁N₂ + N₃N₄。第一個輸出位元是：

N₁ + N₂ + N₁N₂ + N₃N₄

第二次迭代把 N₁ 換成這個新位元。以初始狀態表示第二個輸出位元，得到：

(N₁N₂ + N₃N₄ + N₁ + N₂) + N₁ + (N₁N₂ + N₃N₄ + N₁ + N₂)N₁ + N₂N₃
  = N₁N₃N₄ + N₁N₂ + N₂N₃ + N₃N₄ + N₁ + N₂

新方程式的代數次數是 3（相乘位元數最多的項是 N₁N₃N₄），而回饋函式本身只有次數 2；項數也從四項變成六項。

結果就是：迭代非線性函式很快就產生無法處理的方程式，因為輸出的大小呈指數成長。

執行 NFSR 時你永遠不必計算這些方程式，但攻擊者為了破解系統就得解開它們。

缺點：週期無從得知#

NFSR 的一個缺點是：沒有有效率的方法判定 NFSR 的週期，或哪怕只是知道其週期是否為最大值。

對一個 n 位元的 NFSR，你得跑將近 2^n 次試驗才能驗證其週期是最大值。對 80 位元以上的大型 NFSR，這是不可能的。

所幸有個技巧能讓你使用 NFSR 而不必擔心短週期：把 LFSR 與 NFSR 結合起來，同時取得保證的最大週期與密碼學強度。Grain-128a 正是這麼做的。

Grain-128a#

還記得第 4 章談 AES 區塊密碼時提到的 AES 競賽嗎？串流密碼 Grain 是一個類似計畫的產物——eSTREAM 競賽。這場競賽於 2008 年結束，選出了一份推薦串流密碼的入選名單，包含四個硬體導向密碼與四個軟體導向密碼。Grain 是其中一個硬體密碼，而 Grain-128a 是原作者推出的升級版。

結構#

Grain-128a 簡單到幾乎是串流密碼所能達到的極限：一個 128 位元的 LFSR、一個 128 位元的 NFSR，以及一個濾波函式 h。

• LFSR 的最大週期是 2^128 − 1，這確保整個系統的週期至少是 2^128 − 1，藉此防範 NFSR 中潛在的短循環。
• 同時，NFSR 與非線性濾波函式 h 提供密碼學強度。

初始化#

Grain-128a 接收一把 128 位元金鑰與一個 96 位元 nonce：

1. 把 128 個金鑰位元複製進 NFSR 的 128 個位元。
2. 把 96 個 nonce 位元複製進 LFSR 的前 96 個位元，剩下的 32 位元填入 1，最後一位填 0。
3. 初始化階段把整個系統更新 256 次，才回傳第一個金鑰流位元。

初始化期間 h 函式回傳的位元不會作為金鑰流輸出，而是送進 LFSR，以確保它後續的狀態同時依賴於金鑰與 nonce。

回饋函式#

LFSR 的回饋函式（L₁, L₂, ..., L₁₂₈ 為 LFSR 的位元）：

f(L) = L32 + L47 + L58 + L90 + L121 + L128

它只從 128 位元的 LFSR 取 6 個位元，但這足以得到一個保證最大週期的本原多項式。位元數少也最小化了硬體實作的成本。

NFSR 的回饋多項式（N₁, ..., N₁₂₈）：

g(N) = N32 + N37 + N72 + N102 + N128
     + N44·N60 + N61·N125 + N63·N67 + N69·N101
     + N80·N88 + N110·N111 + N115·N117
     + N46·N50·N58 + N103·N104·N106 + N33·N35·N36·N40

這個函式被審慎挑選，以在最小化實作成本的同時最大化密碼學強度。它的代數次數是 4（變數最多的項 N₃₃N₃₅N₃₆N₄₀ 有四個變數），而且高度非線性，無法用線性函式逼近。

除了 g 之外，Grain-128a 還會把從 LFSR 出來的位元 XOR 進去，把結果回饋為 NFSR 新的最右位元。

濾波函式 h 是另一個非線性函式，它從 NFSR 取 9 個位元、從 LFSR 取 7 個位元，以確保良好密碼學性質的方式結合它們。

在本書寫作時，Grain-128a 沒有已知的攻擊，作者有信心它會保持安全。

它被用在某些需要精簡快速串流密碼的低階嵌入式系統——通常是工業專有系統——這也是為什麼 Grain-128a 在開源軟體社群中鮮為人知。

A5/1#

A5/1 是 2G 行動標準中用來加密語音通訊的串流密碼。它於 1987 年制定，但直到 1990 年代末被逆向工程後才公開。攻擊在 2000 年代初出現，A5/1 最終被以「能真正（而非理論上）解密加密通訊」的方式攻破。

運作機制#

A5/1 依賴三個 LFSR，並使用一個乍看聰明、實則不安全的技巧。三個 LFSR 分別是 19、22、23 位元，多項式為：

LFSR 1 (19 bits):  1 + X^14 + X^17 + X^18 + X^19
LFSR 2 (22 bits):  1 + X^21 + X^22
LFSR 3 (23 bits):  1 + X^8 + X^21 + X^22 + X^23

只有 LFSR、沒有 NFSR，怎麼可能安全？訣竅在於它的更新機制：設計者沒有在每個時脈週期更新全部三個 LFSR，而是加了一條時脈規則：

1. 檢查 LFSR 1 的第 9 位元、LFSR 2 的第 11 位元、LFSR 3 的第 11 位元，稱為時脈位元（clocking bits）。這三個位元要嘛全部相同，要嘛恰好兩個相同。
2. 只推進那些時脈位元等於多數值的暫存器。每次更新會推進兩個或三個 LFSR。

沒有這條簡單的規則，A5/1 將毫無安全性可言；而繞過這條規則就足以破解該密碼。

在 A5/1 的不規則時脈規則下，每個暫存器在任一次更新時被推進的機率是 3/4：至少有另一個暫存器具有相同位元值的機率是 1 − (1/2)²，其中 (1/2)² 是另外兩個暫存器都具有不同位元值的機率。

攻擊面#

2G 通訊使用 64 位元金鑰與 22 位元 nonce 的 A5/1，nonce 每個新資料訊框都會更換。針對 A5/1 的攻擊還原系統的 64 位元初始狀態（19 + 22 + 23 的 LFSR 初始值），從而藉由反推初始化機制揭露 nonce（若尚未得知）與金鑰。

這些攻擊被稱為已知明文攻擊（KPA），因為部分加密資料是已知的，攻擊者可以把密文與已知的明文片段 XOR，藉此判定對應的金鑰流部分。

A5/1 的攻擊主要有兩類：

• 精巧攻擊：利用 A5/1 的內部線性與其簡單的不規則時脈系統。
• 蠻力攻擊：只利用 A5/1 的短金鑰與訊框編號注入的可逆性。

For all 2^19 values of LFSR 1's initial state
    For all 2^22 values of LFSR 2's initial state
        For all 2^11 values of LFSR 3's clocking bit during the first 11 clocks
             Reconstruct LFSR 3's initial state
             Test whether guess is correct; if yes, return; else continue

蠻力攻擊：時間—記憶體權衡#

時間—記憶體權衡攻擊（TMTO）是針對 A5/1 的蠻力攻擊。它完全不管 A5/1 的內部結構，只在乎它的狀態長 64 位元——把 A5/1 看成一個吃進 64 位元值（狀態）、吐出 64 位元值（前 64 個金鑰流位元）的黑箱。

攻擊的想法是：用大量記憶體換取更低的暴力搜尋成本。

最簡單的 TMTO 是碼本攻擊：預先計算一張 2^64 個元素的「鍵：值」表，為 2^64 個可能鍵各存下輸出值。攻擊時只要蒐集一個 A5/1 實例的輸出，在表中查出對應的鍵即可。攻擊本身很快——只花查記憶體的時間——但建表要 2^64 次 A5/1 計算。

更糟的是記憶體：碼本攻擊需要 2^64 × (64 + 64) 位元，也就是 2^68 位元組 = 256 EB。那是好幾十座資料中心，可以免談了。

TMTO 攻擊以「攻擊線上階段的計算量增加」為代價，降低碼本攻擊所需的記憶體：表越小，破解一把金鑰所需的計算就越多。無論如何，準備表仍需約 2^64 次運算，但這只要做一次。

2010 年，研究人員用 GPU 平行執行 100,000 個 A5/1 實例，花了約兩個月產生 2TB 的表。

有了這些大表，以 A5/1 加密的通話幾乎能被即時解密。

電信業者實作了一些權宜措施來緩解此攻擊，但真正的解決方案要等到後來的 3G 與 4G 行動電話標準——它們徹底捨棄了 A5/1。