基于MILP的PICO算法差分和线性区分器的搜索

MILP-Based Search for Differential and Linear Distinguishers of PICO Algorithm

PICO算法是由Bansod等人在2016年提出的一种基于替换和排列的SPN网络的轻量级分组密码.目前针对PICO算法抵抗差分和线性分析的能力还有待进一步评估.本文基于MILP模型,首先利用不等式组对各组件的差分特征和线性掩码的传播规律进行了精细的刻画,其次针对密码算法的结构特点及S盒特性,对该模型进行了优化,缩小了搜索空间,并提出了针对PICO算法有效的两步搜索算法.最后利用该算法,搜索到了3条新的概率为2−63的21轮差分区分器,并首次搜索到了3条相关度为2−30的20轮线性区分器,为当前公开发表的最长线性区分器.

The PICO algorithm is a lightweight packet cipher based on substitution and permutation SPN networks proposed by Bansod et al.in 2016.The ability of the PICO algorithm to resist differential and linear analysis is yet to be further evaluated.Based on the MILP model,this paper describes the differential characteristics of the components and the propagation law of the linear mask using a set of inequalities,optimizes the model for the structural characteristics of the cryptographic algorithm and the S-box properties,narrows the search space,and proposes an effective two-step search algorithm for the PICO algorithm.Using this algorithm,three new 21-round differential distinguishers with probability 2−63 are found,and three 20-round linear distinguishers with correlation 2−30 are found,which are the longest linear distinguishers known so far.