轻量级分组密码算法DoT 的模板攻击

孙家异，韦永壮

（桂林电子科技大学广西密码学与信息安全重点实验室，广西桂林 541004）

0 概述

2002 年，CHARI 等人［1］利用能量消耗与正在处理的数据有关这一基本事实［2］，提出了模板攻击的概念。模板攻击方法使用多元正态分布对采集到的数据特征进行刻画，在模板攻击中，假设攻击者可以对被攻击设备的特征进行刻画，如攻击者拥有一台与被攻击设备类型相同的设备，利用该设备，攻击者根据不同数据和固化的密钥来执行加密操作，即观察加密设备的具体物理实现，并记录对应的能耗信息，然后将与（数据，密钥）相对应的能量迹进行分组，估算多元正态分布的均值向量和协方差矩阵，并由此发起攻击。模板攻击是一种重要的侧信道攻击方法，与传统的简单能量分析［3］、相关性能量分析［4］和差分能量分析［5］等相比，模板攻击在实际的密码算法破译中拥有更强的区分能力，因此，其受到研究人员的广泛关注［6-7］。

近年来，随着物联网技术的快速发展，各种资源受限的设备（如无线传感器等）被广泛应用。由于资源受限设备大多计算与存储资源少，因此在数据安全存储、传输或处理方面存在严重的安全隐患。为解决资源受限环境下的数据安全问题，轻量级密码技术［8-10］应运而生。2019 年，JAGDISH 等人提出一种新的轻量级分组密码算法DoT［11］。与著名的轻量级分组密码算法SIMON［12］相比，DoT在软件与硬件实现方面更为简单。DoT 密码算法整体采用SP 结构［13］以及轻型的线性及非线性运算部件，在硬件实现时仅需993个等效门。设计者声称DoT 算法可以抵御多种传统数学攻击，如线性密码攻击［14］、差分密码攻击［15］等，然而，该算法在实现中是否足以抵御模板攻击仍有待探索。本文基于汉明重量模型，结合DoT 算法的结构及S 盒的特点，将DOT算法S 盒的输出作为中间值进行密钥恢复，提出一种针对DoT 算法的模板攻击方法。

1 DoT 算法描述

DoT 密码算法［11］整体结构采用SPN 设计，其明文分组为64 bit，根据密钥数据长度的不同将该算法分为2 种版本，即80 bit 的DOT-80 和128 bit 的DOT-128。对于不同的密钥长度，DoT 算法使用不同的密钥编排算法。DoT 算法的加密和解密过程均使用31 轮的轮函数迭代运算，每一个轮函数包括轮密钥加（AddRoundkey）、半字节代换（SubCells）和P 置换（Permutation）3 个步骤，如图1 所示。

图1 DoT 密码算法的轮函数Fig.1 Round function of DoT cipher algorithm

1.1 轮密钥加与密钥编排

DoT 密码算法的主密钥是80 bit，记为KEY=K79K78K77…K2K1K0，它的低64 位作为子密钥与明文分组进行比特异或操作。在算法的每一轮加密操作中，KEY 按照如下的密钥编排进行更新：

1）KEY 循环左移13 bit：

KEY ＜＜＜13

2）低8 位K7K6…K2K1K0通过S 盒后将得到的结果与原数据进行替换：

3）将KEY 中的K63K62K61K60K59与轮常数RCi进行异或操作并替换原比特：

1.2 半字节代换

半字节代换是一个非线性变换操作，其将内部状态中的每一个半字节非线性变换为另一个半字节。DoT 中使用4 bit 密码S 盒，即4 bit 输入和4 bit输出，如表1 所示。

表1 4 bit 密码S 盒Table 1 4 bit cryptographic S-box

1.3 置换层

置换层的功能是加强数据扩散，其本质上是一个线性部件。DoT 算法中采用字节的置换层包含2 次置换和1 次循环移位，如图1 所示。

2 模板攻击

2.1 模板攻击的基本思想

密码设备所产生的物理泄露种类多样，如时间序列［16］、能耗［17］和电磁辐射［18］等。近年来的侧信道分析结果表明，能耗攻击仍然是使用最多的一种攻击。模板攻击分析设备在实现加密操作过程中发生的物理泄露，这种泄露在统计上依赖所涉及密钥操作的中间值，从而使得从测量信息泄露所得的数据来推断密钥成为可能。需要注意的是，实现模板攻击有一个重要的假设前提，即攻击者能够完全控制一个和被攻击设备几乎完全类似的设备，可以不受限制地多次调用该设备，且参数由自己设定。这个假设前提有可能实现，原因是被攻击设备通常是标准设备，与其类似的设备可以通过合法途径获得。

