PROFILPELAJAR.COM

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

Salsa20
	Salsa的quarter-round函数，每四组形成一轮。
概述
设计者	丹尼尔·J·伯恩斯坦
首次发布	2007年（2005年设计）
继承算法	ChaCha
相关算法	Rumba20
认证	eSTREAM（英语：eSTREAM）密码组合
密码细节
密钥长度	128或256位
状态长度	512位
结构	ARX
重复回数	20
速度	3.91 cpb（英语：每字节周期）于Intel Core 2 Duo
最佳公开破解
	2008年的密码分析中，在2251次操作中利用231对密钥流，尝试恢复256位的密钥，破解了20轮中的8轮。

Salsa20是一种流加密算法，由丹尼尔·J·伯恩斯坦提交到eSTREAM（英语：eSTREAM）。它建立在基于add-rotate-xor（ARX）操作的伪随机函数之上——32位模加、异或（XOR）和循环移位操作。Salsa20映射一个256位密钥、一个64位nonce以及一个64位流位置到一个512位的输出（也存在一个128位密钥的版本）。这使Salsa20具有了不同寻常的优势，用户可以在恒定时间内寻求输出流中的任何位置。它可以在现代x86处理器中提供约每4–14次循环周期一字节的速度^[4]，并具有合理的硬件性能。它没有注册专利，并且Bernstein还撰写了几篇对常见架构优化的公有领域实现。^[5]

一个相关的密码算法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字节输出块。^[6]但是，使用8轮和12轮的缩减循环的变体Salsa20/8和Salsa20/12也已分别被引入。这些变体被引入以补充原有的Salsa20，但不是取代它，甚至在eSTREAM的基准测量中比Salsa20表现更好^[quantify]，尽管它相应有着较低的安全余量。

eSTREAM选用

Salsa20已被选择作为eSTREAM项目“Profile 1”（软件）的第三阶段设计，其在第二阶段结束时得到了Profile 1中算法中的最高投票得分。^[7] Salsa20先前被选择为Profile 1（软件）的第二阶段设计重点，并作为eSTREAM项目Profile 2（硬件）的第二阶段，^[8]但最终没有晋级到“Profile 2”的第三阶段，因为eSTREAM觉得这对于极其资源受限的硬件环境可能不是一个好的候选。^[9]

密码分析

截至2015年，没有已知的对Salsa20/12或完整Salsa20/20的攻击被发布；已知的最佳攻击^[3]是打破12轮或20轮循环中的8轮。

在2005年，Paul Crowley报告了一个对Salsa20/5的攻击，预计时间复杂度2¹⁶⁵，并赢得Bernstein的1000美金 “最有趣Salsa20密码分析”奖励。^[10]此次攻击及所有后续的攻击都是基于截断差分分析。在2006年，Fischer、Meier、Berbain、Biasse和Robshaw报告了一个对Salsa20/6的攻击，预计时间复杂度2¹⁷⁷，以及一个对Salsa20/7的相关密钥攻击，预计时间复杂度2²¹⁷。^[11]

在2007年，Tsunoo 等人公布了一个Salsa20的密码分析，在2²⁵⁵次操作中，使用2^11.37对密钥流，打破8/20轮来恢复256位的私钥。^[12]但是，这种攻击似乎没有比蛮力攻击更好。

在2008年，Aumasson、Fischer、Khazaei、Meier和Rechberger报告了一个追对Salsa20/7的密码分析攻击，时间复杂度2¹⁵³，并且他们报告了首个对Salsa20/8用预计时间复杂度2²⁵¹的攻击。此攻击使用了对中性密钥位进行截断差分概率检测的新概念。此攻击可以打破使用128位密钥的Salsa20/7。^[3]

在2012年，Aumasson 等人的攻击使Shi 等人将Salsa20/7（128位密钥，时间复杂度2¹⁰⁹）改进为Salsa20/8（256位密钥，时间复杂度2²⁵⁰）。^[13]

在2013年，Mouha和Preneel发布了一则证明^[14]，叙述使用15轮循环的Salsa20在128位的安全差分分析。具体来说，它没有比2⁻¹³⁰更高概率的差分特征，因此差分分析会比用尽128位密钥更困难。

ChaCha变种

在2008年，丹尼尔·J·伯恩斯坦发布了一个密切相关的“ChaCha”密码家族，其目的是增加每一轮的扩散以实现相同或稍微提升的性能。^[16] Aumasson et al. paper也攻击过ChaCha，实现了少一轮循环：256位ChaCha6有复杂性2¹³⁹，ChaCha7有复杂性2²⁴⁸。128位ChaCha6在2¹⁰⁷以内，但据称攻击128位的ChaCha7失败。^[3]

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轮的两次循环允许一些优化。^[17]此外，输入格式可以被重新布置，以支持高效的SSE实现优化，这对Salsa20已被发现。相比逐行、逐列下移置换，还可以沿对角线进行。^[18]这样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次迭代。^[19]

