Salsa20

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

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

一个相关的密码算法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 ⊕= yx = 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的攻击,预计时间复杂度2165,并赢得Bernstein的1000美金 “最有趣Salsa20密码分析”奖励。[10]此次攻击及所有后续的攻击都是基于截断差分分析在2006年,Fischer、Meier、Berbain、Biasse和Robshaw报告了一个对Salsa20/6的攻击,预计时间复杂度2177,以及一个对Salsa20/7的相关密钥攻击,预计时间复杂度2217[11]

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

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

在2012年,Aumasson 等人的攻击使Shi 等人将Salsa20/7(128位密钥,时间复杂度2109)改进为Salsa20/8(256位密钥,时间复杂度2250)。[13]

在2013年,Mouha和Preneel发布了一则证明[14],叙述使用15轮循环的Salsa20在128位的安全差分分析。具体来说,它没有比2−130更高概率的差分特征,因此差分分析会比用尽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[15]

在2008年,丹尼尔·J·伯恩斯坦发布了一个密切相关的“ChaCha”密码家族,其目的是增加每一轮的扩散以实现相同或稍微提升的性能。[16] Aumasson et al. paper也攻击过ChaCha,实现了少一轮循环:256位ChaCha6有复杂性2139,ChaCha7有复杂性2248。128位ChaCha6在2107以内,但据称攻击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),作为OpenSSLRC4的替代品,用以完成互联网的安全通信。[20]Google最初实现了HTTPS (TLS/SSL)流量在Chrome浏览器Android手机版)与Google网站之间的通信。[21]

不久之后,Google在TLS中采用它,ChaCha20-Poly1305算法也以chacha20-poly1305@openssh.com成为OpenSSH中的一个新密码包。[22][23]后来,通过编译时选项避免它依赖于OpenSSL也成为可能。[24]

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

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

CPU软件不支持AES指令集,ChaCha20可提供比AES更好的性能。

WireGuard协议使用了带Poly1305消息鉴别码的ChaCha20[30]

另见

参考资料

  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). 
  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 Differential Cryptanalysis (PDF). 2013 [2016-05-07]. (原始内容存档 (PDF)于2021-03-08). 
  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
  20. ^ draft-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. ^ 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. 
  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. ^ kern/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. ^ arc4random - 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) (英语). 

外部链接