轻量级密码MANTIS的唯密文故障分析

李 玮，张雨希，谷大武，张金煜，朱晓铭，刘 春，蔡天培，李嘉耀

（1. 东华大学计算机科学与技术学院，上海 201620；2. 上海交通大学计算机科学与工程系，上海 200240；3. 上海市可扩展计算机与系统重点实验室（上海交通大学），上海 200240；4. 上海市信息安全综合管理技术研究重点实验室（上海交通大学），上海 220240）

1 引言

近年来，随着5G 技术对物联网普及的持续推动，智能家居、智能电网、智能交通等应用正给人们的工作、学习和生活带来极大的便利. 然而，如何保护网络中的数据免遭中断、截获、篡改和伪造等威胁，已成为物联网面临的重大安全挑战［1，2］. 由于智能卡、射频识别（Radio Frequency Identification，RFID）技术等存储、计算能力方面的限制，物联网中的数据难以直接采用传统密码兼顾安全性和高效性，因此，轻量级密码一经提出，便受到国内外工业界和学术界的广泛关注［3～9］.

MANTIS 密码是于2016 年美密会上由Beierle 等提出的一种轻量级可调分组密码，具有低延迟、高灵活性等特点，适用于保护物联网中的数据安全［9］. MANTIS密码采用FX 结构和TWEAKEY 框架的设计，分组长度、调柄长度均为64 bit，密钥长度为128 bit，用户可以根据实际需求选择不同的轮数及对应版本，其中轮数r≥3，对应版本记为MANTISr［9～12］. 密码设计者Beierle等［9］分析了该密码抵抗差分分析、线性分析、中间相遇分析、积分分析、滑动分析和不变子空间分析等的能力. 2016 年，Dobraunig 等［13］利用截断差分的多条高概率差分特征，实现了对MANTIS5版本的截断差分分析.2018 年，Eichlseder 等［14］提出寻找半截断差分特征族并计算其概率的通用方法，并对MANTIS6版本进行了分析. 2019 年，Chen 等［15］提出聚类多个差分的通用自动搜索方法，给出了对MANTIS6和MANTIS7的分析结果. 同年，Ankele 等［16］提出了针对使用线性扩展可调密钥的分组密码的零相关攻击，并将其应用于缩减轮的MANTIS8的分析. 2020 年，Beyne 等［17］将积分分析方法应用在MANTIS4版本密码的安全性分析中.表1 列举了针对MANTIS 密码不同版本的多种密码分析结果.

表1 针对MANTIS密码的安全性分析汇总

与上述传统密码分析方法不同，故障分析对物联网中密码的实现安全进行分析.1997 年，Boneh 等［18］首次提出故障分析的概念，并将其应用于RSA 公钥密码的破译. 攻击者通常可以物理上访问运行中的设备，并在执行算法加解密运算时，采用电压毛刺、激光脉冲和异常温度等方式向设备注入故障，干扰设备的工作状态，利用错误输出破译密钥信息. 在故障分析的发展历程中，逐渐衍生出差分故障分析、代数故障分析、线性故障分析、中间相遇故障分析以及唯密文故障分析等方法，对现代密码的安全实现提出了严峻的挑战［19～22］.

在密码分析中，根据攻击者能力由弱到强将攻击假设分成唯密文、已知明文、选择明文和选择密文等攻击. 其中，唯密文攻击对攻击者控制使用算法设备的能力要求最弱、在实际中易实施，倘若在该假设下，攻击者能够成功破解密码，则该密码在其他攻击假设下必将遭受更大的安全威胁. 唯密文故障分析是一种基于唯密文攻击假设的故障分析方法，由Fuhr 等［22］于2013年提出并应用于AES 等密码的分析中，攻击者仅需获取随机故障密文，利用统计分析即可破译出密钥. 在AES 密码的唯密文故障分析中，攻击者可通过错误输出来获取密码的中间状态值，利用平方欧氏距离、汉明重量和极大似然等区分器，结合中间状态的统计信息筛选出AES 密码的原始密钥. 2016 年，Dobraunig 等［23］提出了认证加密算法的统计故障分析，并在智能卡、微控制器等硬件上利用激光和时钟毛刺实现了故障注入，成功破译了基于AES密码原语的认证加密算法. 近年来，李玮等［24～26］结合LED 算法、LBlock 和SIMON 等算法提出了拟合优度、拟合优度-平方欧氏距离、拟合优度-极大似然和拟合优度-汉明重量等多种区分器，适用于代换置换网络（SPN）结构和Feistel 结构密码的安全性分析.