ChaCha是BLAKE哈希算法的基础，NIST哈希算法竞争的一个入围者，并且继任者BLAKE2调整为更高的速度。它还定义了一个使用16个64位word（state的1024位）的变种，具有相应调整的循环移位常数。

ChaCha20

Google选择了伯恩斯坦设计的，带Poly1305 訊息鑑別碼的ChaCha20（即ChaCha20-Poly1305），作为OpenSSL中RC4的替代品，用以完成互联网的安全通信。^[20]Google最初实现了HTTPS (TLS/SSL)流量在Chrome浏览器（Android手机版）与Google网站之间的通信。^[21]

不久之后，Google在TLS中采用它，ChaCha20-Poly1305算法也以[email protected]成为OpenSSH中的一个新密码套件。^[22]^[23]后来，通过编译时选项避免它依赖于OpenSSL也成为可能。^[24]

ChaCha20也被用在OpenBSD^[25]和NetBSD^[26]操作系统中的arc4random随机数生成器，取代已经脆弱的RC4，在DragonFly BSD^[27]中内核的CSPRNG子程序中也是如此。^[28]^[29]

ChaCha20已经在RFC 7539中标准化。它在IKE和IPsec中的使用已在RFC 7634中标准化。在RFC 7905中，ChaCha20-Poly1305已经被加入TLS扩展标准。

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

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

另见

Speck – 美国国家安全局开发的一个add-rotate-xor密码算法
高級加密標準（AES）

参考资料

^ Daniel J. Bernstein. The Salsa20 family of stream ciphers (PDF). 2007-12-24 [2016-05-07]. （原始内容 (PDF)存档于2016-06-11）.
^ Daniel J. Bernstein. Salsa 20 speed; Salsa20 software. 2013-05-16 [2016-05-07]. （原始内容存档于2016-04-14）.
^ ^3.0 ^3.1 ^3.2 ^3.3 Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier, and Christian Rechberger. New Features of Latin Dances (PDF). 2008-03-14 [2016-05-07]. （原始内容 (PDF)存档于2016-04-13）.
^ Salsa20 home page. [2016-05-07]. （原始内容存档于2016-04-14）.
^ Speed of Salsa20. [2016-05-07]. （原始内容存档于2016-04-08）.
^ 存档副本 (PDF). [2016-05-07]. （原始内容 (PDF)存档于2016-06-11）.
^ 存档副本. [2016-05-07]. （原始内容存档于2016-07-09）.
^ 存档副本. [2016-05-07]. （原始内容存档于2016-03-03）.
^ 存档副本 (PDF). [2016-05-07]. （原始内容存档 (PDF)于2016-04-09）.
^ Paul Crowley, Truncated differential cryptanalysis of five rounds of Salsa20 （页面存档备份，存于互联网档案馆）
^ Simon Fischer, Willi Meier, Côme Berbain, Jean-Francois Biasse, Matt Robshaw, Non-Randomness in eSTREAM Candidates Salsa20 and TSC-4, Indocrypt 2006
^ Yukiyasu Tsunoo, Teruo Saito, Hiroyasu Kubo, Tomoyasu Suzaki and Hiroki Nakashima. Differential Cryptanalysis of Salsa20/8 (PDF). 2007-01-02 [2016-05-07]. （原始内容存档 (PDF)于2021-02-25）.
^ Zhenqing Shi, Bin Zhang, Dengguo Feng, Wenling Wu (2012): „Improved Key Recovery Attacks on Reduced-Round Salsa20 and ChaCha“.
^ Nicky Mouha, Bart Preneel. A Proof that the ARX Cipher Salsa20 is Secure against Diﬀerential Cryptanalysis (PDF). 2013 [2016-05-07]. （原始内容存档 (PDF)于2021-03-08）.
^ Bernstein, Daniel, ChaCha, a variant of Salsa20 (PDF), 28 January 2008 [2018-06-03], （原始内容存档 (PDF)于2018-05-02）
^ ChaCha home page. [2016-05-07]. （原始内容存档于2016-04-25）.
^ Neves, Samuel, Faster ChaCha implementations for Intel processors, 2009-10-07 [2011-02-20], （原始内容存档于2017-03-28）, two of these constants are multiples of 8; this allows for a 1 instruction rotation in Core2 and later Intel CPUs using the pshufb instruction
^ Bernstein, D. J., ChaCha, a variant of Salsa20 (pdf): 4, 2008-01-28 [2011-02-20], Document ID: 4027b5256e17b9796842e6d0f68b0b5e, （原始内容存档 (PDF)于2018-05-02）
^ ChaCha20 and Poly1305 for IETF protocols （页面存档备份，存于互联网档案馆）, Internet-Draft , Y. Nir, Check Point, A. Langley, Google Inc., November 9, 2014
^ draft-ietf-tls-chacha20-poly1305 The ChaCha20-Poly1305 AEAD Cipher for Transport Layer Security
^ Google Swaps Out Crypto Ciphers in OpenSSL （页面存档备份，存于互联网档案馆）, InfoSecurity, April 24, 2014
^ Miller, Damien. ssh/PROTOCOL.chacha20poly1305. BSD Cross Reference, OpenBSD src/usr.bin/. 2013-12-02 [2014-12-26]. （原始内容存档于2014-12-27）.
^ Murenin, Constantine A. Unknown Lamer , 编. OpenSSH Has a New Cipher — Chacha20-poly1305 — from D.J. Bernstein. Slashdot. 2013-12-11 [2014-12-26]. （原始内容存档于2021-03-09）.
^ Murenin, Constantine A. Soulskill , 编. OpenSSH No Longer Has To Depend On OpenSSL. Slashdot. 2014-04-30 [2014-12-26]. （原始内容存档于2016-06-24）.
^ deraadt (编). libc/crypt/arc4random.c. BSD Cross Reference, OpenBSD src/lib/. 2014-07-21 [2015-01-13]. （原始内容存档于2015-01-14）. ChaCha based random number generator for OpenBSD.
^ riastradh (编). libc/gen/arc4random.c. BSD Cross Reference, NetBSD src/lib/. 2014-11-16 [2015-01-13]. （原始内容存档于2015-01-14）. Legacy arc4random(3) API from OpenBSD reimplemented using the ChaCha20 PRF, with per-thread state.
^ kern/subr_csprng.c. BSD Cross Reference, DragonFly BSD src/sys/. [2015-01-13]. （原始内容存档于2015-01-14）. chacha_encrypt_bytes
^ ChaCha Usage & Deployment. [2016-05-07]. （原始内容存档于2021-02-19）.
^ arc4random - NetBSD Manual Pages. [6 January 2015]. （原始内容存档于2020-07-06）.
^ Donenfeld, Jason A. Protocol & Cryptography - WireGuard. www.wireguard.com. [2020-04-21]. （原始内容存档于2020-05-11）（英语）.

