轻量级PFP算法的差分攻击

李艳俊，李寅霜，杨明华，张黎仙，刘 健

1.中国电子科技集团公司 第十五研究所 信息产业信息安全测评中心，北京 100083

2.北京电子科技学院，北京 100070

3.北京工商大学，北京 100048

随着网络、通信与微电子技术的迅猛发展，物联网[1]这一新兴事物逐渐被广泛应用于多种工业领域。密码技术是保障信息安全的核心技术，其中的分组密码算法是保障信息安全传输的主流密码算法，它可以提供信息的机密性。同时，广泛应用于物联网工业中的典型设备主要是无线传感器、RFID（radio frequency identification）标签、智能卡等体积较小的微电子产品。这些设备具有体积小、要求能耗低、软硬件计算资源受限[2]、电池难以续航等特点。正由于这些原因，使得传统的高复杂度的分组密码算法不能直接应用于具有低功耗要求的物联网设备中。由此，设计出具有较高安全性的轻量级分组密码算法对于实现物联网的更广泛应用具有非常重要的理论意义和工程价值。

近些年，一大批轻量级分组密码被广泛提出，如LBlock、PRESENT、Midori、LED、ZORRO、PFP[3-8]等，轻量级分组密码在正式投入使用之前，非常有必要对它们进行精确的安全性分析，分析成果既可以为轻量级密码的应用提供参考，也可以为新的轻量级密码算法设计提供相应的参考价值。其中PFP 算法是2017年黄玉划等人[8]为了解决面向无线终端资源受限问题设计的超轻量级分组密码算法。算法借鉴了国际标准PRESENT算法的设计思想，整体结构采用了Feistel 结构，具有更高效的软硬件实现效率。

针对分组密码，目前最有效的攻击方法是差分分析[9]、截断差分分析、不可能差分分析[10]、线性分析[11]、积分分析和中间相遇攻击等。其中差分分析是由Biham等人[12]于1991 年针对DES 提出的，本质上是寻找密码算法中存在的高概率差分特征或差分路径来恢复密钥。随着技术的发展，为了能够快速有效找到高概率且更长的差分路径，基于混合整数线性规划（mixed integer linear program，MILP）、布尔可满足性问题（Satisfiability，SAT）等数学工具的自动化差分搜索技术逐渐成熟。2014 年，Sun 等人在文献[13]中通过SAGE 工具来刻画产生S盒差分分布特性的线性不等式集合，并利用这些不等式构建了搜索差分特征的MILP模型。由于搜索程序是启发式的，得到的结果不一定是最优，为了克服这一问题，Sun等人在文献[14]中提出了一种贪心算法，将启发式的搜索算法转变为准确且可以实际应用的搜索方法。

算法设计者在文献[8]提出PFP算法时，对其抗差分能力、不可能差分能力也进行了安全性评估，给出了PFP算法20轮差分活动S盒的个数，通过计算PFP算法的15轮差分概率为2-106，从而推断PFP算法没有明显的15轮差分特征；同时设计者也找到了PFP算法的5轮不可能差分区分器，进行了6 轮的攻击。2020 年沈璇等人[15]推导出了PFP的7轮不可能差分区分器，并进行了9轮的攻击；2022 年黄思佳等人[16]利用MILP 自动化搜索工具找到了12 497 个9 轮不可能差分区分器并进行了13轮的不可能差分攻击，表1给出了PFP算法攻击结果比较。

表1 PFP算法攻击结果比较Table 1 Comparison of PFP algorithm attack results

1 PFP算法

PFP 算法采用经典的二分支Feistel结构，通过借鉴PRESENT算法的轮函数从而设计的。算法的分组长度为64 bit，密钥长度为80 bit，迭代轮数为34。

1.1 常用的符号和术语

M：明文；

Ki：第i轮子密钥；

Li：第i轮输入的左分支64 bit；

Ri：第i轮输入的右分支64 bit；

⊕：按位异或。

1.2 加密变换

把输入的64 bit的分组明文M分为长度为32 bit的左右两分支L0和R0，即M=L0||R0。

对i=0,1,2,…,33，进行如下第i轮变换计算：

Li+1=Ri,Ri+1=Li⊕F(Ri,Ki)

34 轮迭代后输出密文C=L34||R34。加密流程如图1所示。

图1 加密流程图Fig.1 Encryption flow chart

1.3 密钥扩展算法

将主密钥K=k79k78…k0存储在一个80 bit 的密钥寄存器中，取寄存器K的最左边32 bit作为当前轮的子密钥。因此在第i轮，有Ki=ki31ki30…ki0=k79k78…k48。提取子密钥Ki后，对当前的密钥寄存器K=k79k78…k0进行以下更新操作，其中rc为当前的轮次数，S[K]表示对K进行S盒变换。

