三类广义Feistel结构的中间相遇攻击

发布时间：2020-11-20 01:13

　　 Feistel结构由IBM公司的Horst Feistel和Don Coppersmith在1973年设计Lucifer算法时提出,因其具有轮函数选择灵活和加解密相似性等优点,而得到广泛应用。在Feistel结构的基础上,又发展出多种Feistel结构的衍生结构,如三类广义Feistel结构(Type-1型、Type-2型和Type-3型)、收缩Feistel结构和扩张Feistel结构等,这些Feistel结构的衍生结构为密码设计者提供了许多新的思路,同时也引起了研究者的广泛兴趣。Guo等人对Feistel结构、嵌套SP结构的Feistel结构、收缩Feistel结构和扩张Feistel结构进行了研究并给出了通用密钥恢复方案。但是,对于三类广义Feistel结构,目前只有区分攻击的研究,尚未有学者给出对三类广义Feistel结构的密钥恢复攻击。本文利用中间相遇攻击的方法,在选择明文攻击条件下,首次给出了Type-1型、Type-2型和Type-3型广义Feistel结构的通用密钥恢复方案。主要的研究内容及创新点如下:1.给出了对分组规模为n的d分支Type-1型广义结构的5d-3轮的中间相遇攻击。我们通过利用该结构的特殊性及截断差分特征,给出了该结构的3d-1轮中间相遇区分器。接着通过在区分器头部添加d轮,在区分器尾部添加d-2轮,我们以2~((7)d-1(8)n d)的时间复杂度、2~((7)d-1(8)n d)的存储复杂度和的2~(3n d)选择明文量给出了Type-1型广义Feistel结构的5d-3轮密钥恢复攻击。该攻击结果是现有已知的对Type-1型广义Feistel结构最好的密钥恢复攻击。2.给出了对分组规模为n的d分支Type-2型广义结构d(10)3轮的中间相遇攻击。我们通过利用该结构的特殊性及截断差分特征,给出了该结构的d(10)2轮中间相遇区分器。接着通过在区分器头部添加1轮,我们以2~((7)d-1(8)n d)的时间复杂度、2~((7)d-1(8)n d)的存储复杂度和的2~(n d)选择明文量给出了Type-2型广义Feistel结构的d(10)3轮密钥恢复攻击。该攻击结果是现有已知的对Type-2型广义Feistel结构最好的密钥恢复攻击。3.给出了对分组规模为n的d分支Type-3型广义Feistel结构的d(10)2轮密钥恢复攻击。我们通过利用一个特殊的截断差分特征,构造了一个d(10)1轮区分器。接着通过在区分器头部添加1轮,我们给出了Type-3型广义Feistel结构的d(10)2轮密钥恢复攻击,恢复了第一圈全部d-1个轮函数的子密钥。攻击的数据复杂度为2~(2n)个选择明文,存储复杂度为2~dd~(-1n)个分组,每个分组n比特,时间复杂度为2_d~(d-1n)次加密。该攻击结果是已知的对Type-3型广义Feistel结构最好的密钥恢复攻击结果。
【学位单位】：战略支援部队信息工程大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TN918.1
【部分图文】：

第 14 页图 2.3 改变输入差分后的 3d-1 轮差分特征明文对 m, m 0,0, ,j 的输入差分为 j ，我们的轮函数t dF 的输入值为It dF j 且第 t d轮 It d t dF F j 。 同 理 , 第 t d 1轮 的 * 1 1I Ot d t d t dF F F 。 依 次 类 推 ， 我 们 , t 2d轮的输出差分： * O I i i i i iF F F F F 2 1It dF ，根据性质 2.2，我们可以推得2 1I t d F

2.3 Type-1型广义Feistel结构的5 d 3轮中间相遇攻击2.3.1攻击方法概述本节的目标是恢复5 d 3轮Type-1型广义Feistel结构的第1轮和第 4d 轮的子密钥。如图2.4所示, 为了实现5 d 3轮密钥恢复攻击，我们在3d 1轮区分器头部添加d轮，在区分器尾部添加 d 2轮。根据性质4和性质5，如果我们能够计算出1IF 和4IdF ，在已知对应的明密文的条件下，我们就能恢复1K 和4dK 。为了计算出1IF 和4IdF 的值，我们选取很多对满足输入输出差分为 *,*,0, ,0, A *,0, B,*, ,* 的明密文。但是只 有 满 足 差 分 特 征 3 1 2*,*,0, ,0, 0, ,0, , ,*, ,*,0 *,0, ,*, ,d round d round d roundA A B C B 的明密文能够用来计算1IF 和4IdF 的值。所以我们用定理2.1作为一个区分明文对是否满足上述差分特征的区分器。我们的攻击由预计算阶段和在线阶段构成。

第 19 页图 2.5 d 轮差分特征为 *,*,0, ,0, 0, ,0, d roundA A 的充要条件证 明 ： 根 据 性 质 1 ， 我 们 可 得 1, ,12,3, ,d j jX X j d 。 同 1,1 ,2O d dF X 1,1 1O I Id d d d dF X F F F F m 。也就是说输出差0,0, ,0,A 当且仅当 10I Id d d dF F F F m 且 ,10 2,3, ,j X j d。 ,1 1 1 1 1I IF F F F 2 m ， 那 么2,1 X 0当 且 仅 1 1 1 20I IF F F m 。假设2,1 X 0，我们可得20I F ，进而，我们有2O F输入差分为 0,0, ,0,A ，根据性质1，我们有2,2 1,3 3 X X m 0，同时
【参考文献】

相关期刊论文 前10条

1 李永光;曾光;韩文报;;缩减轮数Crypton算法中间相遇攻击的改进[J];计算机科学;2015年11期

2 任炯炯;陈少真;;11轮3D密码算法的中间相遇攻击[J];通信学报;2015年08期

3 李永光;曾光;韩文报;;11轮3D密码算法的中间相遇攻击[J];信息工程大学学报;2015年02期

4 李灵琛;韦永壮;朱嘉良;;11轮3D分组密码算法的中间相遇攻击[J];计算机应用;2015年03期

5 郭瑞;金晨辉;;低轮FOX64算法的零相关-积分分析[J];电子与信息学报;2015年02期

6 伊文坛;陈少真;;Fox密码的多维零相关线性分析[J];密码学报;2015年01期

7 谢作敏;陈少真;鲁林真;;11轮3D密码的不可能差分攻击[J];电子与信息学报;2014年05期

8 卫宏儒;刘青;;FOX密码的中间相遇攻击[J];计算机应用与软件;2014年03期

9 陈杰;胡予濮;张跃宇;董晓丽;;低轮FOX分组密码的差分碰撞攻击(英文)[J];中国通信;2012年07期

10 苏崇茂;韦永壮;马春波;;10轮3D分组密码算法的中间相遇攻击[J];电子与信息学报;2012年03期

本文编号：2890713