Page 213 - 《软件学报》2021年第9期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(9):2837−2848 [doi: 10.13328/j.cnki.jos.005972] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
概率积分及其在 PUFFIN 算法中的应用

尚方舟, 孙 兵, 刘国强, 李 超

(国防科技大学 文理学院,湖南 长沙 410073)
通讯作者: 李超, E-mail: academic_lc@163.com

摘 要: 积分分析是一种针对分组密码十分有效的分析方法,其通常利用密文某些位置的零和性质构造积分区分
器.基于高阶差分理论,可通过研究密文与明文之间多项式的代数次数来确定密文某些位置是否平衡.从传统的积分
分析出发,首次考虑常数对多项式首项系数的影响,提出了概率积分分析方法,并将其应用于 PUFFIN 算法的安全性
分析.针对 PUFFIN 算法,构造了 7 轮概率积分区分器,比已有最好的积分区分器轮数长 1 轮.进一步,利用构造的概率
积分区分器,对 9 轮 PUFFIN 算法进行密钥恢复攻击.该攻击可恢复 92 比特轮密钥,攻击的数据复杂度为 2 24.8 个选择
20
明文,时间复杂度为 2 35.48 次 9 轮算法加密,存储复杂度为 2 个存储单元.
关键词: 积分分析;高阶差分分析;概率积分;PUFFIN 算法
中图法分类号: TP309

中文引用格式: 尚方舟,孙兵,刘国强,李超.概率积分及其在 PUFFIN 算法中的应用.软件学报,2021,32(9):2837−2848.
http://www.jos.org.cn/1000-9825/5972.htm
英文引用格式: Shang FZ, Sun B, Liu GQ, Li C. Probability integral cryptanalysis and its application on PUFFIN. Ruan Jian Xue
Bao/Journal of Software, 2021,32(9):2837−2848 (in Chinese). http://www.jos.org.cn/1000-9825/5972.htm
Probability Integral Cryptanalysis and Its Application on PUFFIN

SHANG Fang-Zhou, SUN Bing, LIU Guo-Qiang, LI Chao
(College of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410073, China)

Abstract: Integral cryptanalysis is an effective method of block cipher analysis, and the integral distinguisher is usually constructed
using a zero-sum property of some positions in the ciphertext. Based on the theorem of higher-order differential attack, the order of
plaintexts can be exploited, to determine if some positions of the ciphertext are balanced. Inspired by the conventional integral
cryptanalysis, the influence of constant on the leading-coefficient of polynomial is considered and the construction of probability integral
distinguisher as well as the attack method are proposed in this study. When applied to PUFFIN, a 7-round probability integral
distinguisher is constructed and used to mount a 9-round attack, and this attack can recover 92-bit round key. The data/time complexity is
20
2 24.8 chosen plaintexts, and 2 35.48 9 round encryptions, and the space complexity is 2 .
Key words: integral cryptanalysis; higher-order differential attack; probability integral cryptanalysis; PUFFIN
[3]
[2]
[1]
积分分析 是针对分组密码十分有效的分析方法之一,它是由 Square 攻击 、Multiset 攻击 和 Saturation
[4]
攻击 发展而来的一种分析方法.
积分分析分为两个阶段:第 1 阶段为构造尽可能长的积分区分器,第 2 阶段为利用构造的积分区分器进行
密钥恢复攻击.其中,第 1 阶段是积分分析的关键所在,主要利用具有特殊结构的明文加密后的密文在某些字节
或比特上异或和为常数,通常来说该常数为 0;第 2 阶段进行密钥恢复攻击,若猜测的密钥为正确密钥,则密文反
解后对应字节或比特异或和一定为常数;若猜测的密钥为错误密钥,则对应异或和随机分布.

∗ 基金项目: 国家自然科学基金(61672530, 61702537, 61772545)
Foundation item: National Natural Science Foundation of China (61672530, 61702537, 61772545)
收稿时间: 2018-12-27; 修改时间: 2019-05-29; 采用时间: 2019-10-13