1. 引言
可分性质 [1] 是密码学者Todo在2015年欧密会上提出来的,它是积分性质的推广。即使分组密码算法具有非双射函数、比特导向结构和低次数函数,也可通过可分性质构造出有效的积分区分器,这弥补了积分性质的缺憾。
可分性质一经提出,引来无数学者的进一步研究。Bing SUN等人 [2] 证明输入集中差分元素至少有个。Sun L等人 [3] 对可分性质作了进一步的解释,引入了一种新的概念——奇偶性集合 [4] ,能够以简单的方式制定和表征任何秩序的可分性质。通过考虑奇偶校验集的更多属性来概括可分性质,从而在分组密码上构建区分器。还出现了另外一种新技术,即在独立考虑每个比特和整体考虑左半部和右半部之间实现折衷 [5] ,这实际上是时间存储复杂度和区分器精度之间的折衷。为了使用常量或子密钥传播AND和OR运算的基于比特的可分性质,Sun L等人 [6] 证明了由输入可分性质推导出已知区域总是包含在从输出可分性质派生的已知区域中。尤瑞英 [7] 研究了已有的积分区分器在密钥恢复过程中的表现,进一步分析了PRESENT、Serpent和Noekeon在积分分析下的安全性。
最初的积分攻击针对的是基于字节或字设计的分组密码。由于基于比特设计的分组密码在应用积分攻击时活跃字节的性质往往被线性变换毁坏,因此Z’aba等人在FSE2008上首次提出了基于比特的积分攻击方法 [8] 。可分性质也是在这样一个基础上推广来的。Todo等人应用基于比特的可分性质,对全轮MISTY1进行了积分特征的分析 [9] 。虽然基于比特的可分性质能找到更准确的积分特征,但它的时间复杂度和数据复杂度都很高。因此,不能将其应用于分组长度超过32的算法。
S盒是分组密码算法中的一个重要部件,本质上是一张替换表,对于给定的输入,通过查找该表能够得到相应的输出。S盒对于整个密码算法的安全性十分重要,对S盒的可分性质研究也有许多。尤其是对轻量级分组密码算法 [10] 中的S盒,如Simon家族、PRESENT等算法。可分性质的提出者Todo也做了对S盒性质的搜索,主要针对MISTY1算法,对其中的S盒及轮函数进行了可分性质分析,发现S7存在一种退化现象,这一现象有利于降低复杂度,因此对S盒的可分性质研究有实际意义。
本文针对现有分组密码算法中的S盒,首先使用基于代数次数的方法,得到S盒的一些可分性质;之后使用基于比特的可分性质分析方法,得到了更好的可分性质结果。最后对两种方法的实验结果进行了分析比较,轻量级4比特S盒具有可以使用的可分性质。基于有限域逆的8比特S盒没有平衡比特因而具有高安全性。S盒具有的不平衡比特越多,安全性就越高。
2. 相关知识
2.1. 符号说明
:表示
上求和运算。对于任意
,第i个元素表示为
,汉明重量
,计算公式
。
子集
:对于任意的整数
,设
是
的一个子集,它是满足
的所有
的集合,定义如下:
。
比特产生函数
:
,
。
在计算可分性质时,为了区分输入数据集与输出数据集,其比特产生函数的自变量分别用u和v表示,即输出数据集比特产生函数记为
。
2.2. 可分性质定义
设X是一个多重数据集,元素取值于
,k取值范围是0到n。当数据集X有可分性质
时,满足如下条件:当
时,对于所有的
,
总是偶的;当
时,
的奇偶性则是未知的。
即当数据集X有可分性质
时,对于所有的
,它满足
。对任意的
,对所有
,
奇偶性都是未知的。也就是说,在可分性质中,u的集合被划分为两个子集,一个子集
奇偶性未知,另一个子集
是0。
可分性质传播规则:设S是一个n比特到n比特的函数(S盒),其代数次数为d。假设输入多重集X有可分性质
,则输出多重集Y有可分性质
,
。另外,假设S盒是排列,当输入集有可分性质
时,输出集的可分性质也是
。
3. 基于代数次数的S盒可分性质分析
3.1. 基于代数次数的分析方法定义
Todo在对MISYT1进行积分分析时,对其中的
和
进行了可分性质搜索。以
为例,其代数次数 [11] 是3,已有S盒的布尔函数
代数标准型ANF(Algebraic Normal Form)。计算复合布尔函数
的可分性质从而得到该S盒的可分性质传播特征。
的代数次数deg与V的汉明重量
对应关系如表1。