在上述假设的基础上，攻击者可以通过该设备对算法中间值的汉明重量构建模板，然后用同样的方法在被攻击设备运行时获取能耗信息并与已构建好的模板进行匹配。匹配效果最好的模板对应的汉明重量就是可能正确的汉明重量，然后根据每一次的匹配结果得出所有可能的候选密钥集合，进行取交集操作，最后筛选出的一个密钥就是所求正确密钥。

2.2 基于汉明重量的模板攻击

模板攻击分为模板刻画和密钥恢复2 个阶段［19］，本书将进行具体阐述。

2.2.1 模板刻画

攻击者选定一个中间值，求出该中间值所有可能的汉明重量，通过使用一组密钥和明文计算出一个汉明重量为mi的中间值，使用这组数据让加密算法在密码芯片中执行重复加密操作并采集该过程中泄露的能耗信息，即能量迹，然后求出所得能量迹的均值，将其作为刻画该汉明重量的模板，这个模板仅由一个均值向量表示，对于每一个可能的汉明重量，都需建立一个均值向量模板。

假设攻击者使用密钥key 和明文pi计算得出中间值的汉明重量为HWi，在设备中重复加密m次，采集到m条能量迹，每一条能量迹上都选取相同的n个点，这时攻击者就得到一个m×n的能耗矩阵M。假设第j条能量迹为{T(j，1)，T(j，2)，…，T(j，n)}(1≤j≤m)，令M(i，k)表示汉明重量为i的均值向量模板M的第k个样本点，则：

攻击者计算出每个样本点的均值，通过计算得到汉明重量为i(0 ≤i≤b)的模板对应的均值向量为：

其中，b表示中间值的长度，对于长度为bbit 的中间值，攻击者共需刻画b+1 个模板。

2.2.2 密钥恢复

攻击者在目标设备上用所求密钥对同一个明文mj进行多次重复加密，采集每一次加密所得的能量迹并求均值得出均值能量迹T′={T′1，T′2，…，T′n}。然后，攻击者使用最小二乘法［20］求得能量迹T′和每个模板的相似程度，根据最大似然原理［21］，与T′相似程度最高的模板对应的汉明重量HWi就与所求中间值的汉明重量相同。攻击者再用所有可能的密钥对该明文mj进行加密并计算得到中间值的汉明重量HWk，如果HWi=HWk，则将对应的密钥加入集合Mk中。通过多次选取明文m1，m2，…，mj得出多个密钥集合M1，M2，…，Mk，最后对这些集合进行取交集操作，当交集为一个密钥时，该密钥即为正确密钥。

值得注意的是，测量得到的每一条能量迹都含有噪声，如果攻击者不对能量迹作预处理，噪声可能会严重影响密钥恢复阶段的成功率。因此，攻击者要对加密进行多次重复操作，通过求均值的方式来降低噪声的影响。最后，使用均值能量迹与模板进行匹配以恢复正确密钥。

3 针对DoT 分组密码的模板攻击

本文针对DoT 的软件实现进行攻击测试。在攻击中，选择DoT 第一轮执行S 盒的输出作为中间值，并采用汉明重量模型构建模板。因为DoT 在设备上执行时是每2个S盒相合并以进行运算，所以是以字节为单位，每一个字节为8 bit，因此，需要分别构建0，1，…，8这9种汉明重量模板。攻击过程如图2 所示。

图2 模板攻击流程Fig.2 Procedure of template attack

针对DoT 的模板攻击步骤如下：

步骤1选择一个用于建立模板的密钥k，使用不同的明文与密钥k执行加密运算，找出加密过程中使中间值的汉明重量分别为0，1，…，8 的明文m0，m1，…，m8，测得加密过程的能量迹并选择4 000 个采样点。然后分别用明文m0，m1，…，m8与密钥k进行加密，对每一个明文都进行1000 次的加密操作，最后求均值得到9 种汉明重量模板p0，p1，…，p8。

步骤2随机选取一个明文m0′，与所求密钥进行1 000 次加密操作并测出能量迹，同样选择4 000 个采样点求均值得出该明文的均值能量迹t。

步骤3采用最小二乘法，将所得均值能量迹t与所建模板p0，p1，…，p8进行匹配，得出明文m0′对应中间值的汉明重量p0′，根据所得汉明重量计算出所有可能的中间值，最后对这些中间值进行逆运算得出所有可能的密钥集合N1={k1，k2，…，kn}。其中，n为所得汉明重量对应的所有可能中间值的个数，如表2 所示。

表2 汉明重量i 的可能中间值数量Table 2 The number of possible median values of Hamming weight i

步骤4选取另一个不同的明文m1′重复步骤2 和步骤3，得出另一个密钥集合N2，将其与步骤3 中求出的集合进行取交集操作。通过多次选取不同明文mi，得出对应密钥集合ni，再进行取交集操作，直至得到的交集为一个密钥，则该密钥即为正确的密钥。

