軟體串流密碼處理的是位元組或 32／64 位元的字，而非個別位元。這在現代 CPU 上更有效率——指令對一個字執行算術運算所花的時間，與對一個位元執行時相同。

因此比起硬體密碼，軟體串流密碼更適合跑在個人電腦上的伺服器或瀏覽器，因為那裡有強大的通用處理器把密碼當原生軟體執行。

為什麼軟體串流密碼重新受到重視#

• 硬體變便宜、CPU 變強大：許多裝置都內嵌強大的 CPU，對小型位元導向密碼的需求降低了。例如 4G 行動通訊標準中的兩個串流密碼（歐洲的 SNOW3G 與中國的 ZUC）處理的都是 32 位元字而非位元，與較老的 A5/1 不同。
• CBC 模式區塊密碼的填充預言機攻擊慘劇：在那之後，串流密碼在軟體領域的人氣以區塊密碼為代價上升。
• 串流密碼更容易規範與實作：它們不必把訊息位元與金鑰位元混在一起，只是把金鑰位元當秘密吃進去。

事實上，最流行的串流密碼之一其實是偽裝成串流密碼的區塊密碼：計數器模式（CTR）的 AES。

有一種軟體串流密碼設計（SNOW3G 與 ZUC 採用）是照抄硬體密碼與它們的 FSR，把位元換成位元組或字。但這對密碼學家而言不是最有趣的設計。本書寫作時，最值得關注的兩個設計是 RC4 與 Salsa20——儘管其中一個已經徹底崩壞。

RC4#

RC4 由 RSA Security 的 Ron Rivest 於 1987 年設計，1994 年被逆向工程並外洩。它長期以來是使用最廣的串流密碼，用於無數應用中，最著名的是第一代 Wi-Fi 加密標準 WEP（Wired Equivalent Privacy）與建立 HTTPS 連線的 TLS 協定。

遺憾的是，RC4 對多數應用（包括 WEP 與 TLS）都不夠安全。

RC4 如何運作#

RC4 是有史以來最簡單的密碼之一。它不執行任何密碼學式的操作——沒有 XOR、沒有乘法、沒有 S-box……什麼都沒有。它只是交換位元組。

RC4 的內部狀態是一個 256 位元組的陣列 S，先設為 S[0]=0, S[1]=1, ..., S[255]=255，再用金鑰排程演算法（KSA）從一把 n 位元組的金鑰 K 初始化：

j = 0
# set S to the array S[0] = 0, S[1] = 1, . . . , S[255] = 255
S = range(256)
# iterate over i from 0 to 255
for i in range(256):
    # compute the sum of v
    j = (j + S[i] + K[i % n]) % 256
    # swap S[i] and S[j]
    S[i], S[j] = S[j], S[i]

演算法跑完後，陣列 S 仍然包含 0 到 255 的所有位元組值，但順序看起來是隨機的。例如以全零的 128 位元金鑰，狀態 S 變成：

0, 35, 3, 43, 9, 11, 65, 229, (...), 233, 169, 117, 184, 31, 39

若翻轉金鑰的第一個位元再跑一次 KSA，會得到完全不同、看似隨機的狀態：

32, 116, 131, 134, 138, 143, 149, (...), 152, 235, 111, 48, 80, 12

有了初始狀態 S，RC4 產生與明文 P 等長的金鑰流 KS 來計算密文 C = P ⊕ KS（設 P 長 m 位元組）：

i = 0
j = 0
for b in range(m):
    i = (i + 1) % 256
    j = (j + S[i]) % 256
    S[i], S[j] = S[j], S[i]
    KS[b] = S[(S[i] + S[j]) % 256]

for 迴圈的每次迭代最多修改 RC4 內部狀態 S 的 2 個位元組——被交換的 S[i] 與 S[j]。若 j 等於 i，則 S[i] 不被修改。

這看起來簡單到不可能安全，但密碼分析者花了 20 年才找到可利用的瑕疵。在那之前，我們只知道 RC4 在特定實作中的弱點——例如第一代 Wi-Fi 加密標準 WEP。

失敗案例一：WEP 中的 RC4#

WEP 是第一代 Wi-Fi 安全協定，如今因協定設計與 RC4 兩方面的弱點而完全崩壞。