Table 1. wv-deg relationship of the7-bit S-box in MISTY1
表1. MISTY1中7比特S盒wv-deg对应关系
该S盒可分性质传播特征如表2。
这是实际传播特征。值得注意的是,根据可分性质传播规则,即
,可以得到理论值传播情况如下表3所示。

Table 2. The 7 bit S-box division property propagation characteristics
表2. S7可分性质传播特征

Table 3. The 7 bit S-box theoretical division property propagation characteristics
表3. S7理论可分性质传播特征
可发现,实际值与理论值有不同。即
理论上传播到
,但实际上传播到
,这是由于最高次项被抵消造成的。这就是此方法分析S盒可分性质的关键之处。
3.2. 基于代数次数的分析方法原理和过程
根据
的代数次数deg与v的汉明重量
之间的关系,可以推出S盒的可分性质传播特征。由可分性质的定义可知,假设输入数据集的可分性质满足
,即当
时,
是0,经复合布尔函数作用之后的输出数据集的可分性质记为
,即当
时,
是0。其中k与
的关系相对应于布尔函数
的代数次数deg与变量v的汉明重量
的对应关系。
研究可分性质传播时,猜测满足可分性质为
的最大集合,设其元素长度为n比特,令其中k个比特的值遍历(每个位置取0或1,共
种情况),其余(n − k)个比特的值固定。经验证,固定值是0或者是1对结果没有影响。取出这样的数据集X之后,根据可分性质的定义,计算该数据集的可分性质,结果证明该数据集满足可分性质,但并不能证明这是满足可分性质是
的最大数据集。
在S盒的可分性质传播中,S盒本身是一个布尔函数,可分性质计算时使用的比特产生函数
也是布尔函数,因此可将这两个布尔函数复合,即
。分析过程如下:
1) 该复合布尔函数
的汉明重量与代数次数对应关系,共n + 1种情况,这里的汉明重量指的是进行比特产生函数计算时,需要遍历的参数v的汉明重量。
2) 接下来根据此关系推导可分性质传播情况:已知输入集X有可分性质
,记输出集Y的可分性质为
。由搜索原理可分别求出与k对应的
的值,即可得到可分性质传播的实际值。
3) 利用传播规则,理论上可分性质传播得到的值为
,与实际值作比较。
另外,尝试遍历所有16!个4比特S盒。遍历过程如下:
1) 用一个递归函数
来求取0到15这16个数的排列即一个4比特S盒,结果用数组
表示;
2) 初始化一个索引与数值对应的链表
值为0到15,给定初始索引位置
为0 ,这两个赋值变量作为递归函数
的两个参数;
3) 取第一个变量
的长度
,当
时,执行下一步,否则执行步骤5);
4) 更新索引位置
,定义一个循环,当
时,将
赋值给
,为了保证
不变,将其赋值给一个新的链表
,这时移去
,调用函数本身进行递归,
和
作为参数;
5) 当
时,16个数的排列已完成,调用求S盒代数次数的函数,这样输出S盒及其代数次数。
3.3. 实验结果
主要针对已有轻量级分组密码算法中的S盒,基于代数次数做了可分性质分析。基于篇幅限制,本文举例进行结果分析。
Camellia、AES、SMS4算法中的8比特S盒,代数次数7,其结果如下表4所示。

Table 4. The 8-bit S-box division property propagation characteristics
表4. 8比特S盒可分性质传播特征
实际值与理论值一致。
研究的4比特S盒有:302个等价类,16个最优S盒G0-G15 [12] ,DES中4个,GIFT,Gost中8个,KLEIN,LED,LBlock中10个,MIBS,mCRYPTON中4个,Midori64中8个,RESENT,PRINCE,PRIDE,Piccolo,PUFFIN,RECTANGLE,SKINNY,SPONGENT,Serpent中8个,TWINE。
302个等价类中第14个:12,9,1,2,3,5,4,7,6,0,10,11,8,13,14,15,代数次数为2,其可分性质传播特征如下表5所示。