外部链接

Salsa20 首页（页面存档备份，存于互联网档案馆）
Specification（页面存档备份，存于互联网档案馆） (PDF)
Salsa20/8 and Salsa20/12（页面存档备份，存于互联网档案馆） (PDF)
eStream page on Salsa20（页面存档备份，存于互联网档案馆）
The ChaCha family of stream ciphers（页面存档备份，存于互联网档案馆）
Salsa20 Usage & Deployment（页面存档备份，存于互联网档案馆）

[sn-20071225-1] Daniel J. Bernstein. The Salsa20 family of stream ciphers (PDF). 2007-12-24 [2016-05-07]. （原始内容 (PDF)存档于2016-06-11）.

[2] Daniel J. Bernstein. Salsa 20 speed; Salsa20 software. 2013-05-16 [2016-05-07]. （原始内容存档于2016-04-14）.

[latin-3] 3.0 ^3.1 ^3.2 ^3.3 Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier, and Christian Rechberger. New Features of Latin Dances (PDF). 2008-03-14 [2016-05-07]. （原始内容 (PDF)存档于2016-04-13）.

[4] Salsa20 home page. [2016-05-07]. （原始内容存档于2016-04-14）.

[5] Speed of Salsa20. [2016-05-07]. （原始内容存档于2016-04-08）.

[6] 存档副本 (PDF). [2016-05-07]. （原始内容 (PDF)存档于2016-06-11）.

[7] 存档副本. [2016-05-07]. （原始内容存档于2016-07-09）.

[8] 存档副本. [2016-05-07]. （原始内容存档于2016-03-03）.

[9] 存档副本 (PDF). [2016-05-07]. （原始内容存档 (PDF)于2016-04-09）.

[10] Paul Crowley, Truncated differential cryptanalysis of five rounds of Salsa20 （页面存档备份，存于互联网档案馆）

[11] Simon Fischer, Willi Meier, Côme Berbain, Jean-Francois Biasse, Matt Robshaw, Non-Randomness in eSTREAM Candidates Salsa20 and TSC-4, Indocrypt 2006

