Page 214 - 《软件学报》2021年第9期

2838 Journal of Software 软件学报 Vol.32, No.9, September 2021

积分分析是一种选择明文攻击,早期主要应用于基于字节设计的密码算法.2008 年,Z’aba 等人对早期的积
[5]
[7]
[6]
[8]
分分析进行扩展,首次提出了基于比特的积分分析 ,并应用于 Noekeon ,Serpent 和 PRESENT 算法.为更加
[9]
充分地利用非线性组件信息,Todo 在 EUROCRYPT 2015 上提出了可分性 理论,该理论利用计算机搜索更长轮
数的积分区分器.接着,Todo 等人 [10] 在 FSE 2016 上将可分性概念应用到基于比特的分组密码,并对 SIMON 算法
积分区分器进行搜索.进一步,在 ASIACRYPT 2016 上,向泽军等人 [11] 首次利用混合整数线性规划(mixed-
integer linear programming,简称 MILP)模型对可分性进行刻画,针对 6 种轻量级分组密码积分区分器进行搜索,
得到了更优的结果.
积分分析也可以看成是差分分析的扩展,其与高阶差分分析在建立区分器上具有某些联系.如果在高阶差
分中考虑异或差分,那么建立具有零和性质的 d 阶积分区分器与密文某些比特代数次数最大为 d−1 是等价的.
2013 年,吴生宝等人 [12] 首次利用高阶差分分析理论,结合 S 盒具体的代数性质,构造算法新的积分区分器.针对
PRESENT 算法,他们利用 S 盒及线性层的性质,改进了原有的积分攻击结果.
在传统的积分分析中,利用一组选择明文来构造积分区分器时,区分器末端得到的密文异或和为零都是以
概率为 1 成立的.那么,能否构造概率不为 1 的有效积分区分器呢?在文献[13]中,Knudsen 等人指出:“与差分类
似,积分也可以是有概率的.”这揭示了概率积分存在的可能性.本文对该问题进行深入研究,考虑常数对布尔函
数首项系数的影响,阐述了构造概率积分区分器的具体方法,并给出了利用概率积分区分器恢复密钥的理论模
型.为验证概率积分分析方法的有效性,本文以 PUFFIN 算法为例进行分析,构造了 7 轮概率积分区分器,并利用
构造的概率积分区分器,对 9 轮 PUFFIN 算法进行密钥恢复攻击.

1 概率积分分析方法
本节从传统的积分分析出发,提出概率积分区分器的构造以及概率积分分析方法.

1.1 积分分析
n
令 f 为 F 到F 2 的 n 元布尔函数,其代数正规型可以表示为
2
f (, ,...,x x 2 x n ) = a I ⎜ ∑ ⎛ x = i ⎟∏ ⎞ ∑ a x I .
1
I
∈
∈
∈
IP ()N ⎝ iI ⎠ I P ()N
这里,N={1,2,…,n},P(N)表示 N 的幂集,即 N 的所有子集构成的集合.加法为F 2 中的加法运算,即模 2 加运算.
非零布尔函数 f 的代数正规型中,系数非零项所含有最多变元的个数称为 f 的代数次数,记为 deg(f),即:
deg(f)=max{|I||a I ≠0,I∈P(N)}.
规定:零函数的代数次数为 0.
在积分分析中,通过判定某个位置的平衡性来构造积分区分器.基于高阶差分思想,可以通过有限域上多项
式函数的首项系数取值来判定某个位置的平衡性.
引理 1 [14] . 设 f 为 n 元布尔函数,其代数正规型为
fx 1 2 x n ) = a x I ,a ∈ ∑ I F 2 ,
(, ,...,x
I
∈
()
IP N
则对任意 I∈P(N),均有:
a I = ∑ f (),x
( )⊆F
x ∈ n ,supp x I
2
其中,supp(x)={1≤i≤n|x i =1}.
引理 1 说明:要确定某个位置密文是否平衡,可通过研究该位置密文与明文之间多项式函数的首项系数来
s
判断.设算法分组长度为 n,其中的 s 个比特遍历{0,1} ,记作 x 0 ,x 1 ,…,x s−1 ;其余比特为常数,记作 c 0 ,c 1 ,…,c n−s−1 ,
0<s≤n.密文每个比特的值都是关于 x 0 ,x 1 ,…,x s−1 ,c 0 ,c 1 ,…,c n−s−1 的多项式函数,不妨记作 f(x 0 ,x 1 ,…,x s−1 ,c 0 ,c 1 ,…,
s
c n−s−1 ),易知,f 是从 F 到F 2 的一个映射.若密文某个比特位置的表达式 f 对任意的 c 0 ,c 1 ,…,c n−s−1 都满足:
2