ChaCha

**Salsa20** 是一種流加密演算法，由丹尼爾・J・伯恩斯坦提交到 eSTREAM。它建立在基於 add-rotate-xor（ARX）操作的偽隨機函式之上 ——32 位元模加、互斥或（XOR）和迴圈移位元運算。Salsa20 對映一個 256 位金鑰、一個 64 位元 nonce 以及一個 64 位元流位置到一個 512 位元的輸出（也存在一個 128 位元金鑰的版本）。這使 Salsa20 具有了不同尋常的優勢，使用者可以在恆定時間內尋求輸出流中的任何位置。它可以在現代 x86 處理器中提供約每 4–14 次迴圈周期一位元組的速度，並具有合理的硬體效能。它沒有註冊專利，並且 Bernstein 還撰寫了幾篇對常見架構最佳化的公有領域實現。

一個相關的密碼演算法 **ChaCha**，具有類似的特點，但有不同的迴圈移位函式，已在 2008 年由伯恩斯坦發布。

## 結構

在其內部，該演算法採用模加⊕（邏輯互斥或），32 位元模加 232 ⊞，和在一個內部十六個 32 位元 word 的 state 上進行恆定距離迴圈移位元運算（<<<）。只使用 add-rotate-xor 操作避免了軟體實現中計時攻擊的可能性。基本的 Salsa20 迴圈函式 `R(a,b,c,k)` 是

```
b ⊕= (a ⊞ c) <<< k;
```

初始狀態是根據金鑰的 8 個 word、流位置的 2 個 word、nonce 的兩個 word（基本上是額外的流位置）和 4 個固定 word 製成。20 輪迴圈混合製成 16 個 word 的串流加密法輸出。

一個 quarter-round 會使用四個 word 的輸入並製成四個 word 的輸出。內部的 16-word 狀態被布置為一個 4x4 矩陣；偶數迴圈應用 quarter-round 操作到四行的每項，奇數迴圈應用 quarter-round 操作到四列的每項。連續兩輪迴圈（一次行迴圈和一次列迴圈）被稱為 double-round。

更精確的規範已在下方呈現為虛擬碼，儘管這種行 / 列模式更難看出⊞是模加 232，<<< 是左旋操作，及⊕是互斥或。`x ⊕= y` 是 `x = x ⊕ y` 的縮寫。

```
x[ 4] ⊕= (x[ 0] ⊞ x[12])<<<7;    x[ 9] ⊕= (x[ 5] ⊞ x[ 1])<<<7;
x[14] ⊕= (x[10] ⊞ x[ 6])<<<7;    x[ 3] ⊕= (x[15] ⊞ x[11])<<<7;
x[ 8] ⊕= (x[ 4] ⊞ x[ 0])<<<9;    x[13] ⊕= (x[ 9] ⊞ x[ 5])<<<9;
x[ 2] ⊕= (x[14] ⊞ x[10])<<<9;    x[ 7] ⊕= (x[ 3] ⊞ x[15])<<<9;
x[12] ⊕= (x[ 8] ⊞ x[ 4])<<<13;   x[ 1] ⊕= (x[13] ⊞ x[ 9])<<<13;
x[ 6] ⊕= (x[ 2] ⊞ x[14])<<<13;   x[11] ⊕= (x[ 7] ⊞ x[ 3])<<<13;
x[ 0] ⊕= (x[12] ⊞ x[ 8])<<<18;   x[ 5] ⊕= (x[ 1] ⊞ x[13])<<<18;
x[10] ⊕= (x[ 6] ⊞ x[ 2])<<<18;   x[15] ⊕= (x[11] ⊞ x[ 7])<<<18;

x[ 1] ⊕= (x[ 0] ⊞ x[ 3])<<<7;    x[ 6] ⊕= (x[ 5] ⊞ x[ 4])<<<7;
x[11] ⊕= (x[10] ⊞ x[ 9])<<<7;    x[12] ⊕= (x[15] ⊞ x[14])<<<7;
x[ 2] ⊕= (x[ 1] ⊞ x[ 0])<<<9;    x[ 7] ⊕= (x[ 6] ⊞ x[ 5])<<<9;
x[ 8] ⊕= (x[11] ⊞ x[10])<<<9;    x[13] ⊕= (x[12] ⊞ x[15])<<<9;
x[ 3] ⊕= (x[ 2] ⊞ x[ 1])<<<13;   x[ 4] ⊕= (x[ 7] ⊞ x[ 6])<<<13;
x[ 9] ⊕= (x[ 8] ⊞ x[11])<<<13;   x[14] ⊕= (x[13] ⊞ x[12])<<<13;
x[ 0] ⊕= (x[ 3] ⊞ x[ 2])<<<18;   x[ 5] ⊕= (x[ 4] ⊞ x[ 7])<<<18;
x[10] ⊕= (x[ 9] ⊞ x[ 8])<<<18;   x[15] ⊕= (x[14] ⊞ x[13])<<<18;
```