Table 5. The 14th of the 302 equivalence classes division property
表5. 302个等价类中第14类S盒的可分性质
其他的4比特S盒代数次数均为3(除了Midori64算法中有一个S盒代数次数为4),可分性质传播的实际值均与理论值一致,具体如下表6。

Table 6. Other 4-bit S-boxes division property
表6. 其余4比特S盒的可分性质
结果分析:以302个等价类中第14类S盒为例,由基于代数次数的可分性质分析结果可知,实际值与理论值有不同,理论上可分性质
经过该S盒传播到
,但实际上传播后的可分性质是
,即除了汉明重量是0的情况是平衡状态,其余均为非平衡状态。这样就会比理论扩散的慢,所以这些可分性质应用到整体算法的安全性分析中可能会相应地降低复杂度。整体来看,除了
、
两种情况传播到其本身,其余均传播到
。也就是说只有0这一个平衡状态,说明该S盒的安全性是极好的。其余大多数S盒的可分性质实际值与理论值一致。
基于代数次数的S盒可分性质分析结果显示,在算法的实际安全性分析中能够真正降低复杂度的情况较少,考虑是汉明重量掩盖造成的,因为同一个汉明重量对应多个具体的取值情况,因此,下一章在基于比特的基础上,继续挖掘更多的可分性质。
4. 基于比特的S盒可分性质分析
4.1. 基于比特的分析方法定义
定义1 基于比特的可分性质 [13]
当分析分组长度为n比特的密码算法时,传统的可分性质使用
,其中
和m是由攻击者在
范围内选定。这里考虑传统的基于比特的可分性质即
。
定义2 可分迹 [14]
设
是分组密码算法的轮函数。假设分组密码算法的输入多重数据集有初始可分性质
,记经过
函数i轮传播之后的可分性质为
。因此,有可分性质传播链:
。另外,对于
中任意向量
,一定存在一个
中的向量
,通过可分性质传播规则能够传播到
。
对于
,如果
能够传播到
,则称
为一个r轮的可分迹。
可分迹便是基于比特的一种概念,接下来使用它对S盒的可分性质进一步分析。可分迹是用来描述可分性质的传播特征的,通过检查所有可分迹的最后一个向量可估计是否存在有用的区分器。方法一中同一个汉明重量包括多种情况,因此,这里将其细化到每一种情况,期待发现比之前更好的结果。
4.2. 分析过程
符号说明:
n:S盒比特长度
k:输入值比特级表示,形如
,
:k的非平衡项集合
:k值对应的输出集
:
:K中元素
k的非平衡项是指,u遍历所有可能的2n个值,若某个u值满足
,那么此u就是k的一个非平衡项,遍历完成后即可得到k的非平衡项集合
。
取定一个k值,当u遍历的过程中,对于每一个u值,判断相应的
中是否存在非平衡项集合
中的项,先计算
。
其中
计算过程如下:
1) 遍历
,非零位置记为1,零位置记0,存为
,同理遍历
可得
。这一步是因为0的存在,本可以直接对原数组
进行遍历,索引值与数值一致。但是,若“0(0000)”这一项存在,索引却为0,检索不到,无法与后一个数组
进行运算,因此建立新数组
,来区别“0”项的存在。
2) 遍历
,对于
的每个非零项,与
中所有项做逻辑或运算,以结果为索引,值为1存入新的数组
中,注意数值采取二进制加法(如果该项出现过两次,则抵消,因为实质上项与项之间是异或运算)。
3) 遍历完成后,得到的是
结果的索引数组
,这样直接利用该
继续下一组运算。
这样
计算完毕,得到的是索引数组,要转变为值数组,主要判断“0”项是否存在。接下来,判断结果中是否包含非平衡项集合
中的项。
若
中存在非平衡项集合
中的项,此u便是输出集
中的一个元素,遍历完成后,可初步确定k值对应的输出集
。
最后需要使用SizeReduce()函数去掉冗余:对于输出集
中任一项
,若存在一个j,使得
,则
是冗余的,删去。这样就可得到该S盒输入k值时的输出集合
。
4.3. 实验结果
由于篇幅限制,本文未列出所有实验结果,下面以SKINNY算法中的S盒为例,举例进行结果分析,结果如下表7。