（1）[k79k78…k0]=[k18k17…k20k19]

（2）[k79k78k77k76]=[k79k78k77k76]

（3）[k19k18k17k16k15]=[k19k18k17k16k15]⊕rc

1.4 轮函数设计

PFP 算法的轮函数F由子密钥加、S 盒及P 置换3个部分组成。

子密钥加。将右分支Ri与第i轮的子密钥Ki进行按位异或，即对Ri=b31b30…b0，进行如下变换：R′i=Ri⊕Ki。

S盒。PFP算法使用了PRESENT算法的S盒，如表2所示。加密时，8个相同的4 bit的S盒并行加密。

表2 S盒Table 2 S-box

P 置换。采用位排列置换，数据经过P 置换后第i比特移动到第P(i)比特。用公式可以表示为：

2 自动化搜索差分特征MILP模型

在PFP 算法中，共涉及到3 种操作：XOR（异或）操作、P置换、S盒。其中RP置换，可以根据相应的比特位置给出等式的约束，重点考虑另外2个操作。

2.1 XOR操作的约束

假设XOR（异或）操作的输入差分为Δa=(Δa0,Δa1,…,Δa31) 和Δb=(Δb0,Δb1,…,Δb31) ，输出差分为Δc=(Δc0,Δc1,…,Δc31)。对0 ≤i≤31，满足Δai⊕Δbi=Δci。由此构建异或操作的差分约束为：

其中，di是假设的0－1 变量，且0 ≤i≤31。

2.2 S盒操作的约束

Sun 等人在文献[14]中提出了S 盒所有可能差分模式的凸闭包H表示方法，利用线性不等式来描述S盒的差分性质，使得刻画的S 盒差分性质更加精确，但对每个S 盒，此方法都会产生大量的不等式，因此需要使用贪心算法来最大程度地减少不等式的数量。

首先需要根据S 盒的差分分布表得到PFP 算法的输入-输出差分分布。将输入-输出差分全部拆分成二进制，得到表3。

表3 S盒的输入-输出差分分布表Table 3 Input-output differential distribution table for S-box

对于S 盒的输入差分(x0x1x2x3) ，输出差分(y0y1y2y3)，可以用向量{x0x1x2x3y0y1y2y3} 表示这种对应关系。为了便于描述，将向量{x0x1x2x3y0y1y2y3}写为{x0x1x2x3x4x5x6x7}的形式。由此，可以把该S 盒的输入特征和输出特征看作ℝ4+4上的一个点，用集合T表示S 盒所有的输入输出形式向量，然后使用SAGE工具生成集合T的凸包不等式组表示H，从而得到327 个线性不等式，最后利用文献[14]中提出的贪婪算法将不等式的数量化简到23 个，化简后的不等式如下所示：

除了所列出的约束，对于S 盒的操作还需要另外3个约束。首先假设S 盒操作的输入差分为Δx=(x0,x1,…,x31)，输出差分为Δy=(y0,y1,…,y31)，PFP 算法每个S盒的输入输出长度都为4 bit，每一轮有8个S盒，设二进制变量Ai为第i个S 盒的活跃标记，即当第i个S盒活跃时，Ai=1，否则Ai=0。

约束1 输入差分不可以全为0，用不等式刻画为：

约束2 当Ai的输入差分不为0时，Ai为活跃的S盒，即对i=0,1,…,7：

然后利用MILP 进行建模搜索，最终搜索得到了PFP算法的一个良好4轮迭代差分路径，如表4所示。

表4 4轮迭代差分路径Table 4 4-round iterative differential path

2.3 PFP算法的22轮差分区分器

可以迭代五次表4 所示的4 轮概率为2-11的迭代差分路径，从而构造出概率为2-55的20 轮差分路径，然后再分别向前后扩展1轮概率为2-2的差分路径，最终构建出有效的22轮差分区分器如图2所示。

图2 22轮差分区分器Fig.2 22-round differential differentiator

3 PFP算法的密钥编排特点

通过研究PFP算法的密钥扩展算法，可以发现每一轮只有子密钥的[31-28]比特位经过了S盒变换和异或操作，其比特值发生改变；而其他位置的比特仅仅发生了移位，通过观察这种规律，在密钥恢复阶段，就可以避免猜测重复的密钥。

如图3所示，显然K0,[26-24]（K0的[26-24]比特位）与K1,[7-5]重复，如果先猜测了第0轮的K0,[26-24]，则第1轮的K1,[7-5]便已知，不需要再重复猜测，同样的，显然K24,[27-24,19]与K25,[8-5,0]相同。

图3 PFP算法的密钥编排特点Fig.3 Key scheduling features of PFP algorithm

