Robin 算法一个新的不可能差分攻击*

王佳琳 欧海文 施 瑞

1.西安电子科技大学，西安市 710071

2.北京电子科技学院，北京市 100070

1 引言

对称密码按照加解密机制不同可以分为分组密码和流密码[1]，本文研究分组密码中的Robin 算法[2]。 对分组密码算法的安全性分析主要包括以下三个方面[1]:一是使用数学知识和计算机工具分析，二是结合物理环境进行分析，三是研究算法在工作模式下的安全性。 其中从物理实现角度，对密码算法通过载体芯片运行时捕获的信息进行分析被称为间接分析，又称为侧信道分析或旁路攻击[3，4]。 基于抵抗侧信道分析的考量，Grosso 等人[2]于2014 年在FSE(快速软件加密)会议上设计了一类基于LS 设计的新的算法族。 该算法族采用比特切片设计，并给出了两个具体的分组密码算法。 其中一个就是采用SPN(Substitution Permutation Network)结构的对合分组密码算法Robin 算法。 所谓对合是指其线性组件和非线性组件均是对合的，即加解密的结构一样。

不可能差分分析由Knudsen 和Biham 分别独立提出[5，6]，是差分密码分析的一个变种。 与差分分析尽可能凭借高概率的差分特征[7]来恢复密钥不同的是，不可能差分分析是利用概率为零的差分特征，逐渐按部分排除那些会导致概率为零的差分出现的候选密钥，最后在剩下的密钥值中用穷尽搜索的办法可以恢复正确密钥。

目前，Robin 算法的不可能差分攻击结果主要有:2014 年，Grosso 等人在设计文档中基于算法的比特模式，利用中间相错技术构造了3 轮的不可能差分区分器。 该区分器主要是利用中间差分某一比特构造矛盾，该构造方法并未充分利用线性层的信息。 对Robin 算法的不可能差分攻击由设计者在设计文档中构造的3 轮不可能差分区分器进化为了现在的构造4 轮不可能差分区分器、实现共计6 轮的不可能差分攻击，并经历了前人的两次改良:一次是2018 年沈等人[8]将Robin 算法的比特模式等价转换为字节模式，并利用线性层信息通过UID 方法[9]搜索到4 轮不可能差分区分器，达到了不考虑非线性层细节情况下的最优长度；另一次是2021 年沈等人[10]对Robin 算法的4 轮不可能差分区分器充分挖掘轮密钥的信息、降低轮密钥的猜测量后的改进攻击，能够降低约28的时间复杂度，时间复杂度为大约293.97次6 轮加密运算、数据复杂度为2118.8。

根据沈等人在文献[10]中的思路，结合王湘南等人[11]的方法，改变一个约束条件，手工推出并证明本文性质一。 根据性质一利用轮密钥之间的线性关系构造新的区分器形式，降低了选择明文数N，使得数据复杂度降低了大约28，时间复杂度有所上升。 利用提前抛弃技术[12]计算复杂度可知该攻击时间复杂度为大约2118.21次6轮加密运算、数据复杂度为2111.18。

其余部分的结构安排如下:第2 节简要介绍Robin 密码的加密算法；第3 节证明性质一，并构造Robin 算法一条新的4 轮不可能差分区分器；第4 节根据新的4 轮不可能差分区分器，在其首尾各加一轮，攻击6 轮的Robin 算法，并给出攻击的完整步骤及复杂度分析；第5 节是结束语。

2 Robin 算法

2.1 Robin 算法简介

Robin 算法是分组长度为128 比特的SPN型分组密码，密钥比特为128 比特，完整轮数为16 轮。 Robin 每一轮由3 个部件构成:

(1) 混淆层(Substitution Layer，SL). 由16个8×8 的S 盒并置组成，在本文中，S 盒只需要视为双射即可，故S 盒的具体细节不给出，可参见文献[2]。

(2) 扩散层(Diffusion Layer，DL). 扩散层置换是一个将128 比特输入状态看成16 字节，通过乘以16×16 的二元矩阵进行矩阵运算得到16 比特输出状态的线性函数，具体如下:(3) 轮密钥加(Round Key Addition，RKA).由每一轮的输入状态和轮密钥ki两者之间异或构成，轮密钥ki是通过密钥扩展算法得到的。

2.2 符号说明

本文使用的符号及标注如表1 所示。

表1 符号说明

3 Robin 算法的4 轮不可能差分区分器

本文是对Robin 算法的6 轮不可能差分分析，首先根据性质一构造了新的4 轮不可能差分区分器，然后在区分器上添加1 轮前置路径和1轮后置路径，得到6 轮不可能差分攻击路径。

性质一:

如图1 所示，存在一明文对，在第3 字节处差分值非零，其余字节处差分值为零，4 轮变换后，密文对差分特征ΔX4不会是如下形式: (0，f，0，g，f，0，g，0，g，0，f，0，h，0，0，0)。 这一不可能差分性质可用下式表示:

(0，0，0，0，0，0，0，0，0，0，b，0，0，0，0，0)⇒(0，f，0，g，f，0，g，0，g，0，f，0，h，0，0，0)

图1 Robin 算法一个新的4 轮不可能差分区分器

其中f，g为任意非零值，f≠g且h＝f⊕g。

证明:

先从前两轮正推。 明文对的输入状态满足(0，0，0，0，0，0，0，0，0，0，b，0，0，0，0，0)， 经过第一轮SL运算，差分特征变为: (0，0，0，0，0，0，0，0，0，0，c，0，0，0，0，0)。 其中，c为非零字节。

经过第一轮DL运算，差分特征为: (c，c，0，0，c，c，0，0，0，0，0，0，c，c，0，c)， 经过第一轮的RKA运算后，因RKA运算不改变差分，所以差分没有发生改变。

再进行第二轮SL运算，第二轮的输入差分可第一轮的输出差分相同，SL运算后差分特征为: (d0，d1，0，0，d4，d5，0，0，0，0，0，0，d12，d13，0，d15)。 接下来进行第二轮的DL运算和RKA运算后，差分特征为: (e0，e1，e2，e3，e4，e5，e6，e7，e8，e9，e10，e11，e12，e13，e14，e15)。

其中有e2＝e8＝d0⊕d5⊕d13⊕d15。

再推导(0，f，0，g，f，0，g，0，g，0，f，0，h，0，0，0) 经过两轮逆变换的过程。

经过第四轮DL－1运算和RKA－1运算，差分特征为:(0，h，0，0，h，0，0，0，0，0，h，0，f，0，g，0)。

经过第四轮SL－1运算，差分特征为: (0，g1，0，0，g4，0，0，0，0，0，g10，0，g12，0，g14，0)。

再进行第三轮DL－1运算和RKA－1运算，差分特征为:

(f0，f1，f2，f3，f4，f5，f6，f7，f8，f9，f10，f11，f12，f13，f14，f15)。

其中f2＝0，f8＝g14，且g1，g4，g10，g12，g14为非0 值。

最后经过第三轮SL－1运算后，差分特征为:

4 对Robin 算法的6 轮不可能差分攻击过程

本节在第3 节已证明的4 轮不可能差分区分器上添加1 轮前置路径和1 轮后置路径，得到6 轮不可能差分攻击路径，如图2 所示。 Robin的1 轮加密由SL、DL和RKA组成(在最后一轮中省略了DL)，SL、DL和RKA的每一次加密等于1/3 次1 轮加密。

图2 6 轮Robin 算法一条新的不可能差分分析路径

4.1 攻击步骤

步骤1. 定义一个在字节(2，3，6，7，8，9，10，11，14)处差分为0，在其余字节(0，1，4，5，12，13，15)处取遍0～127 的明文空间结构，这样的空间中含有28×(16－9)＝256个明文。 每个结构中明文对共有256× 256× 1/2＝2111个。

步骤2. 取2N个上述结构，选取密文对中在(0，2，5，7，9，10，13，14，15)这9 个字节处差分为0，剩余密文对有2N＋111× 2－8×9＝2N＋39个。

步骤3. 假设步骤2 中保留下来的密文对为(C，C′)，猜测密钥k7的7B (k7，1，k7，3，k7，4，k7，6，k7，8，k7，10，k7，12)，在计算复杂度时，只需要计算7B 的值的复杂度。

步骤3.3. 猜测密钥(k7，12)，计算:

步骤4. 猜测密钥k1的7B，使保留下来的密文对相应的明文对为(P，P′)。

根据k1和k7的关系[10]，有k7，10＝k1，0＋k1，1＋k1，4＋k1，5＋k1，12＋k1，13＋k1，15。 由于k7，10在步骤3 中已经猜过了，故可减少猜测任1B 的k1，i值，其中i＝0，1，4，5，12，13，15。

4.2 复杂度分析

下面在分析时间复杂度时采用了密钥恢复的提前抛弃技术。

本节步骤3 中只需要计算7B 的值，所以这一步骤需要2× (2N＋39× 216＋2N＋31× 224)×3/16＋2×224×(2N＋23×216＋2N＋15×224)×3/16＋2×248×(2N＋7×28)×1/16 ≈2117.99次1 轮解密运算。

在步骤4 需要256× 2× (28× 2N－1＋216×2N－9＋…＋248× 2N－41)× 7/16＝21× 2N＋61≈2120.57次1 轮加密。

Robin 算法1 轮加密运算和1 轮解密运算的时间复杂度相当，所以恢复96 比特密钥信息所需要的时间复杂度为:

(2117.99＋2120.57)×1/6 ≈2118.21次6 轮加密。

种子密钥信息是128 比特，上述攻击能够恢复其中104 比特信息，剩下的24 比特密钥信息可通过穷尽搜索得到。 因而总的时间复杂为度为:2118.21＋224≈2118.21。

综合而言，6 轮的攻击复杂度为: 256＋N＝256＋55.18≈2111.18数据复杂度和时间复杂度为大约2118.21次6 轮加密运算。

5 结束语

本文提出了一条新的4 轮不可能差分区分器，在第4 部分中根据Robin 算法的结构特征，在新的4 轮不可能差分区分器上添加了1 轮前置路径和1 轮后置路径，实现了6 轮Robin 算法的不可能差分攻击。 此路径下，该攻击时间复杂度为大约2118.21次6 轮加密运算、数据复杂度为2111.18。 表2 列出了本文的攻击结果并比较了以往相关文献的数据结果。

表2 Robin 算法的不可能差分分析的安全性总结