积分分析及其在PUFFIN算法中的应用

作     者：尚方舟 

作者单位：国防科技大学 

学位级别：硕士

导师姓名：李超

授予年度：2019年

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

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

摘      要：积分分析是针对分组密码十分有效的分析方法之一,其通常利用密文某些位置的零和性质构造积分区分器,并据此进行密钥恢复攻击。为了更加充分地利用算法中的非线性组件信息,在EUROCRYPT 2015上,日本学者Todo提出可分性理论,并给出了搜索积分区分器的一般化算法。之后,在FSE 2016上,Todo等人将可分性概念应用到基于比特的分组密码。但由于基于比特的可分性质搜索复杂度比较大,在ASIACRYPT 2016上,向泽军等人首次运用混合整数线性规划(Mixed-Integer Linear Programming,MILP)模型对可分性质进行刻画,并将其应用到六种轻量级分组密码积分区分器的搜索。本文主要成果如下:(1)运用基于比特可分性质结合MILP搜索工具,得到PUFFIN算法9轮积分区分器。但由于该9轮区分器区分优势不够明显且攻击数据复杂度较高,攻击效果不佳。本文选择8轮积分区分器对PUFFIN算法进行10轮密钥恢复攻击。该攻击能够恢复100比特轮密钥,攻击的数据复杂度为254.81个选择明文,时间复杂度为2次10轮算法加密,存储复杂度为220个存储单元。进一步,运用传统比特可分性的扩展——三元集比特可分性结合MILP搜索工具,得到PUFFIN算法平衡比特数更多的9轮积分区分器。这是PUFFIN算法目前已知最长的积分区分器。(2)为得到更好的实际攻击效果,本文从传统的积分分析出发,考虑以高概率成立的零和性质,首次提出了概率布尔多项式的概念及其运算法则,并由此给出概率积分区分器构造方法及其分析模型。将该方法运用到PUFFIN算法中,得到了7轮概率积分区分器。进一步,利用构造的概率积分区分器,对9轮PUFFIN算法进行密钥恢复攻击,并进行了实验验证。该攻击可恢复92比特轮密钥,数据复杂度为224.8个选择明文,时间复杂度为235.48次9轮加密,存储复杂度为220个存储单元。这是目前已知PUFFIN算法最好的实际积分攻击结果。