[12] Yukiyasu Tsunoo, Teruo Saito, Hiroyasu Kubo, Tomoyasu Suzaki and Hiroki Nakashima. Differential Cryptanalysis of Salsa20/8 (PDF). 2007-01-02 [2016-05-07]. （原始内容存档 (PDF)于2021-02-25）.

[13] Zhenqing Shi, Bin Zhang, Dengguo Feng, Wenling Wu (2012): „Improved Key Recovery Attacks on Reduced-Round Salsa20 and ChaCha“.

[14] Nicky Mouha, Bart Preneel. A Proof that the ARX Cipher Salsa20 is Secure against Diﬀerential Cryptanalysis (PDF). 2013 [2016-05-07]. （原始内容存档 (PDF)于2021-03-08）.

[ChaCha-15] Bernstein, Daniel, ChaCha, a variant of Salsa20 (PDF), 28 January 2008 [2018-06-03], （原始内容存档 (PDF)于2018-05-02）

[16] ChaCha home page. [2016-05-07]. （原始内容存档于2016-04-25）.

[17] Neves, Samuel, Faster ChaCha implementations for Intel processors, 2009-10-07 [2011-02-20], （原始内容存档于2017-03-28）, two of these constants are multiples of 8; this allows for a 1 instruction rotation in Core2 and later Intel CPUs using the pshufb instruction

[18] Bernstein, D. J., ChaCha, a variant of Salsa20 (pdf): 4, 2008-01-28 [2011-02-20], Document ID: 4027b5256e17b9796842e6d0f68b0b5e, （原始内容存档 (PDF)于2018-05-02）

[19] ChaCha20 and Poly1305 for IETF protocols （页面存档备份，存于互联网档案馆）, Internet-Draft , Y. Nir, Check Point, A. Langley, Google Inc., November 9, 2014

[chacha20poly1305-20] raft-ietf-tls-chacha20-poly1305 The ChaCha20-Poly1305 AEAD Cipher for Transport Layer Security

[21] Google Swaps Out Crypto Ciphers in OpenSSL （页面存档备份，存于互联网档案馆）, InfoSecurity, April 24, 2014

[22] Miller, Damien. ssh/PROTOCOL.chacha20poly1305. BSD Cross Reference, OpenBSD src/usr.bin/. 2013-12-02 [2014-12-26]. （原始内容存档于2014-12-27）.

[23] Murenin, Constantine A. Unknown Lamer , 编. OpenSSH Has a New Cipher — Chacha20-poly1305 — from D.J. Bernstein. Slashdot. 2013-12-11 [2014-12-26]. （原始内容存档于2021-03-09）.

[24] Murenin, Constantine A. Soulskill , 编. OpenSSH No Longer Has To Depend On OpenSSL. Slashdot. 2014-04-30 [2014-12-26]. （原始内容存档于2016-06-24）.

[25] raadt (编). libc/crypt/arc4random.c. BSD Cross Reference, OpenBSD src/lib/. 2014-07-21 [2015-01-13]. （原始内容存档于2015-01-14）. ChaCha based random number generator for OpenBSD.

[26] riastradh (编). libc/gen/arc4random.c. BSD Cross Reference, NetBSD src/lib/. 2014-11-16 [2015-01-13]. （原始内容存档于2015-01-14）. Legacy arc4random(3) API from OpenBSD reimplemented using the ChaCha20 PRF, with per-thread state.

[27] rn/subr_csprng.c. BSD Cross Reference, DragonFly BSD src/sys/. [2015-01-13]. （原始内容存档于2015-01-14）. chacha_encrypt_bytes

[28] ChaCha Usage & Deployment. [2016-05-07]. （原始内容存档于2021-02-19）.

[29] rc4random - NetBSD Manual Pages. [6 January 2015]. （原始内容存档于2020-07-06）.

[30] Donenfeld, Jason A. Protocol & Cryptography - WireGuard. www.wireguard.com. [2020-04-21]. （原始内容存档于2020-05-11）（英语）.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

PROFILPELAJAR.COM

Salsa20

结构

eSTREAM选用

密码分析

ChaCha变种

ChaCha20

另见

参考资料

外部链接

Read other articles:

Prostitution in Costa Rica

Corbreuse

Prima Divisione 1932-1933

Shopping Centre Jepara

ليفاديا (ريثيمني)

Pembagian administratif Qatar

Синелобый амазон

Friday's Child (album)

Friedrich Spee

Urban Legend (film)

Aryabhata Award

神山前进统一机构

الهند في العصر الحديدي

Mike Ploog

Gempa Bumi Kalimantan Selatan 2024

Robert Patrick

IPhone 8

Liste de villes de Pologne

USS Growler (SSG-577)

Hoya of Guadix