在 WEP 的實作中，RC4 加密 802.11 訊框的載荷資料。同一個工作階段中所有載荷都使用同一把 40 或 104 位元的秘密金鑰，但訊框標頭中編有一個「理應唯一」的 3 位元組 nonce。看出問題了嗎？

問題在於：RC4 不支援 nonce（至少官方規格中不支援），而串流密碼沒有 nonce 就不能用。

WEP 設計者用一個權宜之計繞過這個限制：他們在無線訊框標頭中放一個 24 位元的 nonce，並把它接在 WEP 金鑰前面當成 RC4 的秘密金鑰。也就是說，若 nonce 是位元組 N[0], N[1], N[2]、WEP 金鑰是 K[0]...K[4]，實際的 RC4 金鑰就是 N[0], N[1], N[2], K[0], K[1], K[2], K[3], K[4]。

淨效果是 40 位元秘密金鑰產生 64 位元的有效金鑰，104 位元金鑰產生 128 位元的有效金鑰。結果？號稱 128 位元的 WEP 協定實際上頂多提供 104 位元的安全性。

但 WEP 這個 nonce 花招真正的問題是：

• nonce 太小，只有 24 位元。 若每則新訊息都隨機挑選 nonce，大約等 2^(24/2) = 2^12 個封包（幾 MB 的流量）就會撞到兩個用同一個 nonce、因而同一串金鑰流加密的封包。即使 nonce 是從 0 跑到 2^24 − 1 的計數器，也只要幾 GB 的資料就會繞回，屆時重複的 nonce 就讓攻擊者能解密封包。

• 這種 nonce 與金鑰的結合方式有助於還原金鑰。 WEP 那三個非秘密的 nonce 位元組，讓攻擊者能判定金鑰排程演算法三次迭代後 S 的值。因此密碼分析者發現：第一個金鑰流位元組強烈依賴於第一個秘密金鑰位元組（KSA 吃進的第四個位元組），而這個偏差可以被利用來還原秘密金鑰。

利用這些弱點需要同時取得密文與金鑰流，也就是已知或選擇明文。但這夠容易了：Wi-Fi 訊框封裝帶有已知標頭的資料時就出現已知明文，攻擊者注入以目標金鑰加密的已知明文時就出現選擇明文。

結論是這些攻擊在實務中真的有效，不只是紙上談兵。

2001 年首批針對 WEP 的攻擊出現後，研究人員又找到需要更少密文的更快攻擊。今天你甚至可以找到 aircrack-ng 這類工具，實作了從網路嗅探到密碼分析的整套攻擊。

失敗案例二：TLS 中的 RC4#

TLS 是網際網路上最重要的單一安全協定。它最為人知的是支撐 HTTPS 連線，但也用於保護某些 VPN 連線、電子郵件伺服器、行動應用等等。可惜的是，TLS 長期支援 RC4。

與 WEP 不同，TLS 的實作沒有犯下「魔改 RC4 規格以使用公開 nonce」的明顯錯誤——TLS 只是餵給 RC4 一把唯一的 128 位元工作階段金鑰，所以它比 WEP 稍微沒那麼糟。

TLS 的弱點完全來自 RC4 本身不可原諒的瑕疵：統計偏差（也就是不隨機），而我們知道這對串流密碼是徹底的致命傷。

例如 RC4 產生的第二個金鑰流位元組是零的機率是 1/128，理想上應該是 1/256。

更瘋狂的是：儘管這些統計偏差自 2001 年就為人所知，多數專家竟然遲至 2013 年仍信任 RC4。

RC4 已知的統計偏差本該足以讓人徹底拋棄這個密碼，即使我們當時還不知道如何利用這些偏差來危害實際應用。在 TLS 中，RC4 的瑕疵直到 2011 年才被公開利用，但據稱 NSA 早在那之前就已成功利用 RC4 的弱點攻破 TLS 的 RC4 連線。

偏差有多廣泛？ 結果不只第二個金鑰流位元組有偏差，前 256 個位元組全都有偏差。2011 年研究人員發現，這些位元組之一為零的機率等於 1/256 + c/256²，其中常數 c 介於 0.24 到 1.34 之間。而且不只零這個值，其他位元組值也一樣。

RC4 令人驚訝之處在於：它在連許多非密碼學 PRNG 都能成功的地方失敗了——也就是產生均勻分布的偽隨機位元組（每個位元組值出現機率皆為 1/256）。

