MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}}); function MyAutoRun() {    var topp=$(window).height()/2; if($(window).height()>450){ jQuery(".outline_switch_td").css({ position : "fixed", top:topp+"px" }); }  }    window.onload=MyAutoRun; $(window).resize(function(){ var bodyw=$win.width(); var _leftPaneInner_width = jQuery(".rich_html_content #leftPaneInner").width(); var _main_article_body = jQuery(".rich_html_content #main_article_body").width(); var rightw=bodyw-_leftPaneInner_width-_main_article_body-25;   var topp=$(window).height()/2; if(rightw<0||$(window).height()<455){ $("#nav-article-page").hide(); $(".outline_switch_td").hide(); }else{ $("#nav-article-page").show(); $(".outline_switch_td").show(); var topp=$(window).height()/2; jQuery(".outline_switch_td").css({ position : "fixed", top:topp+"px" }); } }); 分组密码TWINE的中间相遇攻击
  软件学报  2015, Vol. 26 Issue (10): 2684-2695   PDF    
分组密码TWINE的中间相遇攻击
汪艳凤1, 2 , 吴文玲1    
1. 中国科学院 软件研究所 可信计算与信息保障实验室, 北京 100190;
2. 中国科学院 研究生院, 北京 100049
摘要:将Biclique初始结构与标准的三子集中间相遇攻击相结合,给出了一种普遍的中间相遇攻击模式.与Biclique分析相比,该模式下的攻击作为算法抗中间相遇攻击的结果更为合理.进一步地,评估了算法TWINE抗中间相遇攻击的能力,通过合理选择中立比特位置以及部分匹配位置,给出了18轮TWINE-80以及22轮TWINE-128算法的中间相遇攻击结果.到目前为止,这是TWINE算法分析中数据复杂度最小的攻击结果.
关键词分组密码    TWINE    中间相遇攻击    Biclique    数据复杂度    
Meet-in-the-Middle Attack on TWINE Block Cipher
WANG Yan-Feng1, 2 , WU Wen-Ling1    
1. Trusted Computing and Information Assurance Laboratory, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China;
2. Graduate University, The Chinese Academy of Sciences, Beijing 100049, China
Abstract: This paper presents a general structure of meet-in-the-middle attack by combing the advantages of Biclique and three sub-set meet-in- the-middle. Compared with the Biclique cryptanalysis proposed in Asiacrypt 2011, this attack model is more reasonable to be regarded as the security of one block cipher against meet-in-the-middle attack. Moreover, the study evaluates the security of TWINE against meet-in-the- middle attack and gives attacks on 18-round TWINE-80 and 22-round TWINE-128. Meanwhile, the data complexities of these attacks are the least among the precious attacks on TWINE.
Key words: block cipher    TWINE    meet-in-the-middle    Biclique    data complexity    

中间相遇攻击方法最早由Diffie和Hellman提出[1],之后被广泛应用于Hash函数的安全性分析.Aoki及Sasaki使用该方法给出了基于AES算法的Hash函数的原像攻击,并应用到Whirlpool算法中[2].除此之外,该分析方法首次给出了MD5及Tiger算法的全轮的原像攻击[3, 4]、SHA-1及SHA-2算法的最好的原像攻击[5, 6]以及SHA-2的伪碰撞攻击[7].该分析方法在分析Hash函数的过程中,分析人员提出了各种分析技巧,比如剪接技术、初始结构技巧以及部分匹配技术[6, 8].近年来,很多密码学分析者将该方法应用到分组密码的安全性分析中[9, 10],并提出了三子集中间相遇攻击[11].

