积分故障分析下的Midori128密码算法安全性评估

魏悦川; 贺水喻; 潘峰; 王湘儒; WEI Yuechuan; HE Shuiyu; PAN Feng; WANG Xiangru

doi: 10.11887/j.cn.202404025

魏悦川^1,2 ，贺水喻¹ ，潘峰^1,2 ，王湘儒¹

1. 武警工程大学密码工程学院，陕西西安 710086

2. 网络与信息安全武警部队重点实验室，陕西西安 710086

基金项目: 陕西省基础研究计划资助项目(2021JM-254)

详细信息

作者简介

魏悦川(1982—)，女，天津蓟州人，副教授，博士，硕士生导师，E-mail: wych004@163.com

中图分类号: TP309.7

文献标识码: A

文章编号: 1001-2486(2024)04-229-10

Security evaluation of Midori128 cryptographic algorithm under integral fault analysis

WEI Yuechuan^1,2 ， HE Shuiyu¹ ， PAN Feng^1,2 ， WANG Xiangru¹

1. College of Password Engineering, Engineering University of PAP， Xi′an 710086 ， China

2. Key Laboratory of Network and Information Security of PAP， Xi′an 710086 ， China

摘要

为了研究Midori128密码算法针对积分故障攻击的安全性，建立积分区分器平衡位置、故障密文与轮密钥的关系，通过密钥搜索，可以恢复出算法的最后一轮密钥，进而利用密钥扩展算法恢复出主密钥。理论分析表明，利用3轮和4轮积分区分器进行积分故障攻击时，恢复出正确密钥的时间复杂度分别为2²¹和2²⁴。采用准确性、成功率和耗费时间对倒数第4轮注入故障的攻击过程进行仿真，成功恢复出该算法的主密钥，并且针对不同明文分组和密钥进行对比实验。通过两组故障安全性分析方案可知，Midori128算法的轮函数易受到积分故障攻击，在算法运行时至少需要对倒数6轮进行故障检测等额外防护。

关键词

轻量级分组密码 / Midori128算法 / 积分区分器 / 积分故障分析

Abstract

In order to study the security of the Midori128 cryptographic algorithm against integral fault attack, the relationship between integral distinguisher balance position, fault ciphertext, and the round key was established, and the last round key of the algorithm could be recovered by key search, and then the master key could be recovered by using key extension algorithm. The theoretical analysis shows that the time complexity of recovering the correct key is 2²¹ and 2²⁴ when using 3 and 4 rounds of integral distinguisher for the integral fault attack, respectively. The accuracy, success rate, and elapsed time were used to simulate the attack process of the fourth round of injection fault, and the master key of the algorithm was successfully recovered. Comparison experiments were conducted for different plaintext groups and keys. The two sets of fault security analysis schemes conclude that the round function of the Midori128 algorithm is vulnerable to integral fault attacks and requires additional protection such as fault detection for at least the last 6 rounds while the algorithm is running.

Keywords

lightweight block cipher / Midori128 algorithm / integral distinguisher / integral fault analysis

1 Midori128算法介绍 1.1 算法描述 1.2 密钥扩展算法 2 Midori128算法的积分故障分析 2.1 符号说明 2.2 Midori128的故障假设和故障模型 2.3 主要分析思路 2.4 基于3轮积分区分器的故障攻击方案 2.5 基于4轮积分区分器的故障攻击方案 3 理论分析与实验结果 3.1 理论时间复杂度 3.2 实验结果分析与对比 4 结论

随着物联网（internet of things，IoT）技术和快速通信技术的飞速发展，各种移动终端与物联网中的网络设备变得轻量化、便捷化，将网络与人们的生活紧密关联起来，达到了万物互联、万物智能化的效果。物联网作为新形态互联网络的代表，其适配设备种类纷繁复杂，越来越多的微型嵌入式设备被广泛地应用其中，如射频识别器（radio frequency identification，RFID）、无线传感器、激光扫描器、智能卡等。由于物联网不同于传统互联网，使用的设备计算、存储等资源受限，难以使用传统的分组密码进行加密通信和传输防护，给网络环境的安全带来极大挑战，因此，保护此类受限设备进行安全的信息传输和存储的需求越来越强烈。轻量级分组密码算法因其结构简单、加解密速度快、消耗资源少和利于实现等特点，完美契合于资源受限设备的布设，在此类信息系统安全领域发挥着重要的作用。针对资源受限设备，密码设计者提出了一系列轻量级分组密码算法，如 PRESENT^[1-2]、LED^[3]、LBlock^[4]、MIBS^[5]、 SIMON和SPECK^[6]等，这些轻量级密码算法的安全性备受关注。

