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

尚方舟 等:概率积分及其在 PUFFIN 算法中的应用 2841

0.5,则可得到 ˆ a ,由推论 1 得到该比特平衡概率为1 a− ˆ .若1 a ≠− ˆ I 0.5 ,则可构造一个概率积分区分器.
I
I
1.3 概率积分分析模型
传统积分攻击模型与概率积分攻击模型具有一定的相似之处,但在具体的复杂度计算上存在差异.先给出
需要用到的符号定义.
• b:平衡/概率平衡比特数;
• k:需要猜测的密钥比特数;
• p:明文集合平衡概率;
• N:实验次数.
在传统积分分析中,对于每次实验,若利用 m 组明文集合(根据区分器,每组明文均为部分位置遍历,其余位
−b m
k
置固定为常数)进行攻击,当剩余密钥量的期望值(2 −1)(2 ) <1 时,则此次攻击成功.而在概率积分分析中,m 组
−m
m
明文集合全平衡的概率为 p ,也就是在⎡p ⎤次实验中,至少有一次 m 组明文集合全平衡.而只有当每次实验的 m
组明文全平衡时,此次实验才能成功猜测正确密钥.为刻画正确密钥与错误密钥之间的区分性,本文引入显著度
−m
的概念,记为 C.若进行 N=⎡C⋅p ⎤次实验,则 m 组明文集合全平衡的次数至少为 C,这使得正确密钥与错误密钥
之间的区分更加显著.由此,概率积分分析需满足如下定理.
k
−b m
定理 1. 在概率积分分析中,若进行 N 次实验,每次实验利用 m 组明文集合进行攻击,当 N⋅2 ⋅(2 ) <1 时,此
次攻击成功.
证明:不妨设 N 次实验中,明文集合全部平衡的实验次数为 N 1 ,不全平衡的实验次数为 N 2 ,N 1 +N 2 =N.
−b m
k
在 N 1 次实验中,与传统积分分析相同,最终剩余的正确密钥量为 1,错误密钥量为(2 −1)(2 ) ;在 N 2 次实验
−b m
k
中,与随机情况相同,最终剩余的密钥量均为 2 ⋅(2 ) .因此,最终剩余的总密钥量 K 为
−b m
k
−b m
−b m
k
k
−b m
k
k
−b m
K=N 1 ⋅[1+(2 −1)⋅(2 ) ]+N 2 ⋅2 ⋅(2 ) =N 1 +N 1 ⋅(2 −1)⋅(2 ) +N 2 ⋅2 ⋅(2 ) ≈N 1 +N⋅2 ⋅(2 ) .
−b m
k
故而,当除正确密钥出现次数 N 1 外的候选密钥个数 N⋅2 ⋅(2 ) 小于 1 时,此次攻击成功.证毕. □
2 运用概率积分攻击 PUFFIN 算法
本节利用概率积分的思想,对 PUFFIN 算法抵抗积分攻击的安全性进行分析.首先,针对 PUFFIN 算法构造 6
轮概率积分区分器;接着,利用高阶积分理论,将 6 轮区分器扩展为 7 轮概率积分区分器,并对 9 轮 PUFFIN 算法
进行攻击.
2.1 PUFFIN算法描述
PUFFIN [15] 算法是一种硬件实现良好的轻量级 SPN 结构算法,分组规模为 64 比特,密钥规模为 128 比特,
轮数为 32 轮.算法的 64 比特明文(中间状态、轮密钥及密文)排列为 4 行 16 列的二维数组形式,即(p 0 ,p 1 ,…,p 63 )
T
可表示成 V 0 ,V 1 ,…,V 15 共 16 个向量,其中,V i =(p 4i ,p 4i+1 ,p 4i+2 ,p 4i+3 ) ,0≤i≤15,如图 1 所示.
0 V 1 V V 2 3 V V 4 5 V 6 V 7 V 8 V 9 V V 10 V 11 V 12 V 13 V 14 V 15
0 p 4 p 8 p p 12 p 16 p 20 p 24 p 28 p 32 p 36 p 40 p 44 p 48 p 52 p 56 p 60
1 p 5 p 9 p p 13 p 17 p 21 p 25 p 29 p 33 p 37 p 41 p 45 p 49 p 53 p 57 p 61
2 p 6 p p 10 p 14 p 18 p 22 p 26 p 30 p 34 p 38 p 42 p 46 p 50 p 54 p 58 p 62
3 p 7 p p 11 p 15 p 19 p 23 p 27 p 31 p 35 p 39 p 43 p 47 p 51 p 55 p 59 p 63

Fig.1 Block state of PUFFIN
图 1 PUFFIN 算法分组比特顺序

PUFFIN 算法加密过程可表示为