目前，国内外未有公开发表的基于TWEAKEY 框架的可调分组密码算法的唯密文故障分析研究. 与常见的分组密码相比，MANTIS 密码的首尾轮具有白化密钥，再根据密码自身设计细节的分析，攻击者只能通过密钥之间的异或关系来确定密钥的值，此外结合可调分组密码中的调柄设计，无疑增加了密码破译的难度.本文针对MANTIS 密码抵抗唯密文故障分析的安全性进行了分析，并构造了狄利克雷分布-汉明重量和狄利克雷分布-极大似然等新型区分器. 表2 总结了攻击者使用不同区分器分析AES 密码、LED 密码、LBlock 密码、SIMON密码以及MANTIS密码并恢复完整密钥所需的故障数，可以看出狄利克雷分布-汉明重量和狄利克雷分布-极大似然等新型区分器，不仅能以99%及以上的成功率破译MANTIS密码所有版本的完整密钥，而且降低了密钥恢复所需注入的故障数，有效地提升了攻击效率. 该结果为轻量级可调分组密码的实现安全提供了有价值的参考.

表2 AES密码、LED密码、LBlock密码、SIMON密码及MANTIS密码的唯密文故障分析结果比较

2 MANTIS密码简介

2.1 符号说明

记X为明文，Y为密文，Y*为故障密文.

记K为原始密钥，k0和k′0为白化密钥，k1和为轮密钥，其中，=k1⊕α，α为常数.

记r为轮数，2r为算法总轮数，其中，r∈[3，∞).

记T为原始调柄值，ti为第i轮调柄值，TKi=ti⊕k1，且其 中，r∈[3，∞)，i∈[1，2r].

记RCi为 第i轮 轮 常 数，且RC2r+1-i=RCi，其 中，r∈[3，∞)，i∈[1，2r].

记Ri为前向轮函数，R-1i为后向轮函数，R-1i是Ri的逆变换.

记SC，AC，ART，PC，MC，PC-1分别为信元代替、轮常数加、可调密钥加、信元置换、列混合和逆信元置换操作.

记h为调柄的更新函数，h-1为h的逆运算.

记k1[j]，[j]，RC[j]，ISi[j]分别为k1，，轮常 数和 第i轮ART 输 出 的 第j个 半 字 节，其 中，i∈[1，2r]，j∈[0，15].

记⊕为异或操作，∥为连接操作，＞＞、＞＞＞和＜＜＜分别为右移、循环右移和循环左移操作.

2.2 算法描述

轻量级可调分组密码MANTIS 算法由Beierle 等学者在2016 年美密会上提出，采用FX 结构和TWEAKEY框架设计，分组长度和调柄长度均为64 bit，密钥长度为128 bit. 根据轮数不同，该密码分为不同版本，记为MANTISr，总轮数为2r轮，包括r轮前向轮和r轮后向轮，由一不带密钥的中间层连接，有首尾白化密钥，如图1所示.MANTISr的不同版本均使用相同的轮函数，64 bit数据结构采用4×4矩阵，其中，每个单元格为4 bit.

图1 MANTIS密码结构和轮函数

前向轮函数Ri包含如下5种基本运算.

（1）信元代替（SubCells，SC）：使用以4 bit为单位的S盒进行替换，如表3所示.

表3 信元代替表

（2）轮常数加（AddConstant，AC）：与轮常数进行异或操作.

（3）可调密钥加（AddRoundTweakey，ART）：与可调密钥进行异或操作.

（4）信元置换（PermuteCells，PC）：对16 个单元格进行移位.

（5）列混合（MixColumns，MC）：与矩阵M相乘实现，其中，

后向轮函数中包含5 种运算：MC，PC-1，ART，AC和SC. 其中，逆信元置换表如表4所示，MANTISr的加密算法如算法1所示.

表4 逆信元置换表

算法1 MANTISr加密算法输入：X，k0，k′0，TK，α，r输出：Y 1：S=X⊕k0；2：S=S⊕TK0；3：FOR i=1 TO r DO 4： SubCells(S)；5： AddConstant(S，i)；6： AddRoundTweakey(S，TKi)；7： PermuteCells(S)；8： MixColumns(S)；9：END FOR 10：SubCells(S)；11：MixColumns(S)；12：SubCells(S)；13：FOR i=r TO 1 DO 14： MixColumns(S)；15： InvPermuteCells(S)；16： AddRoundTweakey(S，TKi，α)；17： AddConstant(S，i)；18： SubCells(S)；19：END FOR 20：S=S⊕TK0⊕α；21：Y=S⊕k′0.