Salsa20 在其輸入上實行 20 輪混合，然後添加最終陣列到原數陣列來獲得 64 位元組輸出塊。但是，使用 8 輪和 12 輪的縮減迴圈的變體 Salsa20/8 和 Salsa20/12 也已分別被引入。這些變體被引入以補充原有的 Salsa20，但不是取代它，甚至在 eSTREAM 的基準測量中比 Salsa20 表現更好，儘管它相應有著較低的安全餘量。

## eSTREAM 選用

Salsa20 已被選擇作為 eSTREAM 專案「Profile 1」（軟體）的第三階段設計，其在第二階段結束時得到了 Profile 1 中演算法中的最高投票得分。 Salsa20 先前被選擇為 Profile 1（軟體）的第二階段設計重點，並作為 eSTREAM 專案 Profile 2（硬體）的第二階段，但最終沒有晉級到「Profile 2」的第三階段，因為 eSTREAM 覺得這對於極其資源受限的硬體環境可能不是一個好的候選。

## 密碼分析

截至 2015 年，沒有已知的對 Salsa20/12 或完整 Salsa20/20 的攻擊被發布；已知的最佳攻擊是打破 12 輪或 20 輪迴圈中的 8 輪。

在 2005 年，Paul Crowley 報告了一個對 Salsa20/5 的攻擊，預計時間複雜度 2165，並贏得 Bernstein 的 1000 美金 「最有趣 Salsa20 密碼分析」獎勵。此次攻擊及所有後續的攻擊都是基於截斷差分分析。在 2006 年，Fischer、Meier、Berbain、Biasse 和 Robshaw 報告了一個對 Salsa20/6 的攻擊，預計時間複雜度 2177，以及一個對 Salsa20/7 的相關金鑰攻擊，預計時間複雜度 2217。

在 2007 年，Tsunoo 等人公布了一個 Salsa20 的密碼分析，在 2255 次操作中，使用 211.37 對金鑰流，打破 8/20 輪來恢復 256 位的私鑰。但是，這種攻擊似乎沒有比蠻力攻擊更好。

在 2008 年，Aumasson、Fischer、Khazaei、Meier 和 Rechberger 報告了一個追對 Salsa20/7 的密碼分析攻擊，時間複雜度 2153，並且他們報告了首個對 Salsa20/8 用預計時間複雜度 2251 的攻擊。此攻擊使用了對中性金鑰位進行截斷差分概率檢測的新概念。此攻擊可以打破使用 128 位元金鑰的 Salsa20/7。

在 2012 年，Aumasson 等人的攻擊使 Shi 等人將 Salsa20/7（128 位元金鑰，時間複雜度 2109）改進為 Salsa20/8（256 位金鑰，時間複雜度 2250）。

在 2013 年，Mouha 和 Preneel 發布了一則證明，敘述使用 15 輪迴圈的 Salsa20 在 128 位元的安全差分分析。具體來說，它沒有比 2−130 更高概率的差分特徵，因此差分分析會比用盡 128 位元金鑰更困難。

## ChaCha 變種

