轻量级与非满射S-box的分组密码算法的分析

摘要

在过去的几十年里，由于计算机技术的蓬勃发展给通信安全带来了巨大的挑战和机遇，密码学在信息安全领域的作用日趋显著。在当今密码学领域，分组密码，作为对称密码算法的一种，是一种基础密码算法，其结构也常常被用来构造流密码，哈希函数以及消息认证码。分组密码的加密过程是一个由唯一密钥来决定的置换过程，它先把消息分为等长分组，然后在密钥的作用下转换为等长的密文块。分组密码被广泛应用于如SSL，IPsec等各种安全协议和安全类应用程序。直到现在，分组密码的设计与安全性评估一直是研究的热点。
　　 分组密码算法DES是由IBM公司设计，并在1977年被提名为第一个分组密码加密标准。它密钥长度为56比特，分组长度64比特。整个加密过程是Feistel结构，由一个初始变换，16个迭代轮函数和一个逆变换组成。在此之后，出现了很多Feistel结构的分组密码，比如分组密码CAMELLIA[1]，CAST-128[2]，ICE[4]，LOKI97[5]，LUCIFER[6]。与此同时，一系列的分析方法也正在展开，比如差分分析，线性分析，代数攻击等。因为56比特的密钥空间已经不足以保证DES算法的安全性，1997年，美国国家标准与技术研究所(NIST)开始征集高级加密标准(AES)。2000年由JoanDaemen和VincentRijmen设计的分组密码算法Rijndael被提名为新的高级加密标准(AES)，并在一年后由NIST发布于FIPSPUB197。AES是SPN结构的，这种结构比起Feistel结构实现的效率更高，这是因为为达到同样程度的混乱和扩散，SPN结构相对于Feistel结构更易于并行化。
　　 S盒在分组密码的设计中起着至关重要的作用。S盒是一个布尔函数映射{0，1}m→{0，1}n，它的非线性影响着分组密码的混乱特性。为了抵抗差分分析，有些分组密码如CAST-128[2]，CAST-256[3]，Blowfish[21]等的S盒采用输出比特大于输入比特的设计特点。对于一个输入比特为m，输出比特为n的S盒，也可以实现为一个2m个元素的表。如果n大于m，那么S盒为非满射。线性分析是一种已知明文攻击或者唯密文攻击，由Matsui在1993年提出[26]。因此在设计能抵抗线性分析的大S盒时，常常采用bent函数，这种函数的非线性度能够达到上界2m-1-2m/2-1。在线性分析中，能找到非满射大S盒的输入掩码为0，输出掩码为非0的线性近似表达式是很有用的。然而，遍历S盒所有元素和所有输出掩码往往是非常耗时的。在针对采用非满射大S盒的分组密码的线性分析中，由于计算时间的限制，以有的工作只是搜索了部分线性近似表达式，没有达到全部搜索的目的。
　　 比如，在分组密码算法CAST-128和CAST-256中，有三种轮函数F1，F2，F3，每种都由4个8×32的非满射S盒通过模加、模减和异或的混合运算构成，这导致无法构建S盒的线性分布表。由于CAST的Feistel结构，为了控制每轮的偏差，分析者对0→Γ的线性近似表达式进行了搜索。在[63]中，Nakahara等考虑到模加模减运算会产生借位，因此只考虑了轮函数F1，F2，F3的最优线性近似表达式是00000000x→00000001x，其偏差是2-17，利用它构造了两轮迭代线性近似表达式进而给出了12轮CAST-256的分析结果，需要2101个明文，2101次12轮CAST-256加密。但随后王美琴等在[14]的对CAST-128和CAST256的线性分析中[14]指出进位和借位不总是降低偏差，由于计算时间的限制，他们搜索了轮函数F1和F3的输出掩码的汉明重量不大于3的线性近似表达式;对于轮函数F2，搜索了输出掩码的汉明重量不大于6的线性近似表达式，最后利用F2的最优线性近似表达式00000000x→03400000x，偏差为2-12.91，给出了24轮CAST-256的分析结果，需要2124.1个明文，2156.2次24轮CAST-256加密。然而，轮函数F1，F2，F3的输出比特数为32。所以还有大量的线性近似表达式的偏差没有被计算。是否存在偏差更高的线性近似表达式是未知的。
　　 本文中，我们提出一种针对非满射大S盒(32×32)的所有线性近似表达式(0→Γ)实际可行的搜索方法。该算法充分利用了64位高性能并行计算机的硬件特性，能够分析任何具有非满射大S盒的分组密码算法。为了清晰的描述我们的算法，我们以CAST-256为例。我们找到了比王美琴等找到的最好线性近似表达式更好的线性近似表达式。我们主要描述了对于CAST-256中的轮函数F2的搜索过程。在我们的并行环境里(64颗CPU核，主频2.4GHZ，3MB二级缓存，型号IBMX3950M2)，搜索完所有232个线性近似表达式用时85.3个小时。这里需要提及的一点是我们的工作不只是并行化实现，而是充分利用了硬件的特性来显著降低计算时间。如果没有我们的改进，即便采用并行化，这个搜索过程在我们的并行环境下，也将在256天才能完成。我们得到了CAST-256的轮函数F2的最好线性近似表达式00000000x→8021c53ax，偏差为2-12.63，比已有的最优偏差2-12.91更优。而且我们给出一个通用的针对非满射大S盒的线性近似表达式(0→Γ)搜索方法，利用该方法在我们的并行环境下可以在47.72小时内搜索完CAST-256算法的任一轮函数F1，F2，F3的所有线性近似表达式(0→Γ)。
　　 在最近几年里，由于因特网的迅猛发展，越来越多的微型终端设备被普遍使用，它们可以提供快捷的计算与通信，比如射频标签和传感器网络。然而，广受欢迎的密码算法AES并不能完全适合这种低耗能和计算资源有限的环境。所以最近几年国际密码领域设计了很多轻量级分组密码被设计出来满足这种资源受限的环境的安全需求，比如分组算法DESL[7],mCRYPTON[8],HEIGHT[9],ICEBERG[10],PRESENT[11],PUFFIN[12]等。
　　 PUFFIN是一种轻量级分组密码，由Cheng，Heys和Wang在DSD2008上发表。它是一种32轮SPN结构的分组密码，分组长度为64比特，密钥长度为128比特。和ICEBERG一样，PUFFIN也是一种自反的SPN结构的算法，这使得它能在硬件要求低的环境下使用。在CCECE2009上，Wang和Heys又提出了分组密码算法PUFFIN2[13]，该算法结构与PUFFIN相似，只是轮数为34轮，密钥生成算法略有不同。
　　 PUFFIN原文中提出31轮PUFFIN差分特征的概率小于2-62。Cheng等声称利用这一差分特征，需要262个选择明文对才能破解，这种攻击的数据复杂度接近于字典攻击。但是，PUFFIN的密钥长度为128比特，分组长度是64比特。Cheng等认为对于一个理想的加密算法，即使利用整个数据空间也无法恢复密钥。因此Cheng等声称32轮PUFFIN可以抵抗差分攻击[12]。然而，如果一个攻击能够利用整个数据空间恢复密钥，时间复杂度低于穷搜，那么这种攻击就是有效的。在本文中，我们利用整个数据空间对32轮PUFFIN进行差分分析，进而恢复128比特密钥。同时，我们利用28轮的线性近似表达式恢复128比特的密钥。其数据复杂度为262个明文，计算复杂度为293.7次32轮加密。另外，我们的攻击结果也适用于32轮PUFFIN2。
　　 差分分析是分组密码算法的一种经典攻击方法[24，25]，由Biham和Shamir相继发现[24]，是一种选择明文攻击，它能够恢复出迭代分组密码的密钥。它通过在迭代密码算法中存在的高概率差分特征来作为与随机置换的区分器。抵抗差分分析已经成为分组密码算法设计的安全准则。代数攻击也是分组密码算法的一种通用的攻击类型，它被广泛应用于分析流密码[28,29]，多变元密码系统[30]和一些分组密码算法[31-35]。代数攻击的基本思想是将分组密码算表示为多变量多项式方程组，进而通过求解来恢复密钥。一般来说，变量越多，非线性方程越多，多项式方程组求解的时间复杂度越高，如AES的密钥恢复可以看成对一个已知明文攻击，方程组包含4000个多变元二次方程[31]，其求解复杂度至今仍然是难以估计的。然而个别密码算法导出的方程组其代数特性可能是容易解的[38，39]。如今，人们还在不断寻找更优的求解方法[36,37,40]。一般认为，稀疏的多项式方程组是容易解的。有两类方法Gr(o)bnerBasis，SATSolver可以用来求解这一类多项式方程组，如Magma，Singular，PolyBori，MiniSat2等[43-46]。PolyBori是计算Gr(o)bnerBasis的工具，MiniSat2是一种快速的SATSolver。如果分组密码算法的多项式方程组可以被求解，那么只需要很少的明密文对便可以恢复密钥。
　　 然而，由于多项式方程组的求解时间难以估计，对于分组密码的代数攻击的可行性至今是未知的。近年来，差分分析与代数分析的组合成为人们关注的分析方法。在FSE2009上，Albrecht等提出了一种新型的攻击方法，差分代数攻击[47]。他们提出了三种攻击方法，命名为攻击A，攻击B和攻击C。他们认为攻击A的计算复杂度是难以估计的;攻击B和攻击C的目标是过滤掉不满足差分特征或者差分的错误对，进而识别正确对以恢复密钥。最后给出了对16轮PRESENT-80，17，18，19轮PRESENT-128的攻击。在本文中，我们指出攻击B和攻击C并不适用于PRESENT算法，因为它们不能过滤掉大多数满足密文差分的错误对。而且，我们解释了攻击C是不适用于一般的分组密码算法。其次，我们利用PolyBori和MiniSat2对PRESENT算法执行差分代数攻击，验证其是无效的。在此基础上，我们提出了两种新的差分代数攻击:固定部分密钥比特和多向量的差分代数攻击。基于第一个方法，我们可以攻击16轮PRESENT-80，这需要263个选择明文，最差时间复杂度是279.4次加密。虽然攻击的时间复杂度分析结果更高，但数据复杂度有所降低。
　　 本论文中，我们首先给出了非满射大S盒的线性近似表达式的搜索方法，对32轮PUFFIN进行了差分分析和线性分析，并对Albrecht等在FSE2009上提出的差分代数攻击技术进行了研究。其中差分代数攻击技术的研究内容，主要思想和证明由王美琴老师完成，本文作者负责大批量试验数据测试。具体来讲，本文主要贡献分为以下三个方面:
　　 (1)对非满射大S盒的线性近似表达式的搜索算法
　　 利用硬件特性进行改进
　　 我们将计数器累加操作并行处理分给64个子进程，父进程负责计算偏差。为了降低计数器带来的巨大内存需求，我们重复利用有限的计数器来计算更多不同输出掩码的线性近似表达式的偏差。我们还利用64位寄存器一次内存读获取S盒中的两个元素。
　　 Dot_Multiply运算的优化
　　 受对分查找思想[67]的启发，我们把Dot_Multiply运算从32次异或运算，33次与运算，31次右移运算减少到6次异或运算，8次与运算，6次右移运算。
　　 S盒重排序和累加运算的优化
　　 这里我们以CAST-256的轮函数F2为例。因为输入掩码始终是0，所以S盒中元素的顺序不影响偏差的计算。因此我们把非满射大S盒中的元素进行了重新排序，重新排序后的S盒包含64个新的组，在每一组里都有40000x个元素，然后将每一组分配给一个子进程。
　　 每一组最多由B1，B2和B3三种块组成，其中在B1或B2中，所有元素的6比特最低有效位相同。每一个子进程都会用不同的方式去处理不同类型的块。这样我们可以在对64个连续的输出掩码的计数器累加操作中，只进行最多2次Dot_Multiply运算，并且仅需要操作2个计数器。
　　 最后，在对CAST-256的轮函数F2的最优线性近似表达式的搜索算法基础上，我们给出了对非满射大S盒的线性近似表达式更有效的通用搜索算法。利用这个通用算法，搜索CAST-256的轮函数F1或F3的线性近似表达式仅需要242.81次内存写，内存需求为228个字节，在我们的并行环境下，这实际需要47.72小时。而如果直接采用对轮函数F2的搜索算法来完成，将需要251.58次内存写，内存需求为228个字节。
　　 (2)对32轮PUFFIN的差分分析和线性分析结果
　　 我们识别了4条2轮PUFFIN的迭代差分特征，它们的概率都是2-4，每一轮都只有一个活性S盒。利用其中任一条2轮迭代差分特征，我们可以构建更多轮的差分特征。它们的概率都为2-60，我们列举了其中1条30轮PUFFIN的差分特征，如下，其中(30r→)表示30轮，(00000000x，00004000x)(30r→)(00000000x,00004000x).我们在第2轮到第31轮使用第1条差分特征。我们推出明文差分的4个比特和密文差分的4个比特要满足如下的集合。所以我们选择了264个明文，来构建260个结构，在每一个结构里都有56个明文对，它们仅在第14，22，38，55比特上可能为1。
　　 (△P55,△P38,△P22,△P14)∈{(1,1,0,0),(0,0,0,1),(0,1,0,1),(1,0,1,0),(1,0,1,1),(0,1,1,1),(1,1,1,1)},(△C48,△C46,△C18,△C0)∈{(1,0,0,1),(0,1,0,0),(1,1,0,0),(0,0,1,1),(0,1,1,1),(1,1,1,0),(1,1,1,1)}.然后我们恢复第0轮和第32轮的轮密钥。我们利用其它3条差分特征来恢复其它密钥比特。恢复128比特的密钥，共需要264个明密文对，2112次32轮加密和28个6比特计数器，成功率为99.99999999996％。
　　 要得到多轮数的线性近似表达式，我们在搜索时首先考虑2轮迭代线性近似表达式。我们最终找到了14条2轮迭代线性近似表达式，它们的偏差都是最大值2-3，其中一条如下:(0000000000000010)x(1r→)(0004000000000000)x(1r→)(0000000000000010)x.我们迭代此2轮的线性近似表达式得到28轮的线性近似表达式，它的偏差为2-29。我们在第3轮到第30轮使用这个28轮的线性近似表达式，进而恢复了32轮PUFFIN的主密钥。在密钥恢复过程中，要猜测的轮密钥比特为第0，1，2，31，32轮的轮密钥，总计41比特。从密钥生成算法看，这41个比特等价于主密钥的35个比特。因此剩下的93个比特用穷搜来恢复。因此我们用262个已知明文，293.7次32轮加密，235个64比特计数器恢复32轮PUFFN的128比特主密钥，成功率为91％。
　　 (3)Albrecht等的差分代数攻击技术的研究
　　 Albrecht等发表在FSE2009上的一篇文章里指出差分代数攻击可以用来攻击PRESENT，并给出了三种攻击方法，攻击A，攻击B，攻击C。首先，我们指出攻击C是不能过滤掉满足密文差分值的错误对的。其次，我们用PolyBori和MiniSat2证实了攻击B对于PRESENT算法的攻击也是不可行。原因是在多项式方程组中，能使得错误对较短时间产生矛盾或者使得正确对较短时间求解的约束条件太少。因此，我们给出了两种方法可以更可靠的利用正确对在有效的时间内求解出正确密钥，而且错误对不会求解出错误密钥。第一种方法是在多项式方程组中固定部分密钥比特值。另外一种是用两组以上的明密文对构建多项式方程组。
　　 基于第一种方法，我们给出了16轮PRESENT-80算法的分析结果，这需要263个选择明文，时间复杂度最多需要279.4次加密。相比于16轮PRESENT-80的差分分析，时间复杂度为262次内存访问，数据复杂度为264个明文，我们的攻击方法虽然时间复杂度略高，但数据复杂度有所降低。
　　 对于第二种方法，若攻击16轮PRESENT-80算法，时间复杂度比穷搜密钥攻击略高，我们希望这种方法可以在其它分组密码算法的分析中取得效果。