Midori是由Banik等^[7]于2015年提出的一种轻量级分组密码算法，分组规模有两个版本，分别为Midori64和Midori128，密钥长度相同均为128 bit。该算法提供的计算开销非常小，相较于类似算法PRINCE^[8]和CRAFT^[9]，其能耗更加低。到目前为止，密码学者对Midori算法进行了许多安全性评测工作。任瑶瑶等^[10]对Midori64进行了14轮的相关密钥不可能差分分析，猜测密钥数量为84 bit。Lin等^[11]使用中间相遇攻击，得到了12轮Midori64的攻击，时间复杂度为2^125.5次12轮加密，数据复杂度为2^55.5个64 bit分组。于政等^[12]提出了Midori64的11轮不可能差分分析，攻击的时间复杂度为2^121.6次11轮加密，数据复杂度为2^62.3个64 bit分组。李明明等^[13]在文献^[12]的基础上提出Midori64 的11轮截断不可能差分分析，时间、数据复杂度更加紧实，分别为2^121.42次11轮加密和2^60.82个64 bit分组。程璐等^[14]对Midori64进行了10轮多维零相关线性分析，时间、数据复杂度为2^79.35次10轮加密和2^62.4个64 bit分组。文献^[15-16]分别提出了Midori64的不变子空间攻击和非线性不变量攻击，并以此给出该算法的全轮弱密钥攻击。文献^[17-18]分别对Midori64进行了8轮、10轮及11轮积分攻击，时间复杂度分别为2⁶⁵次8轮、2^67.85次10轮和2^117.37次11轮加密，数据复杂度分别为2^19.80、2⁴⁰和2^40.09个明文对。

故障分析作为侧信道分析方法的其中一种，在现实环境下对密码算法的安全性分析更加有效，已经成为密码算法分析领域广受关注的一个方向，密码算法抵御故障分析的能力也成为衡量密码方案设计的一项重要指标。目前，故障分析衍生出许多种攻击方法，例如差分故障分析^[19]、代数故障分析^[20]等。积分故障分析方法使用积分关系与故障注入相结合的方式，可以充分利用密码算法的积分性质，深入算法内部并达到更深轮数的攻击。沈煜等^[21]运用积分故障分析方法对韩国国家标准密码算法ARIA进行了分析。

针对Midori算法，王艺迪等结合差分故障分析及代数故障分析进行密钥恢复^[22]，结果表明Midori算法在运行中需要对其后5轮进行防护。本文提出了针对Midori128算法的积分故障分析，通过注入随机活跃字节故障，利用正确密文和错误密文构造积分区分器，利用中间状态与轮密钥（round key，RK）之间的积分关系，根据区分器中平衡字节特性恢复密钥。本文提出了两种积分故障分析方案，分别为在倒数第4轮注入活跃字节故障以及在倒数第6轮之后或倒数第5轮之前注入活跃字节故障，给出了密钥恢复方法，并采用准确性、成功率和耗费时间对攻击过程进行仿真实验验证。

1 Midori128算法介绍

1.1 算法描述

Midori128算法采用代换-置换网络（substitution-permutation network，SPN）结构，密钥长度为128 bit，分组长度为128 bit，迭代轮数为20轮，加密流程如图1所示，Midori128的明文分组长度被分成16个字节，状态矩阵表示如下:

S = (\begin{matrix} S [0] & S [4] & S [8] & S [12] \\ S [1] & S [5] & S [9] & S [13] \\ S [2] & S [6] & S [10] & S [14] \\ S [3] & S [7] & S [11] & S [15] \end{matrix})

(1)

其中，S[i]（i=0，1，···，15）表示第i个字节。

图1Midori128算法加密过程

Fig.1Midori128 algorithm encryption process

Midori128轮函数为包括字节替代（SubCell，SB）、置换（ShuffleCell，SC）、列混淆（MixColumn，MC）和轮密钥加（KeyAdd，KA）的复合操作，该轮函数作用在状态矩阵上。在算法加密的起始部分和结尾部分使用白化密钥进行异或，且最后一轮的轮函数只有字节替代操作，其解密流程是加密过程的逆运算。

1）字节替代：Midori128采用4个8 bit S盒SSb₀、SSb₁、SSb₂、SSb₃进行字节代换，每个SSb_i由输入和输出位的排列组合以及两个Sb₁复合得到，Sb₁如表1所示。

表1Midori128使用的4 bit S盒

Tab.1 4 bit S-boxes used by Midori128

Midori128算法的SSb_i中每个输出位的排列被视为相应的输入位排列的倒数，如图2所示，位的逆运算保持了内部关联属性，计算方式记为P_i（x）=yⁱ。

