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

作者简介:

通讯作者:

邹剑,fzuzoujian15@163.com

中图分类号:

基金项目:

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


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

Fund Project:

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

    本文针对Feistel,Misty与Type-1/2型广义Feistel等结构,创新性地将Simon算法的周期性质与生日攻击思想相结合,提出了一种新型传统密钥恢复攻击.与Simon算法可以在多项式时间内恢复周期值不同,我们在传统计算环境下至少需要生日攻击界才能恢复出对应的周期值.利用我们的新方法,本文可以在O(2n/4)的选择明文和密文条件下,以O(23n/4)的时间复杂度恢复出5轮Feistel-F结构的密钥,对应的存储复杂度为O(2n/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结构,本文给出了d2轮的密钥恢复攻击.当d≥6时,本文对于d分支Type-2型广义Feistel结构的新型密钥恢复攻击轮数会优于现有密钥恢复攻击轮数.

    Abstract:

    This paper proposes some new classical key recovery attacks against Feistel, Misty and Type-1/2 Generalized Feistel Scheme. Our new key recovery attacks can be constructed by combining the birthday attack with the periodic property of Simon’s algorithm, which are different from the previous classical attacks. By using Simon quantum algorithm, an adversary can recover the periodic value in polynomial time in the quantum setting. However, we require the birthday bound to recover the candidate value for the periodic value in the classical setting. By combining the periodic property of Simon’s algorithm with birthday attack, our chosen ciphertexts key recovery attack can recover the key of a 5-round Feistel-F in O(23n/4) time and O(2n/4) chosen plaintexts and ciphertexts. The memory complexity of the above attack is O(2n/4). Compared with Isobe’s result, our new result not only increases one round, but also requires lower memory complexity. For the Feistel-FK structure, we can construct a 7-round key recovery attack. In addition, we can apply the above approach to construct some key recovery attacks against Misty schemes and the Type-1/2 Generalized Feistel Scheme. In details, this paper not only proposes the key recovery attacks against the 5-round Misty L-F and Misty R-F, but also shows the key recovery attacks against the 6-round Misty L-KF/FK and Misty R-KF/FK respectively. In addition, this paper constructs a d2-round key recovery attack for the d branches Type-1 Generalized Feistel Scheme. Furthermore, when d≥6 and d is even, we propose a better key recovery attack for the d branches Type-2 Generalized Feistel Scheme than the previous work.

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

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

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • 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号