三子集中间相遇攻击基于的事实是:密码算法的部分中间状态既可以从明文出发向后计算得到,也可以从密文出发向前计算得到.同时,两部分的计算过程中都不覆盖全部的主密钥信息.如此,攻击者可以在优于穷搜攻击的时间内恢复主密钥信息.该攻击方法首次给出了KATAN族算法全轮的攻击方案.此外,Hash函数分析中的初始结构技巧以及部分匹配技巧同样可以应用于分组密码算法的分析中.一种广泛应用的初始结构被称为Biclique.备受关注的Biclique分析将Biclique初始结构与中间相遇相结合,给出了全轮AES算法的攻击结果[12].但是,该攻击方法在中间相遇的计算过程中遍历了全密钥空间,借助时间存储折中技巧,通过预计算并存储部分计算过程,其他密钥下的计算过程只重复计算与存储过程不同的非线性部分,以此达到微优于穷举攻击的单密钥攻击方案.正如文献[13]中所言,Biclique分析方法可以看作是一种加速后的穷举攻击,可以给出任意算法的全轮攻击并使时间复杂度略优于穷举攻击,如Present[14],LED,mCrypton[15],LBlock[16].因此,将Biclique分析的结果作为算法抗中间相遇攻击的安全性评估结果有点牵强.

为了避开中间相遇过程的穷搜密钥情形,本文将Biclique初始结构直接与标准的三子集中间相遇过程结合.当然,与加速后的穷举方法相比,该分析方法下攻击轮数较少,但是该方法下的评估结果作为算法抗中间相遇攻击的能力更有说服力.此外,Biclique结构与三子集部分匹配结合的技巧曾经给出了14轮的Piccolo-80的攻击过程[17];但是该攻击过程中的Biclique位于中间位置,因此导致整个攻击过程需要全密码本的数据量,攻击成功的意义明显下降.为了避免此类情况的发生,在本文提出的中间相遇方法中,将Biclique初始结构建立在明密文附近,以控制攻击的数据复杂度.

TWINE算法[18]是一种轻量级分组密码算法,其分组长度为64bit,密钥长度可以是80bit或者是128bit.设计文档中,针对算法最好的攻击结果是23轮TWINE-80的不可能差分分析以及24轮的TWINE-128的不可能差分分析,两种攻击需要的数据量均在250以上.如上所述,Biclique分析可以给出全轮TWINE算法时间复杂度略优于穷举攻击的结果[19],数据复杂度为260的选择明密文.由于在很多具体的协议环境中只有少量的明密文可以使用[20, 21],因此 ,低数据量下的攻击备受关注.本文将Biclique初始结构与三子集中间相遇相结合,给出了18轮的TWINE-80以及22轮的TWINE-128的中间相遇攻击,攻击成功需要的选择明密文量分别为216和212.这是现存的针对TWINE算法攻击中数据量最少的攻击结果.

1 TWINE 算法简介

轻量级分组密码TWINE算法发表在2012年SAC会议上,其分组长度为64bit,密钥长度可以是80bit或128bit.根据密钥长度的不同,算法分别记为TWINE-80以及TWINE-128.下面简单介绍算法的加密过程以及密钥编排算法.

1.1 加密过程

TWINE算法采用16分支的广义Feistel结构,两种密钥长度下,算法迭代轮数均为36轮.其轮函数包括3种操作:轮密钥加、4bit的S盒变换以及拉线置换P,具体过程如图1所示,其中,每个方块代表长度为4bit的单元.因为具体的S盒置换信息与本文攻击过程无关,所以这里不再详述S盒变换.

图1 TWINE算法的轮函数 Fig.1 Round function of TWINE
1.2 密钥编排算法

图1可知,每轮加密过程需要32bit的轮子密钥.下面根据密钥长度的不同,分别介绍轮子密钥的生成过程.

1.2.1 TWINE-80的密钥编排算法

将80bit的主密钥K以4bit为单位分为20块,迭代更新后选择8个块(共32bit)作为轮子密钥RK嵌入加密过程,具体生成算法为:

\[\begin{align} & {{K}_{0}}||{{K}_{1}}||...||{{K}_{18}}||{{K}_{19}}\leftarrow K \\ & RK_{0}^{1}\leftarrow {{K}_{1}},RK_{1}^{1}\leftarrow {{K}_{3}},RK_{2}^{1}\leftarrow {{K}_{4}},RK_{3}^{1}\leftarrow {{K}_{6}}, \\ & RK_{4}^{1}\leftarrow {{K}_{13}},RK_{5}^{1}\leftarrow {{K}_{14}},RK_{6}^{1}\leftarrow {{K}_{15}},RK_{7}^{1}\leftarrow {{K}_{16}} \\ & RK_{(32)}^{1}\leftarrow RK_{0}^{1}||RK_{1}^{1}||...||RK_{6}^{1}||RK_{7}^{1} \\ & \text{for }i\leftarrow 2\text{ to }36 \\ & \text{ }{{K}_{1}}\leftarrow {{K}_{1}}\oplus S({{K}_{0}}) \\ & \text{ }{{K}_{4}}\leftarrow {{K}_{4}}\oplus S({{K}_{16}}) \\ & \text{ }{{K}_{7}}\leftarrow {{K}_{7}}\oplus 0||CON_{H}^{i-1} \\ & \text{ }{{K}_{19}}\leftarrow {{K}_{19}}\oplus 0||CON_{L}^{i-1} \\ & \text{ }tem{{p}_{0}}\leftarrow {{K}_{0}},tem{{p}_{1}}\leftarrow {{K}_{1}},tem{{p}_{2}}\leftarrow {{K}_{2}},tem{{p}_{3}}\leftarrow {{K}_{3}} \\ & \text{ for }j\leftarrow 0\text{ to }3 \\ & \text{ }{{K}_{j*4}}\leftarrow {{K}_{j*4+4}},{{K}_{j*4+1}}\leftarrow {{K}_{j*4+5}} \\ & \text{ }{{K}_{j*4+2}}\leftarrow {{K}_{j*4+6}},{{K}_{j*4+3}}\leftarrow {{K}_{j*4+7}} \\ & \text{ }{{K}_{16}}\leftarrow tem{{p}_{1}},{{K}_{17}}\leftarrow tem{{p}_{2}},{{K}_{18}}\leftarrow tem{{p}_{3}},{{K}_{19}}\leftarrow tem{{p}_{0}} \\ & \text{ }RK_{0}^{i}\leftarrow {{K}_{1}},RK_{1}^{i}\leftarrow {{K}_{3}},RK_{2}^{i}\leftarrow {{K}_{4}},RK_{3}^{i}\leftarrow {{K}_{6}}, \\ & RK_{4}^{i}\leftarrow {{K}_{13}},RK_{5}^{i}\leftarrow {{K}_{14}},RK_{6}^{i}\leftarrow {{K}_{15}},RK_{7}^{i}\leftarrow {{K}_{16}} \\ & \text{ }RK_{(32)}^{i}\leftarrow RK_{0}^{i}||RK_{1}^{i}||...||RK_{6}^{i}||RK_{7}^{i} \\ & R{{K}_{(32\times 36)}}\leftarrow RK_{(32)}^{1}||RK_{(32)}^{2}||...||RK_{(32)}^{35}||RK_{(32)}^{36} \\ \end{align}\]
1.2.2 TWINE-128的密钥编排算法

将128bit的主密钥K分为32块,迭代更新后每轮选择32bit作为相应轮子密钥,具体生成算法如下:

$\begin{align} & {{K}_{0}}||{{K}_{1}}||...||{{K}_{30}}||{{K}_{31}}\leftarrow K \\ & RK_{0}^{1}\leftarrow {{K}_{2}},RK_{1}^{1}\leftarrow {{K}_{3}},RK_{2}^{1}\leftarrow {{K}_{12}},RK_{3}^{1}\leftarrow {{K}_{15}}, \\ & RK_{4}^{1}\leftarrow {{K}_{17}},RK_{5}^{1}\leftarrow {{K}_{18}},RK_{6}^{1}\leftarrow {{K}_{28}},RK_{7}^{1}\leftarrow {{K}_{31}} \\ & \text{for}\ \ i\leftarrow 2\ \text{to}\ 36 \\ & \text{ }{{K}_{1}}\leftarrow {{K}_{1}}\oplus S({{K}_{0}}) \\ & \text{ }{{K}_{4}}\leftarrow {{K}_{4}}\oplus S({{K}_{16}}) \\ & \text{ }{{K}_{23}}\leftarrow {{K}_{23}}\oplus S({{K}_{30}}) \\ & \text{ }{{K}_{7}}\leftarrow {{K}_{7}}\oplus 0||CON_{H}^{i-1} \\ & \text{ }{{K}_{19}}\leftarrow {{K}_{19}}\oplus 0||CON_{L}^{i-1} \\ & \text{ }tem{{p}_{0}}\leftarrow {{K}_{0}},tem{{p}_{1}}\leftarrow {{K}_{1}},tem{{p}_{2}}\leftarrow {{K}_{2}},tem{{p}_{3}}\leftarrow {{K}_{3}} \\ & \text{ for}\ \ j\leftarrow 0\ \text{to}\ 6 \\ & \text{ }{{K}_{j*4}}\leftarrow {{K}_{j*4+4}},{{K}_{j*4+1}}\leftarrow {{K}_{j*4+5}} \\ & \text{ }{{K}_{j*4+2}}\leftarrow {{K}_{j*4+6}},{{K}_{j*4+3}}\leftarrow {{K}_{j*4+7}} \\ & \text{ }{{K}_{28}}\leftarrow tem{{p}_{1}},{{K}_{29}}\leftarrow tem{{p}_{2}},{{K}_{30}}\leftarrow tem{{p}_{3}},{{K}_{31}}\leftarrow tem{{p}_{0}} \\ & \text{ }RK_{0}^{i}\leftarrow {{K}_{2}},RK_{1}^{i}\leftarrow {{K}_{3}},RK_{2}^{i}\leftarrow {{K}_{12}},RK_{3}^{i}\leftarrow {{K}_{15}},RK_{4}^{i}\leftarrow {{K}_{17}}, \\ & RK_{5}^{i}\leftarrow {{K}_{18}},RK_{6(4)}^{i}\leftarrow {{K}_{28}},RK_{7}^{i}\leftarrow {{K}_{31}} \\ & \text{ }RK_{(32)}^{i}\leftarrow RK_{0}^{i}||RK_{1}^{i}||...||RK_{6}^{i}||RK_{7}^{i} \\ & R{{K}_{(32\times 36)}}\leftarrow RK_{(32)}^{1}||RK_{(32)}^{2}||...||RK_{(32)}^{35}||RK_{(32)}^{36} \\ \end{align}$
2 中间相遇攻击框架

本文中使用的中间相遇攻击方案将Biclique初始结构与三子集中间相遇相结合,前后向独立计算得到部分匹配位置的值,进而通过是否匹配来达到删减密钥的目的,从而形成单密钥下优于穷举的攻击方案.下文中提到的前向(后向)过程的中立比特是指前向(后向)的计算过程与此比特无关.

文中使用到的中间相遇攻击的具体攻击模式如图2所示,过程描述如下:

图2 中间相遇攻击框架 Fig.2 General structure of meet-in-the-middle attack

· 第1阶段:中间相遇阶段.

1. 将k比特的主密钥分为3块,分别为A0,A1A2,共用比特位置记为A0,前向过程和后向过程的中立比特分别为A1,A2.一般情形下,A1,A2的规模是一样的,我们记|A1|=|A2|=d,用i,jÎ{0,1}d标识集合A1,A2中的各个密钥;

2. 遍历A0的所有可能的值,此时主密钥中只有A1,A2未知,用主密钥K[i,j]来表示A1=i,A2=j:

2.1 建立Biclique过程:

I. 任选明文P0在密钥K[0,0]下加密得到S0的值;

II. 在密钥K[0,j]下加密P0得到Sj的值;与步骤I相比,这是密钥A2活跃的一条差分传播路径;

III. 在密钥K[i,0]下解密S0得到Pi的值;与步骤I相比,这是密钥A1活跃的一条差分传播路径;

IV. 如果两条差分路径没有相交的非线性组件,则成功建立Biclique结构.即:任意的i,jÎ{0,1}d,均有${{P}_{i}}\xrightarrow{K[i,j]}{{S}_{j}};$

2.2 部分匹配过程:

I. 遍历Sj,在未知A1的情形下,向前计算得到匹配位置u的值并将(Sj,u)保存到表1中;

表1 中立比特对TWINE-80密钥编排算法的影响 Table 1 Key schedule of TWINE-80 influenced by neutral bits