Table 7. Division trails of the S-box in the SKINNY
表7. SKINNY算法中S盒的可分迹
(0, 0, 0, 1)对应的结果集有3个单位向量(0, 0, 0, 1) (0, 0, 1, 0) (1, 0, 0, 0),也就是说,
这3个比特是非平衡的,而
这1个比特是平衡的;(0, 0, 1, 0)对应的结果集有3个单位向量,即第
这3个比特是非平衡的,而
这1个比特是平衡的;(0, 0, 1, 1)对应的结果集(0, 0, 0, 1) (0, 0, 1, 0) (1, 1, 0, 0),
这2个比特和
乘积项是非平衡的;(0, 1, 0, 0)对应的结果集是4个单位向量,即4个比特都是非平衡的;(1, 0, 1, 1)对应的结果集(0, 0, 1, 1) (0, 1, 1, 0) (1, 1, 0, 1),没有单位向量,即4个比特都是平衡的,这一点在S盒安全性分析时可以降低扩散的速度,更好地分析其安全性。
对于MISTY1中的7比特S盒S7,(0, 0, 0, 1, 1, 1)和(0, 0, 1, 0, 1, 1, 0) 这两个向量作为初始数据集时,结果集中不存在单位向量,即7个比特都是平衡的,而其中一些乘积项如
、
、
等等是非平衡的。
Camellia、AES、SMS4中的8比特S盒结果都是8个单位向量,即这8个比特都是非平衡的。
5. 两种分析结果对比
下面仍以SKINNY算法中的S盒为例,按第一种方法,可分性质
经过该S盒传播到
,即4个比特都是非平衡的,应包含4个单位向量;按第二种方法,汉明重量为3的共4种情况(0, 1, 1, 1),(1, 0, 1, 1),(1, 1, 0, 1),(1, 1, 1, 0)。(0, 1, 1, 1)作为初始向量,经S盒传播后得到集合(0, 0, 0, 1) (0, 1, 1, 0)(1, 1, 0, 0),即
这1个比特、
和
这两个乘积项是非平衡的;(1, 0, 1, 1)作为初始集,结果集合为(0, 0, 1, 1)(0, 1, 1, 0)(1, 1, 0, 1),不包含单位向量,4个比特都是平衡的,这称之为“退化”;(1, 1, 0, 1)作为初始集,结果集合为(0, 0, 1, 1) (1, 1, 1, 0),也是“退化”;(1, 1, 1, 0)作为初始集,经S盒传播后得到集合(0, 0, 0, 1)(0, 1, 1, 0)(1, 1, 0, 0),这种变化与第一种情况相似。又比如(0, 1, 0, 0)作为初始集,结果集是4个单位向量,这时与第一种方法相比就是没有变化的。
下表8对实验中的所有S盒进行了统计。

Table 8. Compare the results of S-boxes division property
表8. S盒可分性质分析结果对比
从S盒整体分析,比如Camellia中的8比特S盒,除了
和
,其余都是传播到
,也就是说所有比特都是非平衡的,这样的S盒安全性是比较高的。再比如302个等价类中的第14个,理论上有一个平衡比特,但是实际上却没有,此S盒的安全性也很好。但是对于MISTY1中的S7来说,
、
、
这三种情况都是传播到
,即均有一个平衡比特,那么在攻击该S盒时便可利用此平衡比特,因此该S盒的安全性便不是最高的。
6. 结论
本文使用基于代数次数、基于比特即可分迹这两种方法,对目前轻量级分组密码算法中的S盒,进行了可分性质分析。第一种方法实验结果中,可利用的可分性质不多,考虑在分析可分性质时,是用汉明重量来区分的,但是同一种汉明重量包括多种情况,很可能存在覆盖隐藏,因此将可分性质传播细化到比特级,即将长度为n的S盒的
种情况分别计算,针对每一个值,研究可能得到的可分性质。发现了确实存在覆盖现象,挖掘出更多隐藏的可利用的S盒可分性质,在对算法做整体安全性分析时,可以降低复杂度或者拓展攻击轮数。
基金项目
本文获得国家自然科学基金项目(No. 61672509、U1603116)和内蒙古自治区科技创新引导奖励资金资助项目的资助。