RAIN-128算法的中间相遇攻击

杜小妮 郑亚楠 梁丽芳 李锴彬

①(西北师范大学数学与统计学院 兰州 730070)

②(西北师范大学密码技术与数据分析重点实验室 兰州 730070)

③(西北师范大学计算机科学与工程学院 兰州 730070)

1 引言

近年来，随着射频识别技术和无线传感器的发展与应用，为了保障这些资源受限设备中的信息安全，功耗低和软硬件实现面积小的轻量级分组密码算法被广泛应用。然而轻量级分组密码算法追求低功耗与高效率并存，这一矛盾会使算法的安全性无法得到保证，因此对轻量级分组密码算法进行安全性分析是非常有必要的。

1977年Diffie和Hellman[1]提出中间相遇攻击的思想，并将其应用到DES[2]的安全性分析中，之后广泛应用于Feistel结构的密码算法分析中；随后在FSE 2008上Demirci和Selçuk[3]利用文献[1]的思想，构造了AES[4]的4轮中间相遇区分器，首次提出了8轮AES-256的中间相遇攻击，是目前针对SPN结构分组密码最经典的中间相遇攻击，一般称之为Demirci-Selçuk中间相遇攻击(DS-MITM)；2010年，Dunkelman等人[5]利用差分枚举技术、多重集技术和密钥桥技术对文献[3]方法进行了改进，降低了复杂度；随后Derbez等人[6]通过搜索得到了大量减轮AES-256的高效路径，进一步降低了复杂度。在ASIACRYPT 2018上，Shi等人[7]首次将自动化搜索模型与算法的相关约束条件结合，实现了SKINNY[8]的22轮中间相遇攻击；2020年，Chen等人[9]利用密钥桥技术，使得密钥恢复攻击的复杂度有所降低；为了进一步降低算法的复杂度，肖钰汾等人[10]在2021年对SKINNY的中间相遇区分器进行自动化搜索时，将搜索过程中一部分状态的猜测转换为密钥的猜测，同时结合密钥桥技术，降低了密钥的猜测量和区分器的存储复杂度。

截断差分分析[11]是差分分析[12]的一个变体。与经典差分分析考虑具体差分值不同，截断差分只考虑差分的一部分性质，比如差分落在某个集合里，差分的某一位为0等。

RAIN是由曹梅春等人[13]于2021年提出的一种面向软硬件和门限实现的轻量级分组密码算法，并额外的调柄输入形成可调分组密码，增加了算法的灵活性。具有类似结构的算法还包括QARMA[14]，CRAFT[15]等。设计者从差分分析[12]、不可能差分分析[16]、积分分析[17]和不变子空间分析[18]4个方面对算法进行了安全性评估，结果显示，算法具有较大的安全冗余，在PC, ARM平台和FPGA平台上都具有出色的实现性能。

本文首次对RAIN-128进行中间相遇攻击，表1给出了8轮和10轮攻击的复杂度对比，主要贡献如下：

表1 RAIN算法的8/10轮中间相遇攻击复杂度

(1) 通过分析算法的结构特性和截断差分特征，利用差分枚举技术找到了4轮区分器，实现了8轮中间相遇攻击，使得预计算阶段的时间复杂度为P次8轮加密，存储复杂度为 275bit。

(2) 类似地，利用(1)中的方法找到了6轮区分器，并实现了10轮中间相遇攻击。其中预计算阶段的时间复杂度为2214次10轮加密，存储复杂度为2219bit。

(3) 利用算法的结构特性和等价密钥MC-1(K)，减少了在线攻击阶段状态字节的猜测量，使得在线攻击阶段的时间复杂度为2109次8/10轮加密，数据复杂度是 272个选择明文。

本文结构安排如下：第2节对本文用到的符号进行说明，并简要介绍RAIN算法和DS-MITM攻击；第3节对RAIN-128进行8轮中间相遇攻击；第4节给出RAIN-128的10轮中间相遇攻击；第5节总结全文。

2 预备知识

2.1 符号说明

2.2 RAIN算法介绍

RAIN[13]是一族轻量级分组密码算法，分组长度支持64 bit和128 bit，对应的密钥长度为64 bit和128 bit，迭代轮数为30轮和36轮，分别记为RAIN-64和RAIN-128。

算法的轮函数由列混合、 字节替换、行移位和轮可调密钥加4种运算构成。r轮(r=30/36)算法的整体结构如图1所示，第i轮的轮函数结构如图2所示。将64/128 bit的明文、中间状态、密文统称为密码状态。令M=m0||m1||...||m15表示一个密码状态，对于1≤s ≤15，当分组长度为64 bit时，ms的长度是4 bit，即半字节；当分组长度为128 bit时，ms的长度是8 bit，即一个字节。按照行的顺序，依次将密码状态输入到4×4的矩阵中，其矩阵形式为

图1 RAIN算法的整体结构

图2 RAIN算法的轮函数结构

RAIN-128的加密流程，具体如下：

(1) 初始白化：将明文P与白化密钥K按字节进行异或操作。

(2) 列混合：密码状态左乘矩阵

(3) 字节替换：对密码状态中的16 Byte分别进行S盒替换，采用8 bit的S盒。

(4) 行移位：采用与AES相同的行移位变换，即密码状态的第2～4行分别向左循环移位1 Byte,2 Byte, 3 Byte。

(5) 轮可调密钥加：将轮可调密钥与步骤(4)的输出进行异或操作。

2.3 DS-MITM攻击

在DS-MITM的分析过程中，将r轮加密算法E分解为如图3所示的E0,E1和E2，即E=E2◦E1◦E0。其中E1为加密算法的第r0轮至第r0+r1轮，且为构建的区分器。E0为加密算法的第0轮至第r0-1轮，E2为加密算法的第r0+r1+1轮至第r-1轮。

图3 DS-MITM模型

图4 4轮RAIN-128算法的中间相遇区分器

定义1(δ-集)[3]若RAIN-128的1 Byte遍历256个值，其它15 Byte取固定值，这样的结构被称为δ-集。其中，遍历256个值的字节为活跃字节，其余为非活跃字节。

在图3中，对于区分器E1，首先需确定δ-集活跃字节的位置和区分器输出字节的位置；其次根据δ-集在第r0轮至第r0+r1轮的差分传播路径，以及输出字节在第r0+r1轮至第r0轮的差分传播路径，猜测两条路径在每一轮输入相交的状态值，穷尽所有相交状态值，在第r0+r1轮可得到不同的输出状态/差分集合，将集合存储在哈希表中，构成中间相遇区分器。对于E0，需确定在第r0+r1轮形成δ-集的明文集，并猜测部分轮密钥；然后将明文集加密r轮生成密文，猜测E2的部分轮密钥，对密文进行解密，求得第r0+r1轮固定字节的输出状态/差分，判断状态/差分值是否在区分器的哈希表中；若存在，则判断E0和E2中猜测的密钥为正确密钥，否则为错误密钥，再通过穷举搜索筛选出正确密钥。

3 RAIN-128的8轮中间相遇攻击

本节首先介绍RAIN-128的4轮中间相遇区分器，其次利用该区分器实现了8轮攻击，最后分析了复杂度。

3.1 4轮中间相遇区分器

3.2 8轮RAIN-128的中间相遇攻击

8轮RAIN-128的中间相遇攻击由两个阶段组成：预计算阶段和在线攻击阶段。攻击过程如图5所示。

图5 8轮RAIN-128算法的中间相遇攻击

在线攻击阶段：

(1) 选择28×9=272个明文，这些明文满足在第0, 4, 6, 8, 9, 12, 15Byte处差分为0，其余9 Byte穷尽即可；

(2) 由于列混合与密钥加是线性操作，故可交换这两个操作，具体操作为：

(a)用等价密钥MC-1(K)异或密码状态；

(b) 对(a)中的状态进行列混合(MC)操作。

记u[i]=MC-1(K[i])，则只需猜测u[5],u[10],u[15] 和ATK0[4, 8, 12]，筛选一对明文，使得这对明文在第2轮输入状态差分仅在第0 Byte非0，取其中之一记为P0；

(3) 根据δ-集的性质，以及上述猜测的轮密钥和P0，可反解P1,P2,...,P255。对P0,P1,...,P255进行8轮加密，得到相应密文；

(5) 猜测ATK6[7, 10, 13]。

(6) 利用上述密钥值部分解密第 (3) 步得到的密文，可得W5[0]，计算差分集。判断差分集是否在预计算阶段建立的哈希表T中。若在，则猜测的密钥为正确密钥，否则为错误密钥。

(7) 通过穷尽搜索的方式筛选出正确密钥。

上述攻击步骤中，需要猜测13 Byte，得到18 Byte的密钥：u[5],u[10],u[15] ,ATK0[4, 8,12],ATK6[7 , 10, 13], ATK7[1, 2, 3, 5, 7, 9, 10, 14, 15]。

3.3 攻击复杂度分析

预计算阶段需猜测8 Byte，计算264×28=272个差分值，因此预计算的时间复杂度为264×28×8/(8×16)=268次加密8轮RAIN-128，存储复杂度为(28-1)×8×28×8≈275bit。

在线攻击阶段选择明文量为 272个明文，即数据复杂度为 272个选择明文。在线攻击阶段需猜测1 3 B y t e，因此在线攻击的时间复杂度为2104×28×16/(8×16)=2109次加密8轮算法。

4 10轮RAIN-128的中间相遇攻击

本节实现了RAIN-128 的10轮中间相遇攻击，因攻击过程与第3节类似，故仅给出结论，不再给出证明过程。

首先给出6轮中间相遇区分器的相关结论，区分器如图6所示。

图6 6轮RAIN-128算法的中间相遇区分器

定理3设Z0[0]为活跃字节，,...,}是经过6轮RAIN-1 2 8 加密的输出，若存在明文对(0≤j ≤255)满足图6的截断差分特征，则输出差分由以下39 Byte确定：

定理4若参数满足定理3的条件，且0，则差分集合可分别由以下字节确定：

10轮中间相遇攻击过程及复杂度分析如下。

在线攻击阶段：需要猜测13 Byte。利用算法的结构特性和等价密钥MC-1(K)可推导出18 Byte的密钥：u[5],u[10],u[15] , ATK0[4, 8, 12] ,ATK8[7, 10, 13], ATK9[1, 2, 3, 5, 7, 9, 10, 14, 15]。利用所得密钥值对密文进行部分解密，可得W7[0]，计算差分集。若差分集在预计算阶段建立的哈希表T中，则猜测的密钥为正确密钥，否则为错误密钥，并通过穷尽搜索的方式筛选出正确密钥。因此10轮RAIN-128所需数据复杂度为 272个选择明文，时间复杂度为2104×28×16/(10×16)≈2109次加密10轮算法。

5 结束语

本文将DS-MITM模型与 RAIN-128的一类截断差分特征相结合，构造了RAIN-128的4轮和6轮区分器，并利用该算法的结构特性和差分枚举技术，实现了8轮和10轮的中间相遇攻击。用等价密钥MC-1(K)和算法的结构特性减少了在线攻击需猜测的密钥量，降低了在线攻击阶段的时间复杂度。在攻击的过程中如何减少状态字节的猜测量仍需进一步研究。