当已经猜测了K1,[7-5]和K0,[27]时，由于这4 bit在第4 轮会一同经过S 盒和异或操作（可计算具体值），从而得到K4,[30-28]，其值等价于K25,[31-29]，所以可以说K1,[7-5]与K25,[31-29]经过变换后等价；同样的，当已经猜测了K0,[19-16]时，这4 bit会在第12轮经过S盒和异或操作得到K12,[31-28]，其值等价于K25,[24-21]，所以可以说K25,[23-21]与K0,[18-16]经过变换后等价；K25,[24]与K0,[19]经过变换后等价。

4 PFP算法的26轮密钥恢复攻击

根据图2所示的22轮差分路径，可以在区分器的前后分别添加两轮进行26轮的密钥恢复攻击，如图4。此时，左输入差分为[000000E0⊕P(0*0*0*0*)]，右输入差分为[P(000000*0)⊕07000000]，其中“*”表示任意非零字节，“？”表示任意字节。

图4 26轮密钥恢复攻击Fig.4 26-round key recovery attacks

步骤1 构造2n个明文结构，每个差分的结构形式如：

其中，每个“*”位可选择24-1 个值，共组成2n+39个明文对，对这些明文加密26 轮，得到相应的2n+39个密文对。在得到的2n+39个密文对中，选择差分形式结构为L26=000000A0⊕P(0*0*000*)，R26=????????的，筛选后剩下密文对的个数为2n+39－20。由于R0=P(000000*0)⊕07000000 的“*”所对应比特位的值需要与“E”经过S盒变换后的8 个值相同，L1=000000E0⊕P(0*0*0*0*)的每个“*”需要与R0的“*”经过扩散后的对应位置的8种情况抵消，筛选后剩下密文对2n+39－20－5。

步骤2 猜测K0,[27-24,19-16,11-8,3-0]总共16 bit，采用提前抛弃技术，先猜测其中的4 bit，再分三步猜测剩下的比特，计算P[S(R0⊕K1)]⊕L0，判断是否符合R1，筛选后剩下2n+14－12个密文对。

步骤3 猜测K1,[7-4]，由密钥编排特点可知K1,[7-5]与K0,[26-24]重复，所以这一步只需要猜测1 bit，计算P[S(R1⊕K2)]⊕L1，判断是否符合R2，筛选后剩下2n+2－3个密文对。

步骤4 猜测K25,[31-0]全部的32 bit。先猜测K25,[31-28]，由密钥编排特点可知，K25,[31-29]与已猜测的K1,[7-5]经过变换后等价，所以只需要猜测1 bit 的K25,[28]；然后猜测K25,[23-20]，同样的K25,[23-21]与K0,[18-16]经过变换后等价，所以仅猜测1 bit的K25,[20]；接着猜测K25,[27-24]，同样的K25,[24]与K0,[19]经过变换后等价，所以仅猜测3 bit 的K25,[27-25]；最后，再分五步每次猜测4 bit 来猜测剩下20 bit的K25,[19-0]，计算P[S(R25⊕K26)]⊕R26，判断是否符合L25，筛选后剩下2n－1－4－4－4－20个密文对。

步骤5 猜测K24,[27-24,19-16,3-0]，由密钥编排特点可知，K24,[27-24,19]与已猜测的K25,[8-5,0]相同，所以这一步猜 测K24,[18-16,3-0]总 共7 bit，计 算P[S(R24⊕K25)]⊕R25，判断是否符合L24，筛选后剩下2n－33－12=2n－45个密文对。

因此，选择n=40，对于猜测正确的48 bit 密钥而言，平均有1个明密文对留下来；对于错误的密钥而言，平均有2-5个明密文对留下来。

复杂度分析：

步骤1 需要加密240×220=260个明文；

步骤2 需要进行以下次S盒查询：

步骤3 需要进行216×21×240+5-3=259次S盒查询；

步骤4 需要进行的S盒查询次数如下：

步骤5 需要进行242×27×27=256次S盒查询。

所以数据复杂度为260个明文，一轮PFP 轮函数加密的复杂度相当于8 次S 盒查询，时间复杂度为(258+259+260+261+259+257+256+256)÷26÷8 ≈254.3次26 轮加密。

5 结束语

本文对PFP 算法进行了差分分析，通过MILP 工具搜索到了其4 轮迭代差分，从而构造了22 轮差分路径，进行了26轮的密钥恢复攻击。攻击过程运用了PFP算法的密钥编排特点，采用了提前抛弃技术，降低了计算复杂度，最终使得26 轮密钥恢复攻击的数据复杂度为260个明文，时间复杂度为254.3次26 轮加密。然而，如何搜索到更长的差分路径，实现更多轮数的密钥恢复攻击则是下一步的工作。