Type-3型广义Feistel结构的中间相遇攻击  

Meet-in-the-middle Attack on Type-3 Feistel Structure

作　　者：邓元豪 金晨辉[2] 赵杰卿 DENG Yuan-Hao;JIN Chen-Hui;ZHAO Jie-Qing(31008 Army,Beijing 100036,China;Information Engineering University,Zhengzhou 450001,China)

机构地区：[1]31008部队 [2]信息工程大学

出　　处：《密码学报》2019年第1期27-36,共10页Journal of Cryptologic Research

基　　金：国家自然科学基金(61772547;61402523;61272488)~~

摘　　要：Feistel结构是设计迭代型分组密码的几种主流结构之一,其安全性分析受到了广大密码研究人员的关注.在Feistel结构的基础上,又发展出多种Feistel结构的衍生结构.郑玉良等人于1989年提出了Type-1、Type-2和Type-3型三类广义Feistel结构,其继承了Feistel结构加解密相似性的优点且各有特点.董乐等人于2017年利用中间相遇攻击的方法分析了3分支的Type-1型广义Feistel结构.邓元豪等人在Inscrypt 2017上给出了d (d>=4)分支Type-1型广义Feistel结构的中间相遇攻击.对于Type-2型和Type-3型广义Feistel结构,尚未有学者给出通用密钥恢复方案.本文给出了Type-3型广义Feistel结构的一类特殊差分,发现在该差分模式下差分特征的所有可能值小于理论上的最大值,从而构造了区分器.对于分组规模为n比特,且含有d个分支的Type-3型广义Feistel结构,我们利用该性质构造了d+1轮中间相遇区分器.通过在区分器头部添加1轮,我们给出了Type-3型广义Feistel结构的d+2轮密钥恢复攻击,恢复了第一轮全部d-1个轮函数的子密钥.攻击的数据复杂度为2n/2个选择明文,存储复杂度为2^((d-1)n/d)个分组,每个分组n比特,时间复杂度为2^((d-1)n/d)次加密.该攻击方法是已知的对Type-3型广义Feistel结构最好的密钥恢复攻击结果.本文的攻击方法在密钥规模kn时有效.Feistel structure is a widely used structure in iteration block cipher design, whose security attracts much research interests. Based on Feistel structure, there are various kinds of generalized constructions. Zheng et al. present three kinds of generalized Feistel structures in 1989, called Type-1, Type-2, and Type-3 Feistel structure respectively, which have the same advantage as the original Feistel structure, while having their own features. Dong Le et al. analyzed Type-1 Feistel structure with 3 sub-blocks by the meet-in-the-middle technique. At Inscrypt 2017, Deng Yuanhao et al. present a meet-in-the-middle attack on Type-1 Feistel structure with d(d >=4) sub-blocks. However, there is no generic key-recovery attack on Type-2 and Type-3 Feistel structure. This paper presents a special difference of this structure, and it is found that the possible number of differential characteristics is less than that in theory, which leads to a d + 1 rounds distinguisher. Then this paper presents key recovery attacks on Type-3 Feistel structure based on this finding. For Type-3 Feistel structure with n bits blocks and d sub-blocks, a d + 1 rounds distinguisher is launched. By prepending one round at the top of the distinguisher, a d + 2 rounds key-recovery attack on Type-3 Feistel structure can be made possible. Moreover, all of the d-1 distinct subkeys in the first round can be recovered. The data complexity is 2n/2chosen plaintexts, the memory complexity is 2(d-1)n/dblocks, each block is n bits, and the time complexity is 2(d-1)n/dtimes that of encryptions, which is the best known generic key recovery attack on Type-3 Feistel structure. The attack is valid if k n.

关 键 词：Type-3型广义Feistel结构 中间相遇攻击 密钥恢复攻击 

分 类 号：TN918.1[电子电信—通信与信息系统]