Salsa20

Salsa20

Salsa的quarter-round函數，每四組形成一輪。
概述
設計者	丹尼爾·J·伯恩斯坦
首次發布	2007年（2005年設計）
繼承算法	ChaCha
相關算法	Rumba20
認證	eSTREAM密碼組合
密碼細節
密鑰長度	128或256位
狀態長度	512位
結構	ARX
重複回數	20
速度	3.91 cpb於Intel Core 2 Duo
最佳公開破解
2008年的密碼分析中，在2251次操作中利用231對密鑰流，嘗試恢復256位的密鑰，破解了20輪中的8輪 。

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

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

結構

在其內部，該算法採用模加⊕（邏輯異或），32位模加2³² ⊞，和在一個內部十六個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。

更精確的規範已在下方呈現為偽代碼，儘管這種行/列模式更難看出⊞是模加2³²，<<<是左旋操作，及⊕是異或。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的攻擊，預計時間複雜度2¹⁶⁵，並贏得Bernstein的1000美金 「最有趣Salsa20密碼分析」獎勵。此次攻擊及所有後續的攻擊都是基於截斷差分分析。在2006年，Fischer、Meier、Berbain、Biasse和Robshaw報告了一個對Salsa20/6的攻擊，預計時間複雜度2¹⁷⁷，以及一個對Salsa20/7的相關密鑰攻擊，預計時間複雜度2²¹⁷。

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

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

在2012年，Aumasson 等人的攻擊使Shi 等人將Salsa20/7（128位密鑰，時間複雜度2¹⁰⁹）改進為Salsa20/8（256位密鑰，時間複雜度2²⁵⁰）。

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

ChaCha變種

ChaCha

The ChaCha quarter-round function. Four parallel copies make a round.
概述
設計者	丹尼爾·J·伯恩斯坦
首次發布	2008
衍生自	Salsa20
相關算法	Rumba20
密碼細節
密鑰長度	128或256位
狀態長度	512 bits
結構	ARX
重複回數	20
速度	3.95 cpb on an Intel Core 2 Duo

在2008年，丹尼爾·J·伯恩斯坦發布了一個密切相關的「ChaCha」密碼家族，其目的是增加每一輪的擴散以實現相同或稍微提升的性能。 Aumasson et al. paper也攻擊過ChaCha，實現了少一輪循環：256位ChaCha6有複雜性2¹³⁹，ChaCha7有複雜性2²⁴⁸。128位ChaCha6在2¹⁰⁷以內，但據稱攻擊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（頁面存檔備份，存於網際網路檔案館）