2.3 密钥编排方案

128 bit 原始密钥K与64 bit 子密钥k0，k1和k′0的关系如下：

其中，k0和k′0为白化密钥，k1为轮密钥.

3 唯密文故障分析

3.1 故障模型和基本假设

本文采用半字节随机故障模型，基本假设如下：

（1）攻击者可在加密过程中注入随机半字节故障，以“与”运算方式对原半字节进行注入；

（2）攻击者能够获得由同一密钥加密得到的故障密文.

图2统计了半字节经随机故障注入后的分布规律.由于比特之间的“与”运算会出现不均匀性，因此注入半字节故障后，结果会出现不均匀分布.

图2 半字节经故障注入后的分布律

3.2 攻击过程

在可调分组密码算法的设计中，调柄通常公开且已知，分为固定和不固定，分别表示每次加密时使用相同或不同的调柄值. 考虑普遍性，本文在调柄不固定时检测MANTIS密码各版本抵御唯密文故障分析的能力，该攻击方法同样适用于调柄固定时的所有情况. 攻击过程主要包含如下3个步骤.

步骤1恢复k1的16 bit相关值和k1⊕k′0的48 bit.

攻击者在倒数第二轮导入随机半字节故障，并获得故障密文. 重复上述操作，攻击者能够收集到一组故障密文用于分析. 攻击者通过分析轮密钥、白化密钥、调柄和故障密文之间的关系，利用调柄、故障密文和猜测的子密钥做解密运算，将故障密文恢复至导入故障时的中间状态. 对于候选密钥比特，攻击者逆推故障密文得到对应的中间状态值，再利用区分器获得最佳区分值，筛选出正确候选密钥比特. 以注入位置在IS2r-1[0]为例，故障扩散路径如图3示，攻击者利用部分候 选 子 密 钥(k1⊕k′0)[5]，(k1⊕k′0)[10]，(k1⊕k′0)[15] 和k1[5]⊕k1[10]⊕k1[15]，可用故障密文恢复出错误半字节IS2r-1[0]，推导公式为

图3 故障导入在倒数第二轮后的扩散路径

通过遍历IS2r-1[0]对应的216个密钥候选值，将每个密钥候选值对应的一组中间状态值分别输入到区分器中，获取216个区分值，再将区分值进行比较，即可得出符合理论分布的一组中间状态，所对应的密钥候选值即为正确密钥候选值. 攻击者通过改变故障注入位置，将故障注入在IS2r-1[1]，IS2r-1[2]和IS2r-1[3]半字节，可 得 到(k1⊕k′0)[1]，(k1⊕k′0)[2]，(k1⊕k′0)[3]，(k1⊕k′0)[4]，(k1⊕k′0)[7]， (k1⊕k′0)[8]， (k1⊕k′0)[9]， (k1⊕k′0)[12]，(k1⊕k′0)[14]以 及k1[1]⊕k1[4]⊕k1[14]，k1[3]⊕k1[9]⊕k1[12]和k1[2]⊕k1[7]⊕k1[8]的值.

步骤2恢复k1的48 bit相关值和k1⊕k′0的16 bit.

攻击者注入随机半字节故障至倒数第三轮，得到故障密文. 以IS2r-2[3]作为注入位置为例，故障扩散路径如图4所示.

图4 故障导入在倒数第三轮后的扩散路径

利用已恢复的k1的相关比特值以及部分k1⊕k′0的值，攻击者可将故障密文恢复至IS2r-2. 以IS2r-2[3]为例，用对应的待猜测子密钥(k1⊕k′0)[0]，(k1⊕k′0)[13]，k1[2]⊕k1[8]⊕k1[13]和k1[0]⊕k1[10]⊕k1[15]，将故障密文恢复至IS2r-2[3]，推导公式可表示为

攻 击 者 依 次 对IS2r-2[3]，IS2r-2[4]，IS2r-2[13]和IS2r-2[10]半字节进行故障注入，每次注入恢复的部分子密钥用于后续的密钥恢复. 重复上述攻击步 骤，攻 击 者 可 以 得 到(k1⊕k′0)[6]，(k1⊕k′0)[11]，k1[7]⊕k1[8]⊕k1[13]，k1[0]⊕k1[5]⊕k1[15]，k1[2]⊕k1[7]⊕k1[13]，k1[3]⊕k1[6]⊕k1[12]，k1[1]⊕k1[11]⊕k1[14]，k1[3]⊕k1[6]⊕k1[9]，k1[1]⊕k1[4]⊕k1[11]，k1[0]⊕k1[5]⊕k1[10]，k1[4]⊕k1[11]⊕k1[14]和k1[6]⊕k1[9]⊕k1[12]的值.

步骤3恢复原始密钥K.

攻击者利用步骤1、步骤2 可以恢复k1的64 bit相关值以及k1⊕k′0的16 个半字节值，可得到关于k1的16 个半字节的方程组和k1⊕k′0的值，具体如下：

其中，bu为已恢复的k1的相关值，u∈[0，15]. 攻击者解出方程组获得k1后，再与k1⊕k′0的值进行异或操作，可得到k′0的值，即k′0=k1⊕(k1⊕k′0).

最后，攻击者通过密钥编排方案恢复MANTIS各版本的原始密钥，即

3.3 区分器

本节使用平方欧氏距离、汉明重量等7种现有区分器及2 种新型区分器对MANTIS 密码进行唯密文故障分析.2013 年，Fuhr 等［22］首次提出平方欧式距离、汉明重量和极大似然区分器对AES 密码进行唯密文故障分析. 近年来，李玮等［24，26］针对LED等密码提出了拟合优度、拟合优度-平方欧氏距离、拟合优度-极大似然和拟合优度-汉明重量等区分器，降低了故障注入数. 本节提出了狄利克雷分布-极大似然和狄利克雷分布-汉明重量新型区分器. 各区分器的原理及取值如表5所示.新型区分器原理如下所述.

表5 各区分器对比

（1）狄利克雷分布-极大似然区分器

狄利克雷分布（Dirichlet Distribution，DD）区分器通过计算在理论分布下中间状态值得到的概率筛选出一组最符合理论分布的状态，概率值DD 越越大，候选密钥为真实密钥的可能性越大.DD值可表示为

狄利克雷分布-极大似然（Dirichlet Distribution-Maximum Likelihood，DD-ML）区分器是结合DD 区分器和ML 区分器的双重区分器，攻击者依次计算DD 值和ML 值，从DD 区分值较佳结果中取ML 的最大值，即为最可能的候选密钥，ML计算式为

其中，n为导入故障数，ISv为第v个中间状态值，O［m］表示中间状态值中值为m的个数，D［m］表示中间状态值为m的理论概率.

（2） 狄利克雷分布-汉明重量区分器

狄利克雷分布-汉明重量（Dirichlet Distribution-Hamming Weight，DD-HW）区分器首先计算在理论分布下中间状态值得到的概率，得到较大概率对应的一组中间状态，然后在这一组中间状态中进行进一步的筛选，以减少所需故障数．攻击者首先利用DD 区分器筛选出一组高概率值的候选值，计算式为

然后利用HW区分器筛选出最小值，计算式为

其中，n为导入故障数，ISv为第v个中间状态值，hw为汉明重量值的计算函数，O［m］表示中间状态值中值为m的个数，D［m］表示中间状态值为m的理论概率.

4 实验分析

本实验在Intel Core Processor（Broadwell，no TSX，IBRS），Ubuntu 21.04，2.4GHz计算机服务器上运行，采用C++编程语言实现对MANTIS 密码的唯密文故障分析. 攻击者采用计算机软件生成半字节随机故障并模拟故障注入，使用“与”运算的方式对原中间状态的指定位置产生影响，再使用各区分器恢复原始密钥. 由于MANTISr的不同版本仅有加密轮数的区别，轮函数和密钥编排均相同，使得从故障密文倒推至注入故障的中间状态的过程也相同，因此相同区分器恢复MANTIS密码各版本原始密钥的效果相同.

本实验以MANTIS8为例，利用SEI，HW，ML，GF，GF-SEI，GF-ML 和GF-HW 区分器以及DD-ML，DD-HW 新型区分器进行统计分析. 在攻击过程中，每次统计分析可恢复16 bit 子密钥的信息，在倒数第二轮和倒数第三轮先后分别注入半字节故障，用于恢复128 bit原始密钥. 图5、图6和表6展示了针对MANTIS8版本的攻击结果，所有结果均为1000 次实验后的统计结果.

图6 各区分器恢复16 bit密钥的耗时