廣播模型攻擊：即使是最弱的攻擊模型也能利用 RC4 在 TLS 中的瑕疵——基本上你只要蒐集密文並尋找明文，而非金鑰。但有個前提：你需要大量密文，它們用不同的秘密金鑰把同一段明文加密了好幾次。這個攻擊模型有時稱為廣播模型，因為它類似於把同一則訊息廣播給多個收件者。

假設你想在攔截到同一則訊息的許多不同密文之後，解出明文位元組 P₁：

C₁² = P₁ ⊕ KS₁²
C₁³ = P₁ ⊕ KS₁³
C₁⁴ = P₁ ⊕ KS₁⁴

由於 RC4 的偏差，金鑰流位元組 KS₁ⁱ 是零的機率高於其他任何位元組值。因此 C₁ⁱ 等於 P₁ 的機率高於等於其他任何值。要從這些 C₁ⁱ 判定 P₁，你只要數每個位元組值出現的次數，把最頻繁的那個當成 P₁。

但因為統計偏差非常小，你需要數百萬個值才能有把握地猜對。

這個攻擊可推廣到還原多個明文位元組、以及利用多個有偏值（不只是零），演算法只是變得複雜些。然而實務上它難以執行，因為它需要蒐集大量「用不同金鑰加密同一段明文」的密文——你得誘使伺服器把同一段明文加密給許多不同收件者，或用不同金鑰對同一收件者加密許多次。

Salsa20#

Salsa20 是一個簡單、為現代 CPU 最佳化的軟體導向密碼，連同它的變體 ChaCha，已被實作在無數協定與函式庫中。設計者是備受敬重的密碼學家 Daniel J. Bernstein，他於 2005 年把 Salsa20 提交給 eSTREAM 競賽，並在 eSTREAM 的軟體組合中贏得一席之地。它的簡潔與速度讓它深受開發者歡迎。

整體架構#

Salsa20 是計數器式串流密碼——它藉由反覆處理一個每區塊遞增的計數器來產生金鑰流。

Salsa20 的核心演算法用金鑰 K、nonce N 與計數器值 Ctr 變換一個 512 位元的區塊，接著把結果加回該區塊的原始值，產生一個金鑰流區塊。

為什麼要有最後那個加法？

若演算法直接把核心的置換當輸出回傳，Salsa20 會完全不安全，因為那個置換可以被反轉。最後加上初始秘密狀態 K ‖ N ‖ Ctr，讓「金鑰到金鑰流區塊」的變換變成不可逆。

四分之一輪函式（QR）#

Salsa20 的核心置換使用一個稱為 quarter-round（QR） 的函式來變換四個 32 位元字 a, b, c, d：

b = b ⊕ ((a + d) <<< 7)
c = c ⊕ ((b + a) <<< 9)
d = d ⊕ ((c + b) <<< 13)
a = a ⊕ ((d + c) <<< 18)

這四行由上而下依序計算——b 的新值依賴 a 與 d，c 的新值依賴 a 與 b 的新值（因而也依賴 d），依此類推。

<<< 是字級的左旋轉，旋轉位元數可以是 1 到 31 之間任何值（對 32 位元字而言）：

0x01234567 <<< 8  = 0x23456701
0x01234567 <<< 16 = 0x45670123
0x01234567 <<< 22 = 0x59c048d1

512 位元狀態的變換#

Salsa20 的核心置換變換一個視為 4×4、每格 32 位元字的 512 位元內部狀態。初始狀態由以下組成：

• 八個字（256 位元）的金鑰
• 兩個字（64 位元）的 nonce
• 兩個字（64 位元）的計數器
• 四個字（128 位元）的固定常數，對每次加解密與所有區塊都相同

變換流程：先對四個欄各自獨立套用 QR（column-round），再對四個列各自獨立套用（row-round）。

column-round:            row-round:
QR(x0,  x4,  x8,  x12)   QR(x0,  x1,  x2,  x3)
QR(x1,  x5,  x9,  x13)   QR(x5,  x6,  x7,  x4)
QR(x2,  x6,  x10, x14)   QR(x10, x11, x8,  x9)
QR(x3,  x7,  x11, x15)   QR(x15, x12, x13, x14)

注意在 column-round 中，每個 QR 接收的 xᵢ 引數是由上到下排列的；而 row-round 的 QR 則以對角線上的字作為第一個引數，而非第一欄的字。

「column-round → row-round」這個序列稱為一個 double-round。