在 2008 年，丹尼爾・J・伯恩斯坦發布了一個密切相關的「**ChaCha**」密碼家族，其目的是增加每一輪的擴散以實現相同或稍微提升的效能。 Aumasson et al. paper 也攻擊過 ChaCha，實現了少一輪迴圈：256 位 ChaCha6 有複雜性 2139，ChaCha7 有複雜性 2248。128 位元 ChaCha6 在 2107 以內，但據稱攻擊 128 位元的 ChaCha7 失敗。

ChaCha 替換了基本的 Salsa20 迴圈函式 `R(a,b,c,k)`

```
b ⊕= (a ⊞ c) <<< k;
```

修改後的計算方法：

```
b ⊞= c;
a ⊕= b;
a <<<= k;
```

迴圈移位量也被更新。一個完整的 quarter-round，`QR (a,b,c,d)` 變為：

```
a ⊞= b; d ⊕= a; d <<<= 16;
c ⊞= d; b ⊕= c; b <<<= 12;
a ⊞= b; d ⊕= a; d <<<= 8;
c ⊞= d; b ⊕= c; b <<<= 7;
```

這除了使其在雙運算元指令集（如 x86）上更有效率，也使其在每次 quarter-round 中更新每個 word 兩次。

在事實上，8 輪的兩次迴圈允許一些最佳化。此外，輸入格式可以被重新布置，以支援高效的 SSE 實現最佳化，這對 Salsa20 已被發現。相比逐行、逐列下移置換，還可以沿對角線進行。這樣 ChaCha 中的兩輪迴圈是：

```
QR (0, 4, 8, 12)
QR (1, 5, 9, 13)
QR (2, 6, 10, 14)
QR (3, 7, 11, 15)
QR (0, 5, 10, 15)
QR (1, 6, 11, 12)
QR (2, 7, 8, 13)
QR (3, 4, 9, 14)
```

其中的數字是十六個 32 位元 state word。ChaCha20 使用兩輪 10 次迭代。

ChaCha 是 BLAKE 雜湊演算法的基礎，NIST 雜湊演算法競爭的一個入圍者，並且繼任者 BLAKE2 調整為更高的速度。它還定義了一個使用 16 個 64 位元 word（state 的 1024 位元）的變種，具有相應調整的迴圈移位常數。

### ChaCha20

Google 選擇了伯恩斯坦設計的，帶 Poly1305 訊息鑑別碼的 ChaCha20（即 ChaCha20-Poly1305），作為 OpenSSL 中 RC4 的替代品，用以完成網際網路的安全通信。Google 最初實現了 HTTPS (TLS/SSL) 流量在 Chrome 瀏覽器（Android 手機版）與 Google 網站之間的通信。

不久之後，Google 在 TLS 中採用它，ChaCha20-Poly1305 演算法也以 chacha20-poly1305@openssh.com 成為 OpenSSH 中的一個新密碼套件。後來，通過編譯時選項避免它依賴於 OpenSSL 也成為可能。

ChaCha20 也被用在 OpenBSD 和 NetBSD 作業系統中的 arc4random 亂數生成器，取代已經脆弱的 RC4，在 DragonFly BSD 中核心的 CSPRNG 子程式中也是如此。

ChaCha20 已經在 RFC 7539 中標準化。它在 IKE 和 IPsec 中的使用已在 RFC 7634 中標準化。在 RFC 7905 中，ChaCha20-Poly1305 已經被加入 TLS 擴充標準。

若 CPU 或軟體不支援 AES 指令集，ChaCha20 可提供比 AES 更好的效能。

WireGuard 協定使用了帶 Poly1305 訊息鑒別碼的 ChaCha20。

## 另見

* Speck – 美國國家安全局開發的一個 add-rotate-xor 密碼演算法
* 高級加密標準（AES）

## 參考資料

## 外部連結

* Salsa20 首頁（頁面存檔備份，存於網際網路檔案館）
* Specification（頁面存檔備份，存於網際網路檔案館） (PDF)
* Salsa20/8 and Salsa20/12（頁面存檔備份，存於網際網路檔案館） (PDF)
* eStream page on Salsa20（頁面存檔備份，存於網際網路檔案館）
* The ChaCha family of stream ciphers（頁面存檔備份，存於網際網路檔案館）
* Salsa20 Usage & Deployment（頁面存檔備份，存於網際網路檔案館）