II. 询问加密Oracle,得到Pi对应的密文Ci.对每一个Ci,在未知A2的情形下,向后计算得到v的值,在表1中寻找是否有u=v匹配:如果有,则将对应的(i,j)作为候选密钥.

· 第2阶段:密钥穷搜阶段.

设密码算法总的密钥长度为k,部分匹配位置的长度为b,则上述过程结束之后,存活密钥个数为2k-b.借助已知的明密文对验证剩余候选密钥是否为正确的密钥值.

· 第3阶段:复杂度评估.

1. 数据复杂度.

攻击过程需要的数据复杂度取决于Biclique建立过程中需要的选择明文数目.更具体地说,在A1活跃下,反向解密的差分传播路径在明文处的活跃比特数决定了整个攻击过程的数据复杂度.设此路径之后明文处活跃比特数为m,则攻击的数据复杂度是2m个选择明密文.

2. 时间复杂度.

整个攻击的时间复杂度主要分为两个部分:中间相遇阶段的时间代价以及密钥穷搜阶段的时间复杂度.

中间相遇阶段分为两步:建立Biclique以及部分匹配.假设Biclique建立轮数为Rb轮,前向部分匹配轮数为Rfor轮,后向部分匹配轮数为Rback轮.针对每一个密钥集合,Biclique的建立过程中使用独立的相关密钥差分路径,两部分的计算均不含有相交的非线性部分,因此两部分的计算代价的加和不超过2d×Rb个轮计算;前向部分匹配的计算过程中,对2d个状态S向前计算了Rfor轮到达部分匹配位置.类似地,后向部分匹配过程中,2d个明文C向后计算了Rback轮得到部分匹配的值.因此,两部分的时间复杂度为2d(Rfor+Rback)个轮计算.以全轮的加密计算量为单位,一个密钥集合中间相遇过程的时间复杂度为

\[{{2}^{d}}\times \left( {{R}_{b}}+{{R}_{for}}+{{R}_{back}} \right)/\left( {{R}_{b}}+{{R}_{for}}+{{R}_{back}} \right)={{2}^{d}}.\]

这一过程总共涉及到${{2}^{|{{A}_{0}}|}}$个密钥集合,因此,中间相遇阶段的时间复杂度不会超过${{2}^{|{{A}_{0}}|+d}}.$

密钥穷搜阶段将使用已有的明密文对候选密钥进行逐个验证,判断其是否为正确密钥.这一阶段的时间复杂度即为中间相遇阶段剩余的候选密钥量2k-b.

因此,整个攻击过程的时间复杂度为$C={{2}^{|{{A}_{0}}|+d}}+{{2}^{k-b}}.$因为全部密钥比特与中立比特长度之间有关系式 k=|A0|+2d,因此,当d>1时,此攻击方法比穷搜攻击有效.

3. 存储复杂度.

在攻击过程中,需要存储的部分为表1所示部分,规模为${{2}^{\min \{|{{A}_{1}}|,|{{A}_{2}}|\}}}={{2}^{d}}$个b比特.

3 TWINE 算法的中间相遇攻击过程 3.1 TWINE-80 算法的 18 轮攻击过程

若将初始主密钥作为恢复目标,中间相遇攻击只能攻击到17轮.为了达到更长的攻击轮数,我们将主密钥迭代更新至提取第8轮子密钥时的密钥状态作为恢复目标,共20个分块80bit的密钥信息.在此基础上,给出18轮的TWINE-80算法的中间相遇攻击结果.按照图2中的标识,我们选择后向匹配过程的中立比特A2的活跃位置为第8轮等价主密钥下的第3个(计数从0开始)密钥分块.相应地,前向过程中的中立比特A1为第1个密钥分块.

3.1.1 中立比特对密钥编排算法的影响

根据TWINE-80算法的密钥编排方案,在给定活跃主密钥比特的情形下,前向后向分别计算得知,从第0轮~第17轮(共18轮)的轮子密钥的活跃模式见表1,表中0表示相应主密钥变化对其没有影响,1表示会随对应密钥的变化而发生变化.

3.1.2 5轮Biclique的建立

为了降低攻击的数据复杂度,我们固定P0为全0比特明文,具体建立过程如图3所示.加密P0得到Sj的值,是密钥A2活跃的一条差分传播路径,如图3上所示;类似地,解密S0得到Pi的值,是密钥A1活跃的一条差分传播路径,如图3下所示.经验证可知,图3中上下两条差分路径没有相交的S盒部分,这样我们就成功建立了5轮的Biclique结构,即:任意的i,jÎ{0,1}d,均有${{P}_{i}}\xrightarrow{K[i,j]}{{S}_{j}}.$此过程中选择明文的数量决定了整个攻击过程中的数据复杂度,通过图3下可知:明文状态初始为全0,扩散结果只有0,1,3,11共4个子块活跃,则攻击过程中需要的明文在其余12个字节位置均与P0的值相同,均为0;更进一步地,选择明密文个数至多为216.

图3 TWINE-80中5轮Biclique的建立 Fig.3 Construction of 5-round Biclique in TWINE-80
3.1.3 13轮的中间相遇过程

在Biclique建立成功之后,我们再进行部分匹配的过程.匹配位置选择在第10轮输入的第12个字节,从前后向分别计算部分匹配位置的值,通过是否存在匹配来删减候选密钥.

· 前向过程

具体计算过程如图4上所示.图中蓝色部分表示i未知的情形下导致的未知中间状态位置,由此可知,匹配位置u(第10轮输入的第12个字节位置)的计算不受i部分密钥的影响.此外,为了降低攻击的时间复杂度,只计算图中黄色部分即可得到部分匹配位置的值,共需计算12个S盒.

图4 TWINE-80的部分匹配过程 Fig.4 Partial matching computation of TWINE-80

· 后向过程

具体计算过程如图4下所示.图中红色部分表示j未知导致的未知中间状态位置,同样可知,匹配位置v(第10轮输入的第12个字节位置)的计算不受j部分密钥的影响.类似地,只计算图中黄色部分即可得到v的值,共覆盖27个S盒.

3.1.4 复杂度分析

1. 数据:建立Biclique的过程决定了整个攻击的数据复杂度,需要216选择明密文对;

2. 时间:近年来,对于时间复杂度的计算越来越细致,我们将非线性组件作为最小计算单元,上述攻击的时间复杂度为${{2}^{72}}\left( \frac{{{2}^{4}}(12+4)+40+{{2}^{4}}(12+27)}{18\times 8} \right)+{{2}^{76}}\approx {{2}^{76}}$的18轮TWINE-80加密过程;

3. 存储:只要存储单向过程的结果即可,可以用Hash值索引找到,因此存储24个4bit信息.

3.2 TWINE-128 算法的22轮攻击过程

类似地,我们将提取第8轮子密钥时的128bit作为恢复目标,给出22轮的TWINE-128算法的中间相遇攻击结果.后向匹配过程的中立比特A2的活跃位置为第8轮等价主密钥下的第22个密钥分块.相应地,前向过程中的中立比特A1为第24个密钥分块.

3.2.1 中立比特对密钥编排算法的影响

根据TWINE-128算法的密钥编排算法,前向后向计算得知:从第0轮~第21轮(共22轮)的轮子密钥的活跃模式见表2,其中,0表示相应主密钥变化对其没有影响,1表示会随对应密钥的变化而发生变化.

表2 中立比特对TWINE-128密钥编排算法的影响 Table 2 Key schedule of TWINE-128 influenced by neutral bits
3.2.2 7轮Biclique的建立

建立Biclique的过程与TWINE-80算法类似.通过验证图5中上下两条差分路径没有相交的S盒部分,则可成功建立7轮的Biclique结构.

图5 TWINE-128中7轮Biclique的建立 Fig.5 Construction of 7-round Biclique in TWINE-128

通过图5下可知:明文状态只有13,14,15共3个子块位置活跃,亦即攻击需要的明文在其余13个字节与P0的值相同,均为0.因此,整个攻击过程中需要的选择明密文个数为212.

3.2.3 15轮的部分匹配过程

在Biclique建立成功之后,我们将部分匹配位置选择在第13轮输入的第4个字节位置.从前后向分别计算得到部分匹配位置的值,通过是否匹配来删减密钥.由于受篇幅所限,这里不再详述部分匹配的过程,只简单说明这一过程的计算复杂度,前向过程覆盖19个S盒,后向过程覆盖35个S盒.

3.2.4 复杂度分析

1. 数据:212选择明密文对;

2. 时间:详细计算为${{2}^{120}}\left( \frac{{{2}^{4}}(23+3)+56+{{2}^{4}}(19+35)}{22\times 8} \right)+{{2}^{124}}\approx {{2}^{124}}$的22轮TWINE-128加密过程;

3. 存储:24个4bit信息.

4 与现存攻击结果的比较

现将之前存在的TWINE算法的攻击结果与本文结果相对比,总结为表3.观察表3可知:本文中的攻击结果与之前TWINE算法的结果相比,攻击轮数没有优势,但数据复杂度有很大优势.虽然TWINE算法的Biclique分析均可以使得全轮攻击下的时间复杂度优于穷举攻击,但是Biclique分析可以给出任意算法全轮下的攻击结果,如Present,LED,mCrypton以及LBlock等.因此,Biclique分析结果作为TWINE算法抗中间相遇攻击的结果有些牵强.本文可以看作是首次给出TWINE算法抗传统中间相遇攻击的结果,具体时间、数据以及存储复杂度可见表3.

表3 对TWINE算法分析结果的比较 Table 3 Comparisons of cryptanalysis results on TWINE
5 结束语

本文提出了一种通用的中间相遇攻击模式,并给出了18轮TWINE-80以及22轮TWINE-128算法的攻击结果,攻击时间复杂度分别为276和2124,数据复杂度分别为216和212,这是迄今为止针对TWINE算法攻击中数据复杂度最小的攻击结果.此外,因为Biclique分析可以给出任意算法全轮下优于穷举攻击的结果,所以此中间相遇攻击模式作为设计者评估算法抗中间相遇分析的结果更为合适.类似本文的攻击模式,在解密Oracle情形下也可以建立类似的攻击模式,对应的数据复杂度类型为选择密文.进一步要做的工作是评估其他算法抗此类攻击的结果以及此分析方法的自动化实现.

参考文献
[1] Diffie W, Hellman ME. Special feature exhaustive cryptanalysis of the NBS data encryption standard. Computer, 1977,10(6):74-84.
[2] Sasaki Y. Meet-in-the-Middle preimage attacks on AES Hashing modes and an application to whirlpool. In: Joux A, ed. Proc. of the Fast Software Encryption. Berlin, Heidelberg: Springer-Verlag, 2011. 378-396.
[3] Sasaki Y, Aoki K. Finding preimages in full MD5 faster than exhaustive search. In: Joux A, ed. Proc. of the Advances in Cryptology—EUROCRYPT 2009. Berlin, Heidelberg: Springer-Verlag, 2009. 134-152.
[4] Guo J, Ling S, Rechberger C, Wang H. Advanced meet-in-the-middle preimage attacks: First results on full tiger, and improved results on MD4 and SHA-2. In: Abe M, ed. Proc. of the Advances in Cryptology—ASIACRYPT 2010. Berlin, Heidelberg: Springer-Verlag, 2010. 56-75.
[5] Knellwolf S, Khovratovich D. New preimage attacks against reduced SHA-1. In: Safavi-Naini R, Canetti R, eds. Proc. of the Advances in Cryptology—CRYPTO 2012. Berlin, Heidelberg: Springer-Verlag, 2012. 367-383.
[6] Khovratovich D, Rechberger C, Savelieva A. Bicliques for preimages: Attacks on Skein-512 and the SHA-2 family. In: Canteaut A, ed. Proc. of the Fast Software Encryption. Berlin, Heidelberg: Springer-Verlag, 2012. 244-263.
[7] Li J, Isobe T, Shibutani K. Converting meet-in-the-middle preimage attack into pseudo collision attack: Application to SHA-2. In: Canteaut A, ed. Proc. of the Fast Software Encryption. Berlin, Heidelberg: Springer-Verlag, 2012. 264-286.
[8] Aoki K, Sasaki Y. Preimage attacks on one-block MD4, 63-step MD5 and more. In: Avanzi R, Keliher L, Sica F, eds. Proc. of the Selected Areas in Cryptography. Berlin, Heidelberg: Springer-Verlag, 2009. 103-119.
[9] Wei YZ, Su CM, Ma CB. Meet-in-the-Middle attack on Rijndael-256 algorithm. Computer Engineering, 2012,38(7):107-109 (in Chinese with English abstract).
[10] Wang Z, Zhang WY. Meet-in-Middle attack on 5-round square. Computer Technology and Development, 2011,21(6):132-135, 139 (in Chinese with English abstract).
[11] Bogdanov A, Rechberger C. A 3-subset meet-in-the-middle attack: Cryptanalysis of the lightweight block cipher KTANTAN. In: Biryukov A, Gong G, Stinson D, eds. Proc. of the Selected Areas in Cryptography. Berlin, Heidelberg: Springer-Verlag, 2011. 229-240.
[12] Bogdanov A, Khovratovich D, Rechberger C. Biclique cryptanalysis of the full AES. In: Lee D, Wang X, eds. Proc. of the Advances in Cryptology—ASIACRYPT 2011. Berlin, Heidelberg: Springer-Verlag, 2011. 344-371.
[13] Canteaut A, Naya-Plasencia M, Vayssière B. Sieve-in-the-Middle: Improved MITM attacks. In: Canetti R, Garay J, eds. Proc. of the Advances in Cryptology—CRYPTO 2013. Berlin, Heidelberg: Springer-Verlag, 2013. 222-240.
[14] Lee C. Biclique cryptanalysis of PRESENT-80 and PRESENT-128. The Journal of Supercomputing, 2014,70(1):95-103.
[15] Jeong K, Kang H, Lee C, Sung J, Hong S, Lim J. Weakness of lightweight block ciphers mCrypton and LED against Biclique cryptanalysis. In: Proc. of the Peer-to-Peer Networking and Applications. 2013. 1-17.
[16] Wang Y, Wu W, Yu X, Zhang L. Security on LBlock against Biclique cryptanalysis. In: Lee D, Yung M, eds. Proc. of the Information Security Applications. Berlin, Heidelberg: Springer-Verlag, 2012. 1-14.
[17] Isobe T, Shibutani K. Security analysis of the lightweight block ciphers XTEA, LED and Piccolo. In: Susilo W, Mu Y, Seberry J, eds. Proc. of the Information Security and Privacy. Berlin, Heidelberg: Springer-Verlag, 2012. 71-86.
[18] Suzaki T, Minematsu K, Morioka S, Kobayashi E. TWINE: A lightweight block cipher for multiple platforms. In: Knudsen L, Wu H, eds. Proc. of the Selected Areas in Cryptography. Berlin, Heidelberg: Springer-Verlag, 2013. 339-354.
[19] Çoban M, Karakoç F, Boztaş Ö. Biclique cryptanalysis of TWINE. In: Pieprzyk J, Sadeghi AR, Manulis M, eds. Proc. of the Cryptology and Network Security. Berlin, Heidelberg: Springer-Verlag, 2012. 43-55.
[20] Bouillaguet C, Derbez P, Fouque PA. Automatic search of attacks on round-reduced AES and applications. In: Rogaway P, ed. Proc. of the Advances in Cryptology—CRYPTO 2011. Berlin, Heidelberg: Springer-Verlag, 2011. 169-187.
[21] Bouillaguet C, Derbez P, Dunkelman O, Fouque P, Keller N, Rijmen V. Low-Data complexity attacks on AES. IEEE Trans. on Information Theory, 2012,58(11):7002-7017.
[22] Wang Y, Wu W. Improved multidimensional zero-correlation linear cryptanalysis and applications to LBlock and TWINE. In: Susilo W, Mu Y, eds. Proc. of the Information Security and Privacy. Springer-Verlag, 2014. 1-16.
[23] 韦永壮,苏崇茂,马春波.Rijndael-256算法的中间相遇攻击.计算机工程,2012,38(7):107-109.
[24] 王哲,张文英.对5轮Square的中间相遇攻击.计算机技术与发展,2011,21(6):132-135,139.