\{\begin{matrix} y_{[0,1, 2,3, 4,5, 6,7]}^{0} = x_{[4,1, 6,3, 0,5, 2,7]} \\ y_{[0,1, 2,3, 4,5, 6,7]}^{1} = x_{[1,6, 7,0, 5,2, 3,4]} \\ y_{[0,1, 2,3, 4,5, 6,7]}^{2} = x_{[2,3, 4,1, 6,7, 0,5]} \\ y_{[0,1, 2,3, 4,5, 6,7]}^{3} = x_{[7,4, 1,2, 3,0, 5,6]} \end{matrix}

(2)

其中，SSb_i分别作用于状态矩阵的各行。

2）置换：将SB作用之后的状态矩阵按字节进行置换，该置换及逆置换如下所示。

\begin{matrix} (\begin{matrix} S [0] & S [4] & S [8] & S [12] \\ S [1] & S [5] & S [9] & S [13] \\ S [2] & S [6] & S [10] & S [14] \\ S [3] & S [7] & S [11] & S [15] \end{matrix}) \overset{S C}{\to} \overset{}{} \\ (\begin{matrix} S [0] & S [14] & S [9] & S [7] \\ S [10] & S [4] & S [3] & S [13] \\ S [5] & S [11] & S [12] & S [2] \\ S [15] & S [1] & S [6] & S [8] \end{matrix}) \end{matrix}

(3)

\begin{matrix} (\begin{matrix} S [0] & S [4] & S [8] & S [12] \\ S [1] & S [5] & S [9] & S [13] \\ S [2] & S [6] & S [10] & S [14] \\ S [3] & S [7] & S [11] & S [15] \end{matrix}) \overset{{S C}^{- 1}}{\to} \\ (\begin{matrix} S [0] & S [5] & S [15] & S [10] \\ S [7] & S [2] & S [8] & S [13] \\ S [14] & S [11] & S [1] & S [4] \\ S [9] & S [12] & S [6] & S [3] \end{matrix}) \end{matrix}

(4)

图2Midori128算法的字节代替（SB）

Fig.2The detail of Midori128 algorithm′s SB

3）列混淆：将SC作用之后的结果左乘矩阵M，执行按列混合变换，操作如下。

(\begin{matrix} S [i] \\ S [i + 1] \\ S [i + 2] \\ S [i + 3] \end{matrix}) \overset{M C}{\to} M (\begin{matrix} S [i] \\ S [i + 1] \\ S [i + 2] \\ S [i + 3] \end{matrix})

(5)

其中，

。

4）轮密钥加：将MC作用之后的状态矩阵和轮密钥进行按位异或计算。

Midori128算法加密过程的伪代码如算法1所示。

1.2 密钥扩展算法

Midori128密钥扩展算法较为简单，如算法2所示。主密钥由两个64 bit的密钥K₀和K₁级联构成，即K=K₀‖K₁，主密钥K直接作为白化密钥使用，即WK=K，在首轮使用轮函数之前和最后一轮使用轮函数之后参与运算；轮密钥

R K_{i} = K \oplus α_{i} （ 0 ⩽ i ⩽ 18 ）

，其中，

\oplus

为异或运算，α_i为轮常数，表2为轮常数所选参数。

算法1 Midori128轮函数加密过程

Alg.1 Midori128 round function encryption process

算法2 Midori128的密钥扩展

Alg.2 Key extension for Midori128

表2轮常数α_i

Tab.2 The round constants α_i

2 Midori128算法的积分故障分析

积分故障分析方法是故障分析的一种新型方式，其主要思路是结合积分分析可以深入算法内部的特点，在密码算法任一轮之间注入随机故障，根据积分区分器的长度，推算出密码算法某一轮的轮密钥，而后反向解密该轮的状态信息，并以此类推，可获得多轮子密钥信息，最终根据密钥扩展方式推断出正确密钥。积分故障分析可以以较低的数据和存储复杂度在物联网等应用中实现，Phan等^[23]首次使用该分析方式对高级加密标准（advanced encryption standard， AES）的倒数4轮进行分析，并获得多轮密钥信息。

2.1 符号说明

Y、Y^（^u^）分别表示正确密文和第u次注入故障的错误密文，均为128 bit；K为128 bit主密钥；WK为128 bit白化密钥；r为迭代轮数。

2.2 Midori128的故障假设和故障模型

故障假设表示攻击者在现实环境中具备的优势或能力，对于Midori128算法，本文基于三点假设：

1）对同一个明文，攻击者可以获得在同一个密钥作用下的正确密文Y和错误密文Y^（^u^）。

2）攻击者可以在算法运行中注入故障，使得某个字节出错。故障字节的具体位置未知，具体的错误值未知，但是每次注入故障的位置相同，错误值不同，即错误值遍历1~255。

3）在一次故障分析中，密钥的值不发生改变。

本文所使用故障模型为：随机活跃字节故障，即在算法运行的某一轮的指定位置引入随机活跃字节故障。

2.3 主要分析思路

攻击者选择任意明文进行加密操作，同时在使用相同密钥的情况下引入活跃字节故障，得到1组密文，其中1个密文为正确密文，255个密文为错误密文；而后构造基于字节的积分区分器，根据区分器的平衡位置对最后1轮密钥进行筛选，找到正确轮密钥，结合密钥扩展算法，恢复出主密钥。

2.4 基于3轮积分区分器的故障攻击方案

本文根据Midori128算法轮函数特点构造了一个3轮积分区分器，该区分器并不是Midori128已知的最长区分器，却是零和效果最好的区分器。

在构造积分区分器时，需要对字节的性质作以下定义^[24]。

稳定字节：对于定义在

F_{2^{8}}

上的字节集合C={a^（^u^）|0≤u≤2⁸-1}，对于任意0≤u≤v≤2⁸-1，均有a^（^u^）=a^（^v^），则称C为

F_{2^{8}}

上的稳定字节。

活跃字节：对于定义在

F_{2^{8}}

上的字节集合A={a^（^u^）|0≤u≤2⁸-1}，对于任意0≤u＜v≤2⁸-1，均有a^（^u^）≠a^（^v^），则称A为

F_{2^{8}}

上的活跃字节。

平衡字节：对于定义在

F_{2^{8}}

上的字节集合B={a^（^u^）|0≤u≤2⁸-1}满足

\overset{2^{8} - 1}{\underset{u = 0}{Σ}} a^{（ u ）} = 0

，则称B为

F_{2^{8}}

上的平衡字节。

其中，稳定/活跃字节经过字节替代和轮密钥异或运算后仍然是稳定/活跃字节；活跃字节的异或为平衡字节；稳定字节异或活跃字节后为活跃字节；平衡字节相互异或后仍为平衡字节。

下面给出Midori128算法的3轮积分区分器。

性质1：对于Midori128算法，如果第r轮输入状态中有1个活跃字节而其他字节均为稳定字节，则r+2轮输出的所有字节均为平衡字节。

以上区分器可以根据字节扩散的性质得出，区分器的一个实例如图3所示，该区分器可以形式化地表示为：

注意到活跃字节一定是平衡字节，因此以上区分器中，输出的所有字节均是平衡的，并且当输入字节中A的位置变化时，输出字节的平衡性仍然保持不变。以上区分器中输出的活跃字节的平衡性可以进行证明。

图3Midori128的3轮积分区分器

Fig.3Midori128′s 3-round integral distinguisher

根据文献^[25]中的两个定理证明性质1中区分器输出活跃字节为平衡字节的正确性。

定理1 设多项式

f （ x ） = \overset{q - 1}{\underset{u = 0}{Σ}} b^{（ u ）} x^{u} \in F_{q} [x]

，其中q是某个素数的幂方，则

\overset{}{\underset{x \in F_{q}}{Σ}} f （ x ） = - b^{q - 1}

。

定理2 若多项式

f （ x ） = \overset{q - 1}{\underset{u = 0}{Σ}} b^{（ u ）} x^{u} \in F_{q} [x]

是置换多项式，则b^q^-1=0。

证明：τ₀，τ₁，τ₂，···，τ₁₅为第r轮输入字节，其中a=τ₀为活跃字节，其他均为稳定字节，则第r轮的输入表示为（τ₀，τ₁，τ₂，···，τ₁₅）=（a，τ₁，τ₂，···，τ₁₅），a为变量，τ₁，τ₂，···，τ₁₅均为常量。由图3可知，第r轮输出可以表示为（τ₀，f₁（a），f₂（a），f₃（a），τ₄，···，τ₁₅），其中，τ₀，τ₄，···，τ₁₅为常量，f₁（a），f₂（a），f₃（a）为

F_{2^{8}}

域上的置换多项式。

第r+2轮的输入为（β，β，β，β，β，h₅（a），h₆（a），β，β，β，h₁₀（a），h₁₁（a），β，h₁₃（a），β，h₁₅（a））。其中，h₅（a），h₆（a），h₁₀（a），h₁₁（a），h₁₃（a），h₁₅（a）是

F_{2^{8}}

域上的置换多项式。上述的每个字节均可用

F_{2^{8}}

上的8个置换多项式的积分和表示。

假设r+2轮输入的第一个字节为p₀（a）

\oplus

p₁（a）

\oplus

···

\oplus

p₇（a），其中，p_i（a）是

F_{2^{8}}

上的置换多项式。结合定理2可得

\overset{}{\underset{a \in F_{2^{8}}}{Σ}} p_{0} (a) = \underset{a \in F_{2^{8}}}{Σ} p_{1} (a) = \dots = \underset{a \in F_{2^{8}}}{Σ} p_{7} (a) = 0

(6)

因此

\begin{matrix} \underset{a \in F_{2^{8}}}{Σ} (p_{0} (a) \oplus p_{1} (a) \oplus \dots \oplus p_{7} (a)) \\ = \underset{a \in F_{2^{8}}}{Σ} p_{0} (a) = \dots = \underset{a \in F_{2^{8}}}{Σ} p_{7} (a) \\ = 0 \end{matrix}

(7)

通过在第r轮的状态矩阵任意字节引入随机活跃字节故障，依据以上区分器，可以得出r+2轮的输出均为平衡字节。本文选择以上区分器进行分析，是因为所有输出字节均为平衡字节，能够以较高的效率恢复轮密钥。

基于以上积分区分器，可以给出在倒数第4轮（第r轮）注入活跃字节故障的攻击方案。

Step 1：选择任意明文X，使用主密钥K进行加密操作，得到正确密文Y。

Step 2：重复加密操作，攻击者在加密过程的倒数第5轮MC之后、倒数第4轮MC之前的任何一个时刻和位置注入活跃字节故障，取值在[0，255]之间，获得故障密文，如图4所示。在倒数第5轮MC之后、倒数第4轮MC之前的任何一个时刻和位置注入活跃字节故障，不会影响活跃字节的属性。后续各状态矩阵的积分值随着故障注入发生变化，密文Y^（^u^）存在如下关系。

\begin{matrix} \overset{255}{\underset{u = 0}{Σ}} S_{r + 3}^{(u)} = \overset{255}{\underset{u = 0}{Σ}} [{S B}^{- 1} (Y^{(u)} \oplus W K^{(u)})] \\ = \overset{255}{\underset{u = 0}{Σ}} [{S B}^{- 1} (Y^{(u)} \oplus W K)] \\ = \overset{255}{\underset{u = 0}{Σ}} [S B (Y^{(u)} \oplus W K)] \end{matrix}

(8)

以上关系式利用了SB变换的对合性，其中，

S_{r + 3}^{（ u ）}

、WK^（^u^）分别表示第u次注入故障时S_r₊₃、WK的值，u=0对应正确的状态矩阵和密文。

图4基于3轮积分区分器的故障分析过程

Fig.4Fault analysis process based on 3-round integral distinguisher

Step 3：基于3轮积分区分器，S_r₊₃中的每个字节都是平衡的，即：

\overset{255}{\underset{u = 0}{Σ}} S_{r + 3}^{(u)} [i] = 0 (0 ⩽ i ⩽ 15)

(9)

其中，

S_{r + 3}^{（ u ）} [i]

是4轮加密操作后状态矩阵在位置i处的值。攻击者逐字节搜索白化密钥WK[i]，计算

S_{r + 3}^{（ u ）} [i] = S B (Y^{（ u ）} [i] \oplus W K [i])

， Y^（^u^）[i]是故障密文中对应位置i的故障字节值。然后判断是否满足

\overset{255}{\underset{u = 0}{Σ}} S_{r + 3}^{（ u ）} [i] = 0

，若满足，则将WK[i]记为候选密钥，不满足则淘汰。

Step 4：保持加密过程中使用的主密钥不变，利用不同明文加密获得对应密文集，包含1个正确密文，255个错误密文。重复进行步骤1~3，再次筛选候选密钥值，直到候选密钥被唯一确定，即恢复出正确的白化密钥。

Step 5：根据Midori128密钥扩展算法可知，WK=K，所恢复出的白化密钥即为主密钥。

2.5 基于4轮积分区分器的故障攻击方案

基于4轮积分区分器进行故障攻击所使用的区分器，是对连闯^[17]给出的Midori64的4轮区分器的扩展，也是目前已知的Midori算法最长的基于字节的积分区分器，性质2是文献^[17]给出的区分器，性质3是本文扩展后的区分器。

性质2^[17]：对于Midori128算法，如果第r轮明文输入状态中第1个字节是活跃字节，其他字节均为稳定字节，则r+3轮输出的第1个字节为平衡字节。

以上字节状态的扩散过程如图5所示，该积分区分器可以形式化地表示为：

图5Midori128的4轮积分区分器

Fig.5Midori128′s 4-round integral distinguisher

经过深入分析，我们发现以上积分区分器可以扩展为以下形式。

性质3：对于Midori128算法，如果第r轮明文输入状态中第i个字节是活跃字节，其他字节均为稳定字节，则r+3轮输出的第i个字节为平衡字节。即:

。

基于性质3中的区分器，本节给出以下攻击方案：在倒数第6轮MC之后或倒数第5轮MC之前的任何一个时刻注入随机活跃字节故障，使用与3轮攻击方案相同的思路进行攻击，则可以恢复出1个字节的密钥，故障分析过程见图6。要恢复出最后一轮密钥的全部字节，需要将上述过程重复16次。

图6基于4轮积分区分器的故障分析过程

Fig.6Fault analysis process based on 4-round integral distinguisher

根据性质3所给出的区分器实施攻击方案如下：

Step 1：选择任意明文X，使用主密钥K进行加密操作，得到正确密文Y。

Step 2：重复加密操作，攻击者在加密过程的倒数第6轮MC之后或倒数第5轮MC之前任何一个时刻注入活跃字节故障，故障位于第i个字节（0≤i≤15），取值在[0，255]之间，并得到故障密文。根据性质3中的结论可知，在引入活跃字节故障之后，经过4轮加密操作可让状态矩阵相应位置的字节达到平衡，并且存在如下关系：

\overset{255}{\underset{u = 0}{Σ}} S_{r + 3}^{(u)} [i] = \overset{255}{\underset{u = 0}{Σ}} [S B (Y^{(u)} [i] \oplus W K [i])]

(10)

Step 3：攻击者通过穷尽搜索对应的密钥字节（取值[0，255]），即验证是否存在密钥字节使得

\overset{255}{\underset{u = 0}{Σ}} S_{r + 3}^{（ u ）} [i] = 0

成立，若存在则保留其为候选密钥字节。

Step 4：保持加密过程的主密钥不变，依次更换活跃字节注入位置，直到恢复出WK全部的候选密钥字节WK[i]（此时WK[i]可能并不唯一）。

Step 5：保持加密过程中使用的主密钥不变，利用不同明文加密获得对应密文集，包含1个正确密文，255个错误密文。重复进行步骤1~4，再次筛选WK[i]的候选密钥值，直到候选密钥被唯一确定，即得到正确的白化密钥。

Step 6：根据Midori128密钥扩展算法可知，WK=K，所恢复出的白化密钥即为主密钥。

3 理论分析与实验结果

3.1 理论时间复杂度

在攻击方案实施过程中，为了计算平衡字节的积分和，攻击者至少需要1组密文，包含1个正确的密文和255个故障的密文。设δ表示1个错误轮密钥满足积分和为零的概率，Γ表示穷尽搜索轮密钥的空间。当攻击者诱导τ组密文集时，轮密钥候选值中剩余错误密钥数为（Γ-1）δ^τ。若（Γ-1）δ^τ＜1，则表示轮密钥候选值可以被唯一确定，即正确的轮密钥。

3 轮积分故障攻击过程中有：

\{\begin{matrix} Γ = 2^{8} \\ δ = 2^{- 8} \end{matrix}

(11)

如果τ＞2，则攻击者可以找到正确的密钥，此时穷尽搜索1组密文集的时间复杂度为2⁸×2⁸×16=2²⁰，即恢复Midori128算法主密钥的最少理论时间复杂度为2²¹。4轮积分故障攻击时，由于单次实验平衡字节数仅为1，需要进行16次不同字节位置故障导入，所以时间复杂度为2⁸×2⁸×16×16=2²⁴。

3.2 实验结果分析与对比

本文的实验环境为Inter Core I5-10800H@4.6 GHz、内存为16 GB的计算机，使用系统环境C++语言程序（Code∶∶Blocks 20.03）编写Midori128算法加解密和积分故障分析计算机仿真过程，通过程序模拟故障注入并生成错误密文，解密一轮后可得到候选密钥值。使用的明密文分组及密钥如表3所示。以在倒数第4轮任意字节注入故障的方案为例，单字节密钥恢复实验中，选定字节位置引入故障，可恢复对应平衡字节所使用的密钥字节，表4为进行1 000次实验时恢复的各个字节位置平均候选密钥个数。

在进行多字节密钥恢复实验时，本节通过采用准确性、成功率和耗费时间对实验结果进行详细描述。候选密钥值与真实密钥值之间的近似程度通过准确性进行衡量，本文采用均方根误差（root mean square error，RMSE）公式来进行计算。

R E S M = \sqrt{\frac{\overset{n}{\underset{e = 1}{Σ}} (ϕ (e) - θ)}{n}}

(12)

式中，n为实验次数，φ（e）为在第e次实验时恢复的候选密钥的字节数，θ为真正密钥的字节数，其中n=200，θ=16。本文共进行1 000次实验，平均分为5组，分别为G₁、G₂、G₃、G₄和G₅。均方根误差越接近于0则实验结果越准确，候选密钥的均方根误差如表5所示，实验结果表明，在倒数第4轮注入故障攻击方案中，使用3组密文集合进行密钥恢复操作即可恢复出正确密钥。图7展示了使用2组密文集合进行密钥恢复后，筛选出正确密钥的效率波形，图8显示表5中对应的使用2组和3组密文集时，成功概率平均值分别为94.7%和100%。

表3实验明密文实例

Tab.3 Examples of experimental plaintexts

表4各字节实验1 000次的平均候选密钥个数

Tab.4 Average number of candidate keys for each byte experiment 1 000 times

表5恢复密钥的均方根误差

Tab.5 RMSE of recovery keys

图7两次密钥筛选效率

Fig.7Twice key screening efficiency

通过更换密钥对应不同明文分组，进行多次对比实验后，总体密钥恢复的效率较高，结果如图9所示。从图9中可以看出，进行两次筛选后可以以高概率得到正确的密钥信息。

本文基于3轮积分区分器攻击方案中单次实验耗费的时间处于12~21 s；在使用4轮积分区分器进行故障攻击时，单次实验耗费时间处于5~14 s，由于单次实验仅可以恢复一个密钥字节，密钥恢复的效率有所下降，恢复密钥字节的平均时间约为9.2 s。

图8成功恢复密钥概率图

Fig.8Probability of successful key recovery

图9密钥筛选对比

Fig.9Key filter comparison

传统的差分故障分析利用的是字节的差分传播特性，本文的积分故障分析利用的是字节的积分特性，两者恢复密钥的原理是不同的。传统的差分故障分析所需的明文量较少，但是故障的注入轮相对较浅，积分故障分析中，由于Midori128算法是基于字节设计的，能够获得较好的字节零和性质，因此积分故障分析更适合对算法进行深度的故障注入分析，并且具有更高的恢复效率。

4 结论

本文提出了基于Midori128算法的积分故障分析方法，构造了Midori128算法的3轮和4轮积分区分器，并采取随机活跃字节故障注入的方式进行分析。使用基于3轮和4轮积分区分器进行故障分析分别可深入Midori128算法的4轮和6轮。理论分析表明了Midori128算法恢复主密钥的可行性，而后通过实验结果进行验证。相较于传统的故障分析方法，本文方案能够对算法的攻击轮数更高，故障注入更为深入。由本文提出的两种方案可知，使用Midori密码算法加密的同时，至少应当对倒数6轮进行故障检测等硬件防护，避免引起密钥泄露。

图1Midori128算法加密过程

Fig.1Midori128 algorithm encryption process

下载: 全尺寸图片

图2Midori128算法的字节代替（SB）

Fig.2The detail of Midori128 algorithm′s SB

下载: 全尺寸图片

图3Midori128的3轮积分区分器

Fig.3Midori128′s 3-round integral distinguisher

下载: 全尺寸图片

图4基于3轮积分区分器的故障分析过程

Fig.4Fault analysis process based on 3-round integral distinguisher

下载: 全尺寸图片

图5Midori128的4轮积分区分器

Fig.5Midori128′s 4-round integral distinguisher

下载: 全尺寸图片

图6基于4轮积分区分器的故障分析过程

Fig.6Fault analysis process based on 4-round integral distinguisher

下载: 全尺寸图片

图7两次密钥筛选效率

Fig.7Twice key screening efficiency

下载: 全尺寸图片

图8成功恢复密钥概率图

Fig.8Probability of successful key recovery

下载: 全尺寸图片

图9密钥筛选对比

Fig.9Key filter comparison

下载: 全尺寸图片

表1Midori128使用的4 bit S盒

下载: 全尺寸图片

表2轮常数α_i

下载: 全尺寸图片

表3实验明密文实例

下载: 全尺寸图片

表4各字节实验1 000次的平均候选密钥个数

下载: 全尺寸图片

表5恢复密钥的均方根误差

下载: 全尺寸图片

图1Midori128算法加密过程

Fig.1Midori128 algorithm encryption process

图2Midori128算法的字节代替（SB）

Fig.2The detail of Midori128 algorithm′s SB

图3Midori128的3轮积分区分器

Fig.3Midori128′s 3-round integral distinguisher

图4基于3轮积分区分器的故障分析过程

Fig.4Fault analysis process based on 3-round integral distinguisher

图5Midori128的4轮积分区分器

Fig.5Midori128′s 4-round integral distinguisher

图6基于4轮积分区分器的故障分析过程

Fig.6Fault analysis process based on 4-round integral distinguisher

图7两次密钥筛选效率

Fig.7Twice key screening efficiency

图8成功恢复密钥概率图

Fig.8Probability of successful key recovery

图9密钥筛选对比

Fig.9Key filter comparison

表1Midori128使用的4 bit S盒

表2轮常数α_i

表3实验明密文实例

表4各字节实验1 000次的平均候选密钥个数

表5恢复密钥的均方根误差

引用提醒

图(9) / 表(5)

引用本文

魏悦川, 贺水喻, 潘峰, 等.积分故障分析下的Midori128密码算法安全性评估[J]. 国防科技大学学报, 2024, 46(4): 229-238.

复制

WEI Y C, HE S Y, PAN F, et al. Security evaluation of Midori128 cryptographic algorithm under integral fault analysis[J]. Journal of National University of Defense Technology, 2024, 46(4): 229-238.

Copy

计量

图1Midori128算法加密过程

Fig.1Midori128 algorithm encryption process

图2Midori128算法的字节代替（SB）

Fig.2The detail of Midori128 algorithm′s SB

图3Midori128的3轮积分区分器

Fig.3Midori128′s 3-round integral distinguisher

图4基于3轮积分区分器的故障分析过程

Fig.4Fault analysis process based on 3-round integral distinguisher

图5Midori128的4轮积分区分器

Fig.5Midori128′s 4-round integral distinguisher

图6基于4轮积分区分器的故障分析过程

Fig.6Fault analysis process based on 4-round integral distinguisher

图7两次密钥筛选效率

Fig.7Twice key screening efficiency

图8成功恢复密钥概率图

Fig.8Probability of successful key recovery

图9密钥筛选对比

Fig.9Key filter comparison

表1Midori128使用的4 bit S盒

表2轮常数α_i

表3实验明密文实例

表4各字节实验1 000次的平均候选密钥个数

表5恢复密钥的均方根误差

BOGDANOV A, KNUDSEN L R, LEANDER G,et al. PRESENT:an ultra-lightweight block cipher[C]//Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems,2007.

黄湘蜀, 王敏, 杜之波, 等. 针对轻量级分组密码算法PRESENT的随机差分故障攻击[J]. 成都信息工程大学学报,2022,37(1):8-15. HUANG X S, WANG M, DU Z B,et al. Random differential fault attack against the lightweight block cipher algorithm PRESENT[J]. Journal of Chengdu University of Information Technology,2022,37(1):8-15.(in Chinese)

GUO J, PEYRIN T, POSCHMANN A,et al. The LED block cipher[C]//Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems,2011.

CUI Y X, XU H, QI W F. Improved integral attacks on 24-round LBlock and LBlock-s[J]. IET Information Security,2020,14(5):505-512.

任炯炯, 侯泽洲, 李曼曼, 等. 改进的减轮MIBS-80密码的中间相遇攻击[J]. 电子与信息学报,2022,44(8):2914-2923. REN J J, HOU Z Z, LI M M,et al. Improved meet-in-the-middle attacks on reduced-round MIBS-80 cipher[J]. Journal of Electronics & Information Technology,2022,44(8):2914-2923.(in Chinese)

SUSANTI B H, PERMANA O J, AMIRUDDIN. Robustness test of SIMON-32, SPECK-32,and SIMECK-32 algorithms using fixed-point attacks[J]. Journal of Physics: Conference Series,2021,1836(1):012006.

BANIK S, BOGDANOV A, ISOBE T,et al. Midori:a block cipher for low energy[C]//Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security,2015.

MÜLLER N, MOOS T, MORADI A. Low-latency hardware masking of PRINCE[C]//Proceedings of the International Workshop on Constructive Side-Channel Analysis and Secure Design,2021.

HADIPOUR H, SADEGHI S, NIKNAM M M,et al. Comprehensive security analysis of CRAFT[J]. IACR Transactions on Symmetric Cryptology,2020,2019(4):290-317.

任瑶瑶, 张文英. Midori64的相关密钥不可能差分分析[J]. 计算机应用研究,2018,35(6):1800-1802. REN Y Y, ZHANG W Y. Related-key differential analysis of Midori64[J]. Application Research of Computers,2018,35(6):1800-1802.(in Chinese)

LIN L, WU W L. Meet-in-the-middle attacks on reduced-round Midori64[J]. IACR Transactions on Symmetric Cryptology,2017,2017(1):215-239.

于政, 毛明, 李艳俊. 基于轮密钥分步猜测方法的Midori64算法11轮不可能差分分析[J]. 计算机应用研究,2018,35(9):2777-2780. YU Z, MAO M, LI Y J. Impossible differential analysis of 11-round Midori64 based on method of step-key-guessing[J]. Application Research of Computers,2018,35(9):2777-2780.(in Chinese)

李明明, 郭建胜, 崔竞一, 等. Midori-64算法的截断不可能差分分析[J]. 软件学报,2019,30(8):2337-2348. LI M M, GUO J S, CUI J Y,et al. Truncated impossible differential cryptanalysis of Midori-64[J]. Journal of Software,2019,30(8):2337-2348.(in Chinese)

程璐, 魏悦川, 李安辉, 等. Midori算法的多维零相关线性分析[J]. 山东大学学报(理学版),2018,53(2):88-94. CHENG L, WEI Y C, LI A H,et al. Multidimensional zero-correlation linear cryptanalysis on Midori[J]. Journal of Shandong University(Natural Science),2018,53(2):88-94.(in Chinese)

GUO J, JEAN J, NIKOLIC I,et al. Invariant subspace attack against Midori64 and the resistance criteria for S-box designs[J]. IACR Transactions on Symmetric Cryptology,2016,2016(1):33-56.

TODO Y, LEANDER G, SASAKI Y. Nonlinear invariant attack:practical attack on full SCREAM,iSCREAM,and Midori64[J]. Journal of Cryptology,2019,32(4):1383-1422.

连闯. 轻量级分组密码的积分分析[D]. 西安: 西安电子科技大学,2018. LIAN C. Integral cryptanalysis of lightweight block ciphers[D]. Xi′an: Xidian University,2018.(in Chinese)

王超, 陈怀凤. Midori64分组密码算法的积分攻击[J]. 计算机工程,2021,47(5):117-123. WANG C, CHEN H F. Integral attacks on Midori64[J]. Computer Engineering,2021,47(5):117-123.(in Chinese)

GUO H, SUN S W, SHI D P,et al. Differential attacks on CRAFT exploiting the involutory S-boxes and tweak additions[J]. IACR Transactions on Symmetric Cryptology,2020,2020(3):119-151.

VIELHABER M. Breaking one. Fivium by AIDA an algebraic IV differential attack[EB/OL].[2022-04-01].https://eprint.iacr.org/2007/413.pdf.

沈煜, 李玮, 谷大武, 等. ARIA密码的积分故障分析[J]. 通信学报,2019,40(2):164-173. SHEN Y, LI W, GU D W,et al. Integral fault analysis of the ARIA cipher[J]. Journal on Communications,2019,40(2):164-173.(in Chinese)

王艺迪, 赵新杰, 张帆, 等. Midori算法抗故障攻击安全性评估[J]. 密码学报,2017,4(1):58-78. WANG Y D, ZHAO X J, ZHANG F,et al. Security evaluation for fault attacks on lightweight block cipher Midori[J]. Journal of Cryptologic Research,2017,4(1):58-78.(in Chinese)

PHAN R C W, YEN S M. Amplifying side-channel attacks with techniques from block cipher cryptanalysis[C]//Proceedings of the International Conference on Smart Card Research and Advanced Applications,2006.

DAEMEN J, KNUDSEN L, RIJMEN V. The block cipher Square[C]//Proceedings of the International Workshop on Fast Software Encryption,1997.

LIDL R, NIEDERREITER H. Finite fields[M].2nd ed. Cambridge, UK: Cambridge University Press,1997.

首页

期刊介绍

投稿指南

编委会

出版道德声明

开放获取声明

联系我们

Email订阅

Rss

English

1 Midori128算法介绍

2 Midori128算法的积分故障分析

3 理论分析与实验结果

4 结论