基于MILP模型的PFP算法的不可能差分分析

Impossible Differential Analysis of PFP Algorithm Based on MILP Model

PFP算法是借鉴国际标准PRESENT算法设计思想提出的一种轻量级分组密码算法,它使用Feistel结构,分组长度为64比特,密钥长度为80比特,迭代34轮。与以往的手动推导等方法不同,本文对PFP算法建立基于混合整数线性规划(MILP)的不可能差分计算模型,通过自动搜索研究获得了12,497个9轮(均是目前为止最长的)不可能差分区分器。并选取一个可以利用PFP算法S盒的差分传播特性的差分路径,构造出不可能差分区分器,实现了对PFP算法进行了13轮(文献中最多到9轮)不可能差分分析。这是目前为止攻击轮数最多、时间复杂度最低的一个攻击结果。

PFP algorithm is a lightweight block cipher algorithm using the design idea of the international standard PRESENT algorithm for reference,it adopted the Feistel structure and the block length,key length and iteration are 64 bits,80 bits and 34 rounds respectively.Different from the previous manual derivation methods,an impossible differential calculation model based on the MILP(Mixed Integer Linear Programming)for the PFP algorithm is established in this paper,and 12,4979-round impossible differential differentiators(all are longest so far)are obtained through automatic search research.A differentiator capable of utilizing the differential propagation characteristics of the S-box in the PFP algorithm is selected to construct an impossible differential path,and to realize an impossible differential cryptanalysis to the PFP algorithm for 13 rounds(up to 9 rounds in available literatures).Our cryptanalysis achieves the highest attack round and lowest time complexity to date.