Robin算法改进的6轮不可能差分攻击

沈 璇，王欣玫，何 俊，孙志远

国防科技大学 信息通信学院，武汉430010

分组密码算法是对称密码算法中非常重要的一大类。它的安全性分析方法可以分为直接分析和间接分析两种，其中直接分析指的是利用数学、计算机等工具直接对密码算法本身的安全性进行分析[1-3]，而间接分析指的是利用密码算法在密码设备中运行时泄露的信息进行分析[4-6]，间接分析又称为侧信道分析。很多密码学者在设计分组密码算法时，会考虑密码算法对侧信道攻击的抵抗能力。

为了有效抵抗侧信道攻击，2014年，Grosso等人[7]在“快速软件加密”会议上设计了一类新的分组密码算法族——基于LS设计的算法族。该算法族采用比特切片设计，设计者根据该设计思想给出了两个具体的分组密码算法，一个是非对合的分组密码算法Fantomas，另外一个是对合的分组密码算法Robin。Robin算法采用SP结构，其线性组件和非线性组件均是对合的。

不可能差分攻击是目前针对分组密码算法最有效的攻击方法之一，它对包括AES、SMS4、Camellia、ARIA、SIMON、SKINNY、Piccolo等[8-14]在内的许多分组密码算法的安全性分析效果显著。该攻击方法由Knudsen[15]和Biham等人[16]独立提出，它由不可能差分构造和密钥恢复两个阶段组成，其中前者需要构造尽可能长的不可能差分区分器，后者利用已构造的区分器进行密钥恢复得到正确密钥。此外，不可能差分构造阶段得到的区分器除了长度外，区分器的形式同样能够影响最后的攻击效果。

目前，Robin算法的不可能差分攻击结果主要有：2014年，Grosso等人在设计文档中，基于算法的比特模式，利用中间相错技术构造了3轮的不可能差分区分器。该区分器主要是利用中间差分某一比特构造矛盾，该构造方法并未充分利用线性层的信息。为了解决这一问题，充分挖掘线性层的信息构造更长轮数的区分器，2018年，Shen等人[17]将Robin算法的比特模式等价转换为字节模式，并利用UID方法[18]搜索到4轮不可能差分区分器，达到了不考虑非线性层细节情况下的最优长度，该区分器的构造已充分利用了线性层的信息，进一步作者利用该区分器攻击了6轮的算法，攻击的数据复杂度为2119个选择明文，时间复杂度为2101.81次6轮算法加密。与此同时，需要指出的是，作者在进行不可能差分攻击时，没有充分利用轮密钥之间的信息，只是将涉及到的轮密钥看成独立密钥分别进行猜测。若在攻击的过程中能够充分挖掘轮密钥的信息，则能够降低轮密钥的猜测量，进而降低攻击所需的时间复杂度。

为了解决上述线性层和轮密钥信息的利用问题，进一步改进Robin算法不可能差分攻击的结果。

本文首先利用中间相错技术构造了一条新的4轮不可能差分区分器，该区分器长度同样达到了不考虑非线性层细节情况下的最优长度。该区分器的构造充分挖掘了线性层的信息，解决了线性层信息利用问题。进一步，该区分器的形式与文献[17]不同，这使得它在密钥恢复阶段涉及到的轮密钥也不一样。利用新构造的区分器，在进行密钥恢复时，涉及到的轮密钥之间存在线性关系，解决了轮密钥信息利用问题。具体来说，本文利用轮密钥之间的线性关系，在进行密钥猜测时，能够少猜测1个字节的轮密钥量，进而能够降低约28的时间复杂度。

1 Robin算法简介

Robin算法的分组长度为128 bit，密钥长度也为128 bit，总轮数为16轮。该算法采用比特切片设计，在该算法的设计文档中，它是基于比特的形式进行描述。考虑到其作用到每列上的线性层均相同，因此在文献[17]中，作者将该算法的比特描述等价转换为字节描述，这样更有利于区分器的构造。本文也采用基于字节的描述方式。

Robin算法的整体加密流程，如图1所示。

图1 Robin算法的加密流程

明文先与种子密钥进行异或，然后经过16轮轮函数迭代后得到密文。Robin算法的轮函数由三部分组成：S层、L层和KC层。

S层：16个8 bit的S盒并置加密。在本文中，S盒只需要视为双射即可，故S盒的具体细节不给出，可参见文献[7]。

L层：在S层之后，利用一个分支数为8的16×16的二元矩阵作用在128 bit的状态上。若L层的输入为X=(x0,x1,…,x15)，输出为Y=(y0,y1,…,y15)，这里xi、yi(i=0,1,2,…,15)均为8 bit的字节，则线性层L对应的加密变换为：

在Robin算法中，L层是对合的，即L层和L-1层加密变换完全相同。

KC层：种子密钥K和轮常数Con(i)进行异或，再与中间状态异或。这里Con(i)表示第i轮的轮常数，具体取值参见文献[7]。

在本文中，Robin算法的任一128 bit状态X=(x0,x1,…,x15)，这里xi均为8 bit的字节，均按照图2的4×4矩阵形式进行排列。

图2 128 bit状态按照矩阵形式排列

2 Robin算法4轮不可能差分区分器构造

本章利用中间相错技术构造了Robin算法的一条新的4轮不可能差分区分器。注意该区分器的长度达到了不考虑S盒细节情形下的区分器最长轮数。

下面给出Robin算法的新4轮不可能差分区分器：

这里b、h均是非零字节差分。

证明 如图3所示，该命题的证明思路主要是从加密方向看，输入差分经过两轮正向差分传播后，中间差分在第8、9字节处相等；从解密方向看，输出差分经过两轮反向差分传播后，中间差分在对应的第8、9字节处不等，故得矛盾。

图3 Robin算法4轮不可能差分

注意到KC层和KC-1层是通过异或的方式参与加解密的，在差分传播的过程中，它们可以视为常数，不改变差分的值。下面分别从加密方向和解密方向进行详细说明：

（1）加密方向。第2轮的输入差分为：

经过S层后这里b和c均是非零字节差分。再经过L层和KC层后第3轮的输入差分和第2轮的输出差分相同，经过S层后，接着经过L层和KC层后得到的输出差分为：

并且有e8=e9=d0⊕d6⊕d14⊕d15。

（2）解密方向。第5轮的输出差分为：

经过KC-1层和L-1层后：

这里h为非零字节差分。再经过S-1层后：

这里g1、g7、g9、g12均为非零字节差分。第4轮的输出差分和第5轮的输入差分相同，经过KC-1层和L-1层后：

这里f8=0,f9=g12≠0。接着经过S-1层后得到的输入差分为：

综上所述，输入差分从加密方向传播2轮得到的中间差分和输出差分从解密方向传播2轮得到的中间差分在第8、9字节处相矛盾，因此该差分为一条4轮不可能差分。

3 Robin算法6轮不可能差分攻击

考虑到6轮Robin算法的最后一轮存在线性层，本节首先利用等价密钥技术[19]，将Robin算法等价为一个新的算法，这样能够降低不可能差分攻击时最后一轮的密钥猜测量，进而降低攻击的复杂度。接着利用构造的新的4轮不可能差分区分器，在区分器前后各加一轮，攻击6轮的Robin算法。

设6轮Robin算法的明文为P，密文为C，根据Robin算法加密流程知：

图4 6轮Robin算法最后一轮等价变换

此外，根据K′=L-1(K)，考虑K′的第1、7、9、12字节，有如下式子成立：

下面利用上章构造的4轮不可能差分区分器，并结合等价密钥技术，给出6轮Robin算法的不可能差分攻击，如图5所示。

图5 Robin算法的6轮不可能差分攻击

整个攻击的步骤如下：

步骤1选择一个明文结构，该明文结构中的数据满足如下形式：

这里xi(i=0,1,2,…,6)是一个任意可变的字节，ci(i=0,1,2,…,8)是一个固定的字节。则在该明文结构中任取两个明文P0、P*0，它们的异或差分值满足：

这里ai(i=0,6,7,10,11,14,15)表示一个非零的字节差分。该明文结构能够提供28×7=256个明文，能够提供256×256/2=2111组明文对。

步骤2选取2n个上述明文结构，则它们能够提供2n+56个明文，2n+111组明文对，选择使得密文差分满足如下形式的明文对：

这里it(t=1,7,9,12)表示一个非零的字节差分，上述差分形式中有12个字节差分为零，它成立的概率为2-8×12=2-96。此时，经过步骤2后剩下的明密对数量约为2n+111×2-96=2n+15。

步骤3对于上述剩余明密对，猜测最后一轮等价密钥K′的第1、7、9、12字节，即K′1、K′7、K′9、K′12共计32 bit的密钥，计算：

选择使得该差分在第1、7、9、12字节处相等的明密对，上述事件成立的概率为2-8×3=2-24，则经过步骤3后剩下的明密对数量约为2n+15×2-24=2n-9。

步骤4对于上述剩余明密对，猜测种子密钥K的第0、6、7、10、11、14字节，即K0、K6、K7、K10、K11、K14共计48 bit的密钥。

根据K′和K之间的关系，如式（1）中的第一个等式：

故有：

注意到在步骤3中K′1已猜测，当猜测K0、K6、K7、K10、K11、K14后，K15即可得到。进一步，计算：

选择使得该差分在第0、6、7、10、11、14、15字节处相等的明密对，上述事件成立的概率为2-8×6=2-48。若该事件成立，则筛除K′的32 bit和K的48 bit共计80 bit的候选密钥。

因为中间的4轮差分是不可能差分，所以满足该不可能差分输入和输出形式的候选密钥是错误的密钥。当分析完2n-9个密文对后，错误密钥仍然能够保留下来的数目为：

当n=62.8时，

则所有可能的错误密钥被筛除，剩下的密钥即为正确密钥。

复杂度分析。数据复杂度为2n+56=2118.8个选择明文；时间复杂度主要由步骤3和步骤4组成，注意到在步骤3中主要涉及4个S盒解密，而1轮解密涉及16个S盒，结合早夭技术[20]知，步骤3需要：

在步骤4中涉及7个S盒加密，而1轮加密涉及16个S盒，则步骤4需要：

注意到在复杂度计算时，Robin的1轮算法加密和1轮算法解密的时间相当，因此恢复80 bit密钥信息需要的时间复杂度为：

它约为296.55/6≈293.97次6轮算法加密。此外，种子密钥信息是128 bit，上述攻击能够恢复其中80 bit信息，剩下的48 bit密钥信息可通过穷尽搜索得到。故总的时间复杂度为293.97+248≈293.97次6轮算法加密。

4 结果对比

本文通过构造Robin算法新的4轮不可能差分区分器，利用轮密钥之间的关系，攻击了6轮Robin算法，攻击的数据复杂度为2118.8个选择明文，时间复杂度为293.97次6轮算法加密。该结果与已有不可能差分攻击结果的比较如表1所示，表中“—”表示无。从表1可以看出，在区分器构造方面，与文献[17]相同，本文构造的区分器同样达到了4轮，解决了区分器构造中的线性层信息利用问题。但是本文构造的区分器形式与文献[17]不同，这意味着在密钥恢复阶段对应的轮密钥不同；在算法攻击方面，与文献[17]相比，本文同样达到了6轮的攻击轮数，但是本文通过充分挖掘轮密钥之间的关系，解决了文献[17]中轮密钥信息利用不充分的问题。通过建立轮密钥之间的线性关系，使得在攻击的过程中，猜测的轮密钥量减少，攻击所需的复杂度降低。具体来说，本文攻击所需的数据复杂度略低，时间复杂度约为文献[17]的1/256，较大程度地降低了不可能差分攻击所需的时间复杂度。

表1 Robin算法不可能差分攻击总结

5 结束语

本文主要研究了Robin算法的不可能差分性质。通过中间相错技术构造了一条新的4轮不可能差分区分器，该区分器涉及到的轮密钥之间存在线性关系，利用该线性关系，在密钥恢复阶段，相比文献[17]能够少猜测1个字节的轮密钥。本文的攻击结果相比已有最好结果，主要改进了其时间复杂度，使得它约为已有最好结果的2−8。

目前关于Robin算法的不可能差分构造还没有利用到非线性组件S盒的具体细节。下一步通过研究非线性组件的信息，希望构造更长轮数的区分器，进而改进其不可能差分攻击结果。此外，Robin算法与韩国标准算法ARIA相似，希望通过对Robin算法的研究，能够进一步提高对ARIA算法的安全性分析结果。