4 测试结果与分析

本文测试环境选用WindowsXP 系统，算法实现使用MathMagic 侧信道分析仪，其中，处理器选用STC89C52，并用MM_SCA 软件进行波形分析。

在测试过程中，在MathMagic 侧信道分析仪的STC89C52 处理器上实现DoT 算法。将采样率设置为1GS/s，可以准确地获取加密过程中的能耗泄露信息，通过MM_SCA 软件对获取的能耗曲线进行分析。首先，进行模板创建得到9 种汉明重量的能耗曲线并作为模板，如图3 所示；然后，采集波形并用最小二乘法将其与模板进行匹配，如图4 所示；最后，通过加密算法的逆运算恢复出候选密钥集合。

图3 模板曲线Fig.3 Template curves

图4 波形匹配Fig.4 Waveforms matching

本文在STC89C52 处理器上进行实验，选择6 组明文和一个固定的密钥，如下：

在实际攻击中，真正的密钥是未知的，本文中的真正密钥用来验证实验结果是否正确。在恢复第一个字节时，用6 组明文的第一个字节(0xA4，0x96，0x33，0xCF，0xF0，0x21)与密钥的第一个字节进行加密获得6 条能量迹，在每一条能量迹上同样选取4 000个采样点，且每一条能量迹都是通过加密1000次得到的均值能量迹。然后，分别用这6 条能量迹与模板曲线进行匹配得到中间值对应的汉明重量5、4、4、4、5、1。根据第一个汉明重量计算出每一个可能的中间值以及每一个可能的密钥组成集合，再根据第二个汉明重量得到相应集合，将其与第一个集合进行取交集操作，在进行第四次实验后，所得交集只剩下0x11，即为正确密钥。

在第一次测试时，模板匹配得到HW(y)=5，已知明文首字节为0xA4，通过筛选后的密钥集合为：

在第二次测试时，模板匹配得到HW(y)=4，已知明文首字节为0x96，通过筛选后的密钥首字节集合为：

在第三次测试时，模板匹配得到HW(y)=4，已知明文首字节为0x33，通过筛选后的密钥首字节集合为：

在第四次测试时，模板匹配得到HW(y)=4，已知明文首字节为0xCF，通过筛选后的密钥首字节集合为：

在第五次测试时，模板匹配得到HW(y)=5，已知明文首字节为0xF0，通过筛选后的密钥首字节集合为：

在第六次测试时，模板匹配得到HW(y)=1，已知明文首字节为0x21，通过筛选后的密钥首字节集合为：

经过上述6 次筛选测试，最终捕获正确的8 bit密钥。

5 模板攻击抵御方法

任何对抗侧信道攻击的方法都是使加密设备消耗的能量不依赖密码算法执行加密时出现的中间值，掩码技术［22］是一种著名的防护对策，其通过随机化设备处理的中间值来实现这一目标。掩码防护方法通常在算法级上进行防御，其优点是可以直接作用在密码算法的输入或输出的中间状态值上，而不必改变密码设备的硬件器件。本文提出一种对DoT密码S 盒的输入和输出进行掩码防护的方法。通常情况下可以将S 盒分为软件实现和硬件实现2 种方式。文献［23］指出掩码的密码硬件实现可能会降低其实现速度。因此，本文采用软件实现方法对DoT算法进行掩码防护。

DoT 算法的S 盒软件实现是通过使用查找表T，对于每个输入变量v，其输出都和表T 中的某个数据相对应。因此，可以对表T 加Mask 来进行掩码保护。首先，随机生成一个掩码值m，使得输入变量变成m⊕v，为了使S 盒的输出也被掩码防护，需要计算得出一个新的掩码S 盒，用S′表示，原S 盒用S表示，S′需要满足S′(v⊕m)=S(v)⊕m′，其中，m′在后续还原数据时用到。要保证S′的输出异或m′后能转变为原来的数据S（v），如图5 所示。

图5 DoT 掩码后的图形化描述Fig.5 Graphical description of masked DoT

基于以上掩码方法，本文针对DoT 密码算法进行编译实现，并进行相应的模板攻击。注意到，掩码中引入了随机数，导致敌手无法通过模板攻击中的中间值计算直接捕获正确密钥，实际测试结果也证实了这一点。

6 结束语

本文基于汉明重量模型，利用DoT 算法结构及密码S 盒的特点，提出一种针对DoT 算法的模板攻击方法。实验结果表明，DoT 算法在该模板攻击下具有脆弱性。为了抵御这一攻击，本文设计一种DoT 算法S盒掩码方案，测试结果验证了其有效性。下一步将针对DoT 密码算法设计高效的门限掩码防护方案。