茶年 · 中文维基百科

Salsa20

Wikipedia · 2022-05-12 维基百科 👁 1 阅读

Salsa20是一种流加密算法，由丹尼尔·J·伯恩斯坦提交到。它建立在基于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上进行恒定距离循环移位操作（R(a,b,c,k)是
b ⊕= (a ⊞ c) 32，x ⊕= y是x = x ⊕ y的缩写。
x[ 4] ⊕= (x[ 0] ⊞ x[12])[quantify]，尽管它相应有着较低的安全余量。

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

密码分析
截至2015年，没有已知的对Salsa20/12或完整Salsa20/20的攻击被发布；已知的最佳攻击此次攻击及所有后续的攻击都是基于截断差分分析。在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。

在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失败。此外，输入格式可以被重新布置，以支持高效的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算法也以[email protected]成为OpenSSH中的一个新密码套件。后来，通过编译时选项避免它依赖于OpenSSL也成为可能。

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

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

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

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

另见

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

参考资料
外部链接

#互联网标准 #带有源代码的公共领域软件 #流密码

评论 (0)

  • 还没有评论，来抢沙发吧。