论文部分内容阅读
SPN结构作为一种非常重要的分组密码结构,被多个密码算法采用,最著名实例当属高级加密标准AES。而截断差分攻击和不可能差分攻击作为传统差分攻击的推广,是针对分组密码算法非常有效的两种攻击方法,针对多个分组密码算法得到了很好的攻击,甚至是全轮或接近全轮的攻击。因此,分析SPN结构密码算法抵抗这两种攻击的能力,是一个非常值得研究的问题。本文从截断差分区分器和不可能差分区分器的角度出发,主要做了以下四个方面的工作:1.提出了一种估计SPN结构截断差分路径期望差分概率的新方法准确计算/估计截断差分路径的概率,对于成功进行截断差分攻击并准确估计攻击的数据复杂度和时间复杂度至关重要。对于Markov密码,其截断差分路径关于独立均匀轮密钥的期望概率等于其内部所有具体差分路径的期望概率之和关于所有可能输入差的平均值。因此大多数情况下,很难遍历其所有内部路径以准确计算出截断差分路径的准确期望概率,估计这一概率成为更现实的选择。然而,现有方法主要将截断差分路径也像具体差分路径那样看作Markov链,通过各轮独立概率的乘积推断整个路径的期望概率。这些Markov方法要么通用但无法考虑S盒真实的差分分布,从而针对不同算法、不同路径,给出的期望概率估计值会较大偏离准确概率;要么只能考虑特定种类S盒、只适用于特定截断差分路径,而无法被广泛使用。我们从截断差分路径关于独立均匀轮密钥的期望概率计算公式出发,通过巧妙估计截断差分路径内部可能具体差分路径的数量NE和内部单条具体路径的平均期望概率PE,给出了一种估计截断差分路径期望概率的新方法。该方法克服了已有方法无法考虑S盒差分分布或仅适用于特殊截断差分路径的缺点,能够同时考虑S盒的差分分布和线性层带来的相关性,且适用于任何SPN结构密码算法的截断差分路径。作为实际应用,我们针对已有文献中用于4个SPN结构密码算法(KLEIN、Midori64、CRYPTON和ARIA)截断差分攻击的共8条截断差分路径,利用新方法重新估计了它们的期望概率:对于其中6条期望概率可准确计算出来的路径,我们的方法给出了非常接近准确概率的估计值,且精度及稳定性不低于已有的估计方法,而已有方法要么估计精度针对不同算法/路径波动较大,要么不适用;对于其中另外2条准确期望概率无法现实计算的路径,由于原有方法没有考虑其S盒的差分分布,我们相信本文方法估计的期望概率更接近其准确值(KLEIN减轮路径的准确期望概率验证了这一点)。该方法还有一个额外的用处,能够很好地估计出与这些截断差分路径匹配的具体差分路径的数量,这是现有方法所不具备的,从而为今后研究差分集聚提供了新思路。2.提出了一种证明SPN结构S盒无关不可能差分长度上界的新方法不可能差分区分器的最大长度,是衡量分组密码算法抵抗不可能差分攻击能力的一个重要指标。孙兵等人在EUROCRYPT2016上指出,特定SPN结构(P层定义在有限域上且S层的S盒数量t和S盒规模m满足t?2m-1-1)不可能差分的存在性问题可以归约到输入/输出差均只有一个活动S盒的不可能差分的存在性问题,进而可以利用P层特征矩阵的本原指数以O(t)的复杂度,非常简洁的给出这类SPN结构S盒无关的不可能差分长度上界。然而现实是,很多SPN结构密码算法并不满足他们的方法所要求的特殊条件,因而无法用他们的方法得到这些算法S盒无关的不可能差分长度上界。考察SPN结构S盒无关的不可能差分长度上界,关键在于研究P层如何将输入模式逐轮“扩张”为全非零的输出模式,以便于“中间相遇”得到上界。我们选取了一种特殊的“1-?模式”(而非传统的1-0模式),引入分块矩阵“行块秩”的概念,充分刻画了P层对输入1-?模式的扩张作用。这种扩张刻画足够充分,既适用于任意P层,又能保证任意输入模式经过尽可能少轮数的迭代扩张便得到全非零模式。同时,这种扩张还满足特殊的“保序性”,从而同样将任意不可能差分的判定问题归约到输入/输出差均只有一个活动S盒的不可能差分的判定问题。最终,该方法克服了已有方法复杂度太高或仅适用于特殊P层的不足,能够以多项式时间、给出任意SPN结构S盒无关不可能差分长度的上界,首次给出了CRYPTON、m Crypton、Minalpher-P、Midori和Skinny64的S盒无关不可能差分长度紧的上界,同时针对现有方法适用的算法也能给出同样的上确界。我们将该方法实现并封装为方便使用的C函数,便于设计者调用以分析SPN结构密码算法关于不可能差分攻击的安全性,以及独立于S盒去选择线性层以提高算法抵抗不可能差分攻击的能力。3.理论证明了AES不存在5轮以上S盒相关但密钥生成算法无关的具体不可能差分研究AES的区分器,始终是密码学界的热点和难点问题之一。王乾在其硕士论文中,首次理论证明了即使考虑S盒的细节但不考虑密钥生成算法,AES也不存在5轮以上的截断不可能差分。相较于前人不考虑S盒细节得到的界,他们的结果进一步明确了AES关于不可能差分攻击的可证明安全性。但是,他们仅通过证明AES的任何5轮截断差分内部至少有一个可能具体差分对应,去证明该截断差分为可能的。因此,AES的5轮截断差分内部的大量具体差分对应中,到底有多少是可能差分,多少是不可能差分,仍然是未知的。如果其中大量为不可能差分,则仍然可以被攻击者作为5轮不可能差分集合区分器去扩展AES不可能差分攻击的轮数。在本文中,我们通过深入研究AES的S盒及其定义在有限域GF(28)上的线性层的特殊代数特性,引入一个新的概念——“(w,d)-依赖树”,在考虑S盒差分分布但不考虑密钥生成算法的条件下,严格地理论证明了AES不存在5轮以上的具体不可能差分,更细致地明确了AES关于不可能差分攻击的可证明安全性。在将来,该证明思路有可能被推广应用于证明其它SPN结构密码算法S盒相关的不可能差分长度上界。4.找到了TASS1分组密码算法长轮数的概率为1差分路径,并构造了全轮的不可能差分区分器和差分计数区分器TASS1是2019年全国密码算法设计竞赛的第一轮候选分组密码算法,它新颖地采用了4进32/64出的“密化随机池”以期提高算法抵抗已知和未知攻击的能力。但是,我们研究发现其“密化随机池只有4比特输入且每轮只使用3次”的特征使得算法存在安全性缺陷:寻找算法长轮数概率为1差分路径的问题可以被有效地转化为求解线性方程组的问题(该方法也被李艳俊团队同时独立地发现),同时密化随机池(可被看作扩张S盒)由扩张特性引起的差分分布不均匀性经过多轮迭代后仍有保留。最终,我们找到了TASS1-128最长19轮、TASS1-256最长41轮的概率为1差分路径,从而构造了TASS1-128的40轮、TASS1-256的84轮(TASS1总共49轮)不可能差分区分器,同时构造了TASS1-256的全轮差分计数区分器,能以273的数据量、278.2的时间复杂度和280的存储复杂度,将TASS1-256与随机置换区分开来。