目录

声明

摘要

主要符号对照表

第一章 引言和主要结果

1．1 密码学的发展

1．2 非满射大S盒的最优线性近似表达式0→(Γ)搜索

1．3 PUFFIN算法的差分分析和线性分析

1．4 Albrecht等的差分代数攻击的研究

1．5 本文的主要结构

第二章 分组密码算法

2．1 安全的定义

2．2 分组密码的设计

2．2．1 参数长度的确定

2．2．2 设计原则

2．2．3 结构

2．3 分组密码算法的安全性分析

2．3．1 攻击类型

2．3．2 常见攻击方法

2．4 轻量级分组密码

第三章 CAST-256，PUFFIN和PRESENT的算法描述

3．1 CAST-256算法描述

3．2 PUFFIN算法描述

3．3 PRESENT算法描述

第四章 非满射大S盒的最优线性近似表达式的搜索方法

4．1 以前CAS-256的分析结果

4．2 利用硬件特性进行改进

4．2．1 利用计算特性减少计算时间

4．2．2 利用并行环境降低计算时间

4．2．3 降低内存需求

4．3 优化Dot_Multiply运算

4．4 S盒重排序

4．5 累加运算的优化

4．6 轮函数F1和F3的搜索算法

4．7 小结

第五章 32轮PUFFIN的差分分析和线性分析

5．1 30轮PUFFIN的差分特征

5．2 32轮PUFFINN的差分分析

5．3 28轮PUFFIN的线性近似表达式

5．4 32轮PUFFIN的线性分析

5．5 小结

第六章 Albrecht等的差分代数攻击技术的研究

6．1 Albrecht的差分代数攻击描述

6．1．1 攻击A

6．1．2 攻击B

6．1．3 攻击C

6．2 差分代数攻击方法的研究

6．2．1 攻击C的不适用性

6．2．2 攻击B的不适用性

6．3 新差分代数攻击

6．3．1 固定密钥比特的差分代数攻击

6．3．2 多向量的差分代数攻击

6．4 小结

第七章 结论和研究计划

参考文献

致谢

个人简历

学位论文评阅及答辩情况表