Salsa20 重複 10 個 double-round，總共 20 輪——這就是 Salsa20 名字裡 20 的由來。

實際觀察#

以全零金鑰（00 位元組）與全一 nonce（ff 位元組）初始化時，第一與第二個區塊的初始狀態只差一個位元（計數器）：

第一區塊                                第二區塊
61707865 00000000 00000000 00000000    61707865 00000000 00000000 00000000
00000000 3320646e ffffffff ffffffff    00000000 3320646e ffffffff ffffffff
00000000 00000000 79622d32 00000000    00000001 00000000 79622d32 00000000
00000000 00000000 00000000 6b206574    00000000 00000000 00000000 6b206574

但僅僅一個位元之差，經過 10 個 double-round 後，兩者的內部狀態已經完全不同：

e98680bc f730ba7a 38663ce0 5f376d93    1ba4d492 c14270c3 9fb05306 ff808c64
85683b75 a56ca873 26501592 64144b6d    b49a4100 f5d8fbbd 614234a0 e20663d1
6dcb46fd 58178f93 8cf54cfe cfdc27d7    12e1e116 6a61bc8f 86f01bcb 2efead4a
68bbe09e 17b403a1 38aa1f27 54323fe0    77775a13 d17b99d5 eb773f5b 2c3a5e7d

但要記得：即使金鑰流區塊中的字值看起來很隨機，這遠遠不是安全的保證。RC4 的輸出也看起來隨機，卻有明顯的偏差。

所幸 Salsa20 比 RC4 安全得多，而且沒有統計偏差。

00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000001 00000000 00000000 00000000
00000000 00000000 00000000 00000000

80040003 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000001 00000000 00000000 00000000
00002000 00000000 00000000 00000000

9ed7eb7f 060002c0 18028b0c 57ca83c0
00000000 00000000 00000000 00000000
00000001 0000e000 801c0006 00000000
00002000 00040000 04000008 0060f300

3ab3c25d 9f40a5c9 10070e30 07bd03c0
db1ee2ce 43ee9401 21a7022c 348fd800
403c1e72 00034003 4dc843be 700b8857
5625b75b 099c00e0 06000348 23f712d4

d93bed6d a267bf47 760c2f9f 4a41d54b
0e03d792 7340e010 119e6aa0 e90186af
7fa9617e b6aca0d7 4f6e9a4a 564b34fd
98be796d 644908d3 4897f7ca a684a2df

延伸：對 Salsa20/8 的攻擊

Salsa20 預設做 20 輪，但有時為了加快只用 12 輪，稱為 Salsa20/12。儘管少了八輪，Salsa20/12 仍顯著強於較弱的 Salsa20/8（八輪版本，較少使用）。

由於使用 256 位元金鑰，破解 Salsa20 理想上應該要 2^256 次運算。若能以少於 2^256 次運算還原金鑰，該密碼理論上就被破解了——Salsa20/8 正是如此。

針對 Salsa20/8 的攻擊（發表於 2008 年論文〈New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba〉，本書作者為共同作者之一，並因此獲得 Daniel J. Bernstein 頒發的密碼分析獎）利用 Salsa 核心演算法在四輪後的統計偏差，來還原八輪 Salsa20 的金鑰。

實際上這主要是理論性的攻擊：我們估計其複雜度為核心函式的 2^251 次運算——不可能達成，但比預期的 2^256 複雜度低。

攻擊原理：它不只利用 Salsa20/8 前四輪的偏差，也利用後四輪的一個性質——已知 nonce N 與計數器 Ctr 時，把計算從金鑰流反推回初始狀態所需的唯一值就是金鑰 K。

但若你只知道 K 的一部分，你可以把計算部分反推到第四輪，並觀察該中間狀態的某些位元——包括那個有偏差的位元。只有在你對部分金鑰的猜測正確時才會觀察到該偏差，因此偏差就成為「猜對金鑰」的指標。

在實際的 Salsa20/8 攻擊中，我們需要猜金鑰的 220 個位元，並需要 2^31 對金鑰流區塊（全都在 nonce 上具有相同的特定差異）。一旦挑出正確的 220 個位元，剩下只要暴力破解 36 個位元。暴力破解花 2^36 次運算，相較於完成第一部分所需的 2^220 × 2^31 = 2^251 次不切實際的試驗，這點計算量微不足道。