基于周期性质的新型密钥恢复攻击方法
作者:
作者单位:

作者简介:

邹剑(1985-),男,博士,副教授,主要研究领域为对称密码分析,量子计算;邹宏楷(1998-),男,硕士生,主要研究领域为量子计算;董晓阳(1988-),男,博士,副研究员,主要研究领域为对称密码算法安全性分析,量子计算;吴文玲(1966-),女,博士,教授,博士生导师,主要研究领域为对称密码算法分析与设计;罗宜元(1986-),男,博士,副教授,主要研究领域为对称密码的安全性分析.

通讯作者:

邹剑,E-mail:fzuzoujian15@163.com

中图分类号:

基金项目:

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


New Key Recovery Attack Based on Periodic Property
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    针对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结构的新型密钥恢复攻击轮数会优于现有密钥恢复攻击轮数.

    Abstract:

    This study proposes a new classical key recovery attack against schemes such as Feistel, Misty, and Type-1/2 generalized Feistel schemes (GFS), which creatively combines the birthday attack with the periodic property of Simon’s algorithm. Although Simon’s algorithm can recover the periodic value in polynomial time, this study requires the birthday bound to recover the corresponding periodic value in the classical setting. By this new attack, the key to a 5-round Feistel-F scheme can be recovered with the time complexity of O(23n/4) under the chosen plaintexts and ciphertexts of O(2n/4), and the corresponding memory complexity is O(2n/4). Compared with the results of Isobe and Shibutani, the above result not only increases one round but also requires lower memory complexity. For the Feistel-FK scheme, a 7-round key recovery attack is constructed. In addition, the above approach is applied to construct the key recovery attacks against Misty schemes and Type-1/2 GFS. Specifically, the key recovery attacks against the 5-round Misty L-F and Misty R-F schemes and those against the 6-round Misty L-KF/FK and Misty R-KF/FK schemes are given; for the d-branch Type-1 GFS, a d2-round key recovery attack is presented, and when d≥6, the number of rounds of the key recovery attack is superior to those of the existing key recovery attacks.

    参考文献
    相似文献
    引证文献
引用本文

邹剑,邹宏楷,董晓阳,吴文玲,罗宜元.基于周期性质的新型密钥恢复攻击方法.软件学报,2023,34(9):4239-4255

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-11-01
  • 最后修改日期:2021-12-02
  • 录用日期:
  • 在线发布日期: 2022-03-24
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号