Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (10): 2967-2972.DOI: 10.11772/j.issn.1001-9081.2019122228

• Cyber security • Previous Articles     Next Articles

Integral attack on PICO algorithm based on division property

LIU Zongfu1,2, YUAN Zheng1, ZHAO Chenxi1,2, ZHU Liang1,2   

  1. 1. Department of Cryptography Science and Technology, Beijing Electronic Science and Technology Institute, Beijing 100070, China;
    2. School of Communication Engineering, Xidian University, Xi'an Shaanxi 710071, China
  • Received:2020-01-06 Revised:2020-03-25 Online:2020-10-10 Published:2020-07-08
  • Supported by:
    This work is partially supported by the Cryptology Theory Project of National Cryptology Development Fund During the 13th Five Year Plan (MMJJ20180217).

对PICO算法基于可分性的积分攻击

刘宗甫1,2, 袁征1, 赵晨曦1,2, 朱亮1,2   

  1. 1. 北京电子科技学院 密码科学与技术系, 北京 100070;
    2. 西安电子科技大学 通信工程学院, 西安 710071
  • 通讯作者: 袁征
  • 作者简介:刘宗甫(1995-),男,陕西西安人,硕士研究生,主要研究方向:对称密码算法的安全性分析;袁征(1968-),女,山西中阳人,教授,博士,主要研究方向:密码设计、密码分析、密码混淆;赵晨曦(1996-),女,陕西西安人,硕士研究生,主要研究方向:对称密码算法的安全性分析;朱亮(1995-),男,山东泰安人,硕士研究生,主要研究方向:对称密码算法的安全性分析。
  • 基金资助:
    “十三五”国家密码发展基金密码理论课题(MMJJ20180217)。

Abstract: PICO proposed in recent years is a bit-based ultra lightweight block cipher algorithm. The security of this algorithm to resist integral cryptanalysis was evaluated. Firstly, by analyzing the structure of PICO cipher algorithm, a Mixed-Integer Linear Programming (MILP) model of the algorithm was established based on division property. Then, according to the set constraints, the linear inequalities were generated to describe the propagation rules of division property, and the MILP problem was solved with the help of the mathematical software, the success of constructing the integral distinguisher was judged based on the objective function value. Finally, the automatic search of integral distinguisher of PICO algorithm was realized. Experimental results showed that, the 10-round integral distinguisher of PICO algorithm was searched, which is the longest one so far. However, the small number of plaintexts available is not conducive to key recovery. In order to obtain better attack performance, the searched 9-round distinguisher was used to perform 11-round key recovery attack on PICO algorithm. It is shown that the proposed attack can recover 128-bit round key, the data complexity of the attack is 263.46, the time complexity is 276 11-round encryptions, and the storage complexity is 220.

Key words: ultra lightweight block cipher algorithm, PICO, integral cryptanalysis, division property, Mixed-Integer Linear Programming (MILP)

摘要: 对近年来提出的基于比特的超轻量级分组密码算法PICO抵抗积分密码分析的安全性进行评估。首先,研究了PICO密码算法的结构,并结合可分性质的思想构造其混合整数线性规划(MILP)模型;然后,根据设置的约束条件生成用于描述可分性质传播规则的线性不等式,并借助数学软件求解MILP问题,从目标函数值判断构建积分区分器成功与否;最终,实现对PICO算法积分区分器的自动化搜索。实验结果表明,搜索到了PICO算法目前为止最长的10轮积分区分器,但由于可利用的明文数太少,不利于密钥恢复。为了取得更好的攻击效果,选择搜索到的9轮积分区分器对PICO算法进行11轮密钥恢复攻击。通过该攻击能够恢复128比特轮子密钥,攻击的数据复杂度为263.46,时间复杂度为276次11轮算法加密,存储复杂度为220

关键词: 超轻量级分组密码算法, PICO, 积分密码分析, 可分性质, 混合整数线性规划

CLC Number: