改进的减轮MIBS-80密码的中间相遇攻击

任炯炯 侯泽洲 李曼曼 林东东 陈少真

(战略支援部队信息工程大学 郑州 450001)

1 引言

随着物联网新技术的突破式发展，万物联网的需求使得无线传感器、智能卡和射频识别(Radio Frequency IDentification， RFID)标签等受限设备的应用越来越广泛。轻量级分组密码广泛应用于这类资源受限环境下的数据安全和隐私保护，成为密码学研究的热点。MIBS密码算法是Izadi等人[1]在2009年提出的一个整体采用Feistel型，轮函数为代换置换网络(Substitution-Permutation Network，SPN)型结构的轻量级分组密码。其分组长度为64 bit，密钥长度有64 bit和80 bit两种，迭代轮数均为32轮。由于MIBS算法涉及的运算便于硬件实现，占用资源少，MIBS算法广泛适用于物联网和传感器网络等环境，对MIBS密码的分析已备受关注。

对MIBS密码的安全性分析主要集中在传统的差分与线性分析、不可能差分攻击、积分攻击、相关密钥攻击和故障分析等。杨林等人[2]首先以0.99的成功概率给出了13轮MIBS差分分析的结果。Bay等人[3]对MIBS抗差分和线性攻击的能力进行了新的评估。但是，杜承航等人[4]发现文献[3]不可能差分分析的错误并重新给出了12轮不可能差分分析的结果。文献[5]首次利用积分攻击分析了8轮MIBS-64和9轮MIBS-80，随后文献[6，7]给出了10轮MIBS-80积分攻击的结果。刘超等人[8]利用MIBS算法Feistel结构的等价性，构造出6轮中间相遇区分器，并结合轮子密钥与主密钥的关系，首次给出11轮MIBS-80算法的中间相遇攻击。付立仕等人[9]基于MIBS-80中S盒不可能差分和密钥间的制约关系筛选明文对，并利用独立的80-bit轮密钥来恢复主密钥，对13轮MIBS-80进行了不可能差分分析。文献[10，11]从侧信道的角度，分别对MIBS密码进行故障分析和旁路立方攻击。

中间相遇攻击是一种时空折中的攻击方法，首先由Diffie等人[12]在1977年分析双重DES(TWO-DES)时提出，广泛应用于很多主流分组密码的分析[13–15]。其主要思想是将密码算法分解成两部分，首先建立选择明文经过前半部分加密对应的筛选集合，接着猜测相关的密钥，正向加密和逆向解密明密文对的若干字节和比特，判断是否构成中间数据的碰撞，进而形成有效的攻击。中间相遇攻击需要大量的预计算和时间复杂度，虽然预计算只需要计算1次，但如果涉及的猜测密钥太多，就会超过穷举复杂度。因此如何减少预计算的参数个数，减少需要猜测的密钥量，降低时间复杂度，是亟需解决的问题。

Dunkelman等人[16]在亚密会(ASIACRYPT)2010年分析高级加密标准(Advanced Encryption Standard， AES)时，引入多重集并利用有效的差分枚举手段，大大降低了中间相遇攻击预计算阶段涉及的参数数量。此外还发现存储差分筛选集合的有效方法，降低了存储复杂度。总的来说，文献[16]对AES中间相遇攻击的思想具有里程碑式的进步。2013年欧密会，Derbez等人[17]在Dunkelman基础上，借鉴“rebound-like”思想，证明了文献[16]预计算阶段满足截断差分路径的多重集参数不会全部取遍，进而再次降低了区分器涉及的参数，给出了7轮AES-128和8轮AES-192中间相遇攻击的最好结果。随后，文献[18]利用有效的密钥桥和差分枚举技术，给出了对10轮AES-256的中间相遇攻击，是目前为止针对AES-256攻击轮数最长的单密钥攻击。近年来，随着自动化搜索技术的发展，文献[19，20]给出了中间相遇攻击一般化的搜索模型，可以快速有效地给出典型结构分组密码最优中间相遇区分器。

本文主要研究了针对MIBS密码的中间相遇攻击，首先利用MIBS算法Feistel结构的特点，构造了8轮多重集，多重集的相关位置比特由28个半字节决定，超过穷举的计算复杂度。接着通过研究MIBS算法S盒和截断差分的性质，利用有效的枚举技术，剔除中间重复计算的变量，将预计算的参数由28个减少到15个，降低预计算复杂度，构造了8轮中间相遇区分器。最后给出MIBS算法差分传递的性质，结合轮密钥与主密钥的关系，首次实现了13轮MIBS-80算法的中间相遇攻击，需要的数据复杂度为253个选择明文，时间复杂度为262次13轮加密运算。此外，利用8轮中间相遇区分器，结合MIBS算法的部分差分传递性质，攻击了12轮MIBS-80算法，所需时间复杂度为253.2次12轮加密运算。表1列出了针对MIBS-80算法单密钥攻击的主要结果。

表1 MIBS-80算法单密钥攻击结果比较

本文的结构安排如下：第2节简要介绍MIBS密码算法；第3节给出2个定理，构造8轮中间相遇区分器；第4节给出差分传递和密钥扩展算法的相关性质，具体描述13轮MIBS-80密码中间相遇攻击的过程；第5节利用第3节和第4节的部分结果，简要介绍12轮MIBS-80密码中间相遇攻击的结果；第6节总结全文。

2 MIBS密码算法

2.1 MIBS加密算法

分组密码MIBS算法[1]是Feistel结构的密码体制，分组长度为64 bit，支持的密钥长度有64 bit和80 bit两种，加密轮数均为32轮。MIBS中间状态的操作以4 bit为1个单位，称为半字节。轮函数F函数为SPN型，包括密钥加、S盒变换以及线性P置换。

2.2 MIBS-80算法的密钥生成算法

设80 bit的主密钥K=(k79，k78，...，k0)， state0是初始密钥K，s tatei表示第i轮的密钥扩展状态，statei[a～b] 表 示s tatei从 高 比 特a到 低 比 特b的a-b+1bit。则由主密钥生成32个32 bit的轮子密钥Ki(1≤i ≤32)的具体过程为

3 MIBS密码算法8轮中间相遇区分器

本节首先针对MIBS中间状态的半字节运算，给出MIBS算法δ-集的定义，再按照其Feistel结构特点构造多重集得到定理1，其相关位置比特由28个半字节决定，超过了穷举的计算复杂度。接着研究MIBS算法S盒的性质，利用有效的差分枚举技术得出定理2，构造了有效的8轮中间相遇区分器。

图1 第i轮符号说明示意图

图2 8轮MIBS算法的截断差分路径

4 13轮MIBS-80密码算法的中间相遇攻击

本节利用第3节构造的8轮中间相遇区分器，前面加2轮，后面加3轮，构成13轮的攻击路径，如图3所示。为了减少复杂度，首先利用MIBS算法的差分传递特征，分别从加密方向和解密方向给出性质2和性质3，筛选满足截断差分的明文；接着利用MIBS-80密钥扩展算法中轮密钥与主密钥的关系，减少密钥的猜测量。

图3 13轮MIBS-80密码的中间相遇攻击路径

性质2 对MIBS算法，若第i+ 1轮输入差分ΔAi=(0000000γ)， ΔBi=(00000000)， 则第i+3轮的输出差分满足关系式

4.1 预计算阶段

4.2 在线阶段

4.3 复杂度分析

5 12轮MIBS-80密码算法的中间相遇攻击

本节在第3节定理2的8轮中间相遇区分器基础上，前面加1轮，后面加3轮，进行12轮MIBS-80算法的中间相遇攻击，攻击路径去掉图3中13轮路径的第1轮。与第4节13轮的攻击过程相比，其明文的差分特征不再满足性质3，密文的差分特征依然满足性质2。

6 结束语

本文评估了适用于物联网的密码MIBS算法抵抗中间相遇攻击的安全性。与其他针对Feistel结构的密码分析工作相比，本文充分利用MIBS算法的结构特点，构造8轮多重集。进一步，利用MIBS算法S盒的性质和有效的差分枚举技术，减少了8轮中间相遇区分器的参数，从而首次实现了对12轮和13轮MIBS-80密码的中间相遇攻击。攻击过程利用差分传递的性质筛选明文对，利用轮密钥与主密钥的关系，减少了密钥猜测量，降低了时间复杂度。该攻击方法明显优于文献[8]中间相遇攻击的结果。与其他攻击方法相比，在时间复杂度和选择明文量上也有整体优势。本文的攻击思想同样适用于其他Feistel-SP结构的典型密码算法的分析，如 Camellia，E2算法等。如何结合自动化搜索算法构造较长轮数的区分器，并加大密钥筛选的力度将是下一步值得研究的工作。