4.1 故障数

在故障攻击中，攻击算法需要注入的故障数越少，在实际硬件实现时越具有优势. 表6 给出了恢复MANTIS8完整密钥且成功率达到99%及以上时，各区分器所需的故障注入数. 本文提出的DD-HW 和DDML 双重区分器分别需要392 个和396 个故障数，与现有区分器相比，所需故障数较少. 其中，SEI区分器对每一个中间状态值统计所得的个数采用了相同的处理系数，故中间状态值与统计所得个数间映射关系的改变不会影响区分值大小，同时，异或操作会导致这个映射关系发生变化. 因此，如果待分析的中间状态值是通过故障密文与待猜测密钥候选值直接异或所得的，那么SEI区分器无法起到区分效果.

表6 各区分器恢复完整密钥所需故障数、时间复杂度和数据复杂度

4.2 成功率

成功率指成功恢复密钥的次数占实验次数的比例. 在故障分析中，若候选密钥经区分器筛选后得到唯一候选密钥且该候选密钥与真实密钥值相同，那么该次密钥恢复实验成功. 恢复完整密钥需进行两阶段攻击，依次在加密的倒数第二轮和倒数第三轮分别注入故障，由于注入故障轮数不同，故障对加密过程的影响不同，导致区分器恢复密钥的成功率不同，因此图5（a）和（b）分别展示在倒数第二轮和倒数第三轮注入故障时不同区分器的攻击效果，即子密钥恢复成功率与导入故障个数的关系，其中横坐标为故障注入数，纵坐标为子密钥恢复成功率. 为了减少第一阶段攻击对第二阶段攻击的实验数据的影响，第二阶段攻击的实验数据在第一阶段攻击待恢复子密钥已知的基础上进行统计. 从数据可以看出，HW，ML，GF，GF-SEI，GF-ML，GF-HW，DD-ML 和DD-HW 区分器均可以99%及以上的成功率恢复MANTIS密码原始密钥. 鉴于SEI 区分器成功率最高不超过20%，实际攻击时不建议采用SEI区分器.

图5 各区分器恢复16 bit密钥的成功率

4.3 复杂度

时间复杂度和数据复杂度是衡量密码破译的时间量和数据量的重要指标，其计算式分为

和

其中，f1和f2分别为两阶段攻击中注入的故障数，ω为不同区分器对应的复杂度系数. 表6 给出了不同区分器以不小于99%的成功率恢复MANTIS8完整密钥所需的时间复杂度和数据复杂度，新型双重区分器DDML 和DD-HW 的时间复杂度以及数据复杂度均小于已有区分器.

4.4 耗时

在密码算法的攻击中，耗时越少则攻击的时间成本越小. 图6（a）和（b）分别表示在不同区分器下，在两阶段攻击中恢复子密钥的耗时与故障注入数的关系.其中横坐标表示注入的故障个数；纵坐标表示耗时，具体为遍历候选密钥和故障密文、统计中间状态的分布律、计算区分值并筛选正确密钥的总时间. 实验结果表明，除SEI 区分器外，使用HW，ML，GF，GF-SEI，GFML，GF-HW，DD-ML和DD-HW区分器以99%及以上的成功率恢复出完整密钥消耗的最少时间分别483.6 ms，462.8 ms，756.0 ms，564.8 ms，577.6 ms，554.8 ms，500.4 ms，490.8 ms. 其中，DD-ML 和DD-HW 新型区分器恢复完整密钥的耗时次于HW 和ML 单区分器，但在所有双重区分器比较中，新型区分器耗时最少.

因此，结合图5、图6 和表6 的统计分析，新型区分器DD-ML 和DD-HW 恢复MANTIS 完整密钥的成功率可达99%及以上，所需的故障数、时间复杂度、数据复杂度均达到最优，耗时低于现有双重区分器.

5 结束语

本文提出了针对MANTIS密码的唯密文故障分析方法，采用狄利克雷分布-汉明重量和狄利克雷分布—极大似然等新型区分器，不仅能以99%及以上的成功率破译密码，而且降低了故障注入数，提升了攻击效率. 研究表明，MANTIS 密码易受到唯密文故障攻击的威胁，因此，在物联网中的智能卡、RFID 等设备中使用该密码算法时，建议实施必要的举措对密码最后若干轮加以防护，以减少受到该类分析的威胁. 下一步工作将结合MANTIS密码的内部更深轮进行唯密文故障分析研究.