Integral attack on PICO algorithm based on division property

doi:10.11772/j.issn.1001-9081.2019122228

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 Zongfu^1,2, YUAN Zheng¹, ZHAO Chenxi^1,2, ZHU Liang^1,2

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,2, 朱亮^1,2

1. 北京电子科技学院密码科学与技术系, 北京 100070;
2. 西安电子科技大学通信工程学院, 西安 710071

通讯作者: 袁征
作者简介:刘宗甫(1995-),男,陕西西安人,硕士研究生,主要研究方向:对称密码算法的安全性分析;袁征(1968-),女,山西中阳人,教授,博士,主要研究方向:密码设计、密码分析、密码混淆;赵晨曦(1996-),女,陕西西安人,硕士研究生,主要研究方向:对称密码算法的安全性分析;朱亮(1995-),男,山东泰安人,硕士研究生,主要研究方向:对称密码算法的安全性分析。
基金资助:
“十三五”国家密码发展基金密码理论课题（MMJJ20180217）。

Abstract

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 2^63.46, the time complexity is 2⁷⁶ 11-round encryptions, and the storage complexity is 2²⁰.

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比特轮子密钥，攻击的数据复杂度为2^63.46，时间复杂度为2⁷⁶次11轮算法加密，存储复杂度为2²⁰。

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

CLC Number:

TP309.7

LIU Zongfu, YUAN Zheng, ZHAO Chenxi, ZHU Liang. Integral attack on PICO algorithm based on division property[J]. Journal of Computer Applications, 2020, 40(10): 2967-2972.

刘宗甫, 袁征, 赵晨曦, 朱亮. 对PICO算法基于可分性的积分攻击[J]. 计算机应用, 2020, 40(10): 2967-2972.

References

[1] BANIK S,PANDEY S K,PEYRIN T,et al. GIFT:a small present[C]//Proceedings of the 2017 International Conference on Cryptographic Hardware and Embedded Systems,LNCS 10529. Cham:Springer,2017:321-345.
[2] BANIK S,BOGDANOV A,ISOBE T,et al. Midori:a block cipher for low energy[C]//Proceedings of the 2015 International Conference on Cryptology and Information Security,LNCS 9453. Berlin:Springer,2015:411-436.
[3] GUO J,PEYRIN T,POSCHMANN A,et al. The LED block cipher[C]//Proceedings of the 2011 International Workshop on Cryptographic Hardware and Embedded Systems, LNCS 6917. Berlin:Springer,2011:326-341.
[4] BEIERLE C,JEAN J,KÖLBL S,et al. The SKINNY family of block ciphers and its low-latency variant MANTIS[C]//Proceedings of the 2016 Annual International Cryptology Conference,LNCS 9815. Berlin:Springer,2016:123-153.
[5] DAEMEN J,KNUDSEN L,RIJMEN V. The block cipher Square[C]//Proceedings of the 1997 International Workshop on Fast Software Encryption, LNCS 1267. Berlin:Springer, 1997:149-165.
[6] BIRYUKOV A,SHAMIR A. Structural cryptanalysis of SASAS[C]//Proceedings of the 2001 International Conference on the Theory and Applications of Cryptographic Techniques,LNCS 2045. Berlin:Springer,2001:395-405.
[7] LUCKS S. The saturation attack-a bait for Twofish[C]//Proceedings of the 2001 International Workshop on Fast Software Encryption,LNCS 2355. Berlin:Springer,2001:1-15.
[8] Z'ABA M R,RADDUM H,HENRICKSEN M,et al. Bit-pattern based integral attack[C]//Proceedings of the 2008 International Workshop on Fast Software Encryption, LNCS 5086. Berlin:Springer,2008:363-381.
[9] TODO Y. Structural evaluation by generalized integral property[C]//Proceedings of the 2015 Annual International Conference on the Theory and Applications of Cryptographic Techniques. LNCS 9056. Berlin:Springer,2015:287-314.
[10] TODO Y. Integral cryptanalysis on full MISTY11[C]//Proceedings of the 2008 International Workshop on 2015 Annual Cryptology Conference,LNCS 9215. Berlin:Springer,2015:413-432.
[11] XIANG Z,ZHANG W,BAO Z,et al. Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers[C]//Proceedings of the 2016 International Conference on the Theory and Application of Cryptology and Information Security, LNC 10031. Berlin:Springer,2016:648-678.
[12] 信文倩, 孙兵, 李超. LiCi算法的基于比特积分攻击[J/OL]. 计算机工程[2020-03-27]. http://kns.cnki.net/kcms/detail/31.1289.TP.20190828.1759.006.html. (XIN W Q, SUN B,LI C. Bit-based integral attack on LiCi[J/OL]. Journal of Computer Engineering[2020-03-27]. http://kns.cnki.net/kcms/detail/31.1289.TP.20190828.1759.006.html)
[13] 尚方舟, 沈璇, 刘国强, 等. 基于MILP搜索的PUFFIN算法积分分析[J]. 密码学报,2019,6(5):627-638.(SHANG F Z, SHEN X,LIU G Q,et al. Integral cryptanalysis on PUFFIN based on MILP[J]. Journal of Cryptologic Research,2019,6(5):627-638.)
[14] 李艳俊, 梁萌. 基于比特可分性的BORON和Khudra积分区分器搜索[J/OL]. 计算机应用研究[2020-03-27]. https://kns.cnki.net/KCMS/detail/51.1196.TP.20191024.1009.031.html. (LI Y J, LIANG M. Integral distinguisher search of BORON and Khudra based on bit-based division property[J] Application Research of Computers[2020-03-27]. https://kns.cnki.net/KCMS/detail/51.1196.TP.20191024.1009.031.html.)
[15] 马楚焱, 刘国强, 李超. 对PICO和RECTANGLE的零相关线性分析[J]. 密码学报,2017,4(5):413-422.(MA C Y,LIU G Q, LI C. Zero-correlation linear cryptanalysis on PICO and RECTANGLE[J]. Journal of Cryptologic Research,2017,4(5):413-422.)
[16] 马楚焱. 混合整数线性规划在分组密码安全性分析中的应用[D]. 长沙:国防科技大学,2017.(MA C Y. Application of mixed integer linear programming in block cipher security analysis[D]. Changsha:National University of Defense Technology, 2017.)
[17] BOGDANOV A,LEANDER G,NYBERG K,et al. Integral and multidimensional linear distinguishers with correlation zero[C]//Proceedings of the 2012 International Conference on the Theory and Application of Cryptology and Information Security,LNCS 7658. Berlin:Springer,2012:244-261.
[18] BANSOD G, PISHAROTY N, PATIL A. PICO:an ultra lightweight and low power encryption design for ubiquitous computing[J]. Defence Science Journal,2016,66(3):259-265.
[19] SUN S,HU L,WANG P,et al. Automatic security evaluation and (related-key) differential characteristic search:application to SIMON,PRESENT,LBlock,DES (L) and other bit-oriented block ciphers[C]//Proceedings of the 2014 International Conference on the Theory and Application of Cryptology and Information Security, LNCS 8873. Berlin:Springer, 2014:158-178.
[20] BIHAM E,SHAMIR A. Differential cryptanalysis of DES-like cryptosystems[J]. Journal of Cryptology,1991,4(1):3-72.
[21] MATSUI M. Linear cryptanalysis method for DES cipher[C]//Proceedings of the 1993 Workshop on the Theory and Application of Cryptographic Techniques, LNCS 765. Berlin:Springer, 1993:386-397.
[22] BOGDANOV A, KHOVRATOVICH D, RECHBERGER C. Biclique cryptanalysis of the full AES[C]//Proceedings of the 2011 International Conference on the Theory and Application of Cryptology and Information Security, LNCS 7073. Berlin:Springer,2011:344-371.
[23] BOGDANOV A,RIJMEN V. Linear hulls with correlation zero and linear cryptanalysis of block ciphers[J]. Designs,Codes and Cryptography,2014,70(3):369-383.
[24] BIHAM E. New types of cryptanalytic attacks using related keys[J]. Journal of Cryptology,1994,7(4):229-246.

Integral attack on PICO algorithm based on division property

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

[1]	CHEN Yonghong, GUO Lili, ZHANG Shibing, YANG Jie. Energy efficiency optimization of heterogeneous cellular networks based on transmitting power of pico base station [J]. Journal of Computer Applications, 2020, 40(4): 1115-1118.
[2]	REN Zhi, TIAN Jieli, YOU Lei, LYU Yuhui. Access protocol for terahertz wireless personal area networks based on high efficient handover of piconet coordinator [J]. Journal of Computer Applications, 2018, 38(3): 728-733.