软件学报

作者：邹剑，邹宏楷，董晓阳，吴文玲，罗宜元

单位：邹剑，福州大学 计算机与大数据学院, 福建 福州 350108;网络系统信息安全福建省高校重点实验室(福州大学), 福建 福州 35010811,邹宏楷，福州大学 计算机与大数据学院, 福建 福州 350108;网络系统信息安全福建省高校重点实验室(福州大学), 福建 福州 35010802,董晓阳，清华大学 高等研究院, 北京 10019003,吴文玲，中国科学院 软件研究所 可信计算与信息保障实验室, 北京10019004,罗宜元，惠州学院 信息科学技术学院, 广东 惠州 51600705

关键词：Feistel;Misty;Type-1/2型广义Feistel结构;密钥恢复攻击;Simon算法;周期性质;生日攻击

基金：国家自然科学基金(61902073, 62072445, 62072207, 62072109, U1804263); 福建省自然科学基金(2021J01623, 2021J06013)

针对Feistel, Misty与Type-1/2型广义Feistel等结构, 创新性地将Simon算法的周期性质与生日攻击思想相结合, 提出一种新型传统密钥恢复攻击. 与Simon算法可以在多项式时间内恢复周期值不同, 在传统计算环境下至少需要生日攻击界才能恢复出对应的周期值. 利用所提方法, 可以在${\rm{O}}({2^{n/4}})$的选择明文和密文条件下, 以${\rm{O}}({2^{3n/4}})$的时间复杂度恢复出5轮Feistel-F结构的密钥, 对应的存储复杂度为${\rm{O}}({2^{n/4}})$. 上述结果比Isobe和Shibutani的工作结果多扩展1轮, 并且所需的存储复杂度也更少. 对于Feistel-FK结构, 构造7轮密钥恢复攻击. 此外, 还将上述方法应用于构造Misty结构和Type-1/2型广义Feistel结构的密钥恢复攻击. 对于不同的Misty密码方案, 分别给出5轮Misty L-F和Misty R-F结构的密钥恢复攻击, 以及6轮Misty L-KF/FK和Misty R-KF/FK结构的密钥恢复攻击. 对于$d$分支Type-1型广义Feistel结构, 给出${d^2}$轮的密钥恢复攻击. 当d≥6时, 对于d分支Type-2型广义Feistel结构的新型密钥恢复攻击轮数会优于现有密钥恢复攻击轮数.

来源：2023年第9期

《软件学报》期刊编辑部

查看软件学报杂志2023年第9期