基于MILP搜索的PUFFIN算法积分分析

作     者：尚方舟 沈璇 刘国强 李超 SHANG Fang-Zhou;SHEN Xuan;LIU Guo-Qiang;LI Chao

作者机构：国防科技大学文理学院长沙410073 国防科技大学信息通信学院武汉430010 

出 版 物：《密码学报》 (Journal of Cryptologic Research)

年 卷 期：2019年第6卷第5期

页      面：627-638页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：国家自然科学基金(61672530 61702537 61772545) 

主　　题：积分分析 混合整数线性规划 可分性质 PUFFIN算法 

摘      要：积分分析是针对分组密码十分有效的分析方法之一,其通常利用密文某些位置的零和性质构造积分区分器,并据此进行密钥恢复攻击.在ASIACRYPT 2016上,向泽军等人首次运用混合整数线性规划(MILP)模型对积分分析可分性质进行刻画,并对六种轻量级分组密码积分区分器进行搜索.本文针对轻量级分组密码PUFFIN算法,运用基于比特可分性质的MILP模型搜索可分路径,得到PUFFIN算法最长9轮积分区分器.但由于该9轮区分器区分优势不够明显且攻击数据复杂度较高,攻击效果不佳.为取得更好的攻击效果,本文选择搜索8轮积分区分器对PUFFIN算法进行10轮密钥恢复攻击.该攻击能够恢复PUFFIN算法100比特轮密钥,攻击的数据复杂度为254.81个选择明文,时间复杂度为267.49次10轮算法加密,存储复杂度为220个存储单元.