Salsa序列算法分析研究

刘莺迎

（河南牧业经济学院，郑州 450001）

1 引言

Salsa20算法属于序列密码算法[1]。序列密码，也称流密码，是密码学的重要分支，它利用初始密钥产生一条密钥流序列，与明文简单异或进行加密。Salsa20算法是欧洲著名密码计划eSTREAM[2]的入选算法。该计划旨在征集软件或者硬件性能优于AES的序列密码算法。Salsa20算法[3]是由美国学者Daniel J.Bernstein提出的序列密码算法。于2005年5月提交作为eSTREAM候选算法，同时提供了算法的速度，安全性分析以及设计原则介绍[4]。经过三轮的算法评估，最终Salsa20/12算法成功入选，它在软件组中排名第二，另外它支持的密钥长度为256比特或者是128比特（比较倾向于256比特）。

2 算法实现

Salsa20算法的基本处理单位为32比特字，最基本的函数为quarterround函数，采用的运算为模232的整数加法，异或和循环移位运算的复合，软件处理速度非常快。Salsa20算法的核心是输入输出都是512比特的hash函数。这512比特输入以32比特字为单位排成一个4阶方阵，初始矩阵用密钥，IV，nonce和常数值进行填充。填充后对该矩阵用quarterround函数交替进行10次列变换和10次行变换，得到的矩阵与原矩阵模232加输出密钥流序列。

3 算法混淆效果分析

通过以上对Salsa20算法结构的介绍以及实现过程，可以发现其混淆效果很好。这里通过模拟实验构造所需输入对分析一下Salsa20算法的混淆效果究竟如何。为说明Salsa20算法的混淆效果极佳，这里构造两个输入矩阵，它们只在一个字的一个比特上有差分。并在此基础上分析这一个比特在不同位置上所发生的混淆效果有什么不同。通过模拟实验结果发现，在Salsa20算法的16个字输入差分当中，仅仅有一个字存在一个非零比特，就可以使得三轮轮函数作用后此非零比特扩散到16个字的所有比特。

在这里把一次运算后两个状态在同一个位置出现的不同比特记作“活跃比特”。以上只对输入差分做了4轮Salsa20算法轮函数作用，混淆效果就已经如此巨大，接下来的16轮轮函数作用后还将有更多的活跃比特。

4 5轮Salsa20截断差分攻击

本节考虑的是Paul Crowley等简化至5轮的Salsa20的截断差分攻击及其改进[5][6]，其主要思路是：先是对n轮差分进行反向分析，得到n-2轮差分特征，然后按一定方法对密钥进行穷举，以达到密钥恢复的效果。

5 差分链的验证与计算

对于任何算法，进行差分攻击时最重要的一步就是寻找高概率差分链，这一步往往需要耗费很大的资源。根据ARX密码的模加差分概率计算方法[7]，可以对各论文中出现的3轮差分链进行理论概率计算，然后进行大数据模拟实验验证差分链的输入输出正确性和差分概率正确性。

假设三轮差分链表示为以下形式：

6 结束语

本文对Salsa20算法进行了深入探究，主要工作包括对Salsa20算法结构的介绍与分析、对算法特性的分析，对Salsa20算法的Python语言编程实现、对5轮Salsa20算法的差分攻击，以及对攻击算法复杂度的分析，最后是对现有差分链的验证和差分链概率的计算。

本文主要有以下几个重点内容：第一点是在深入分析Salsa20算法的各组成函数以及对其扩展函数和加密函数的前提下，对其进行了Python语言的编程实现以及对其安全性进行了一定的分析。第二点是对Salsa20算法进行了5轮的截断差分攻击，包括对差分链选择标准的判断、在Paul Crowley提出的关于Salsa20算法差分攻击的基础上进行了改进和优化，并且提出了具体的分析算法，同时进行了算法的复杂度分析。第三点是对现有差分链进行了有效的验证，并且对这些差分链进行了理论概率的计算，最后通过模拟实验判断了它们是否符合高概率的条件。