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.1 轮密钥加与密钥编排

DoT密码算法的主密钥是80 bit，记为$ \mathrm{K}\mathrm{E}\mathrm{Y}={K}_{79}{K}_{78}{K}_{77}\cdots {K}_{2}{K}_{1}{K}_{0} $，它的低64位作为子密钥与明文分组进行比特异或操作。在算法的每一轮加密操作中，$ \mathrm{K}\mathrm{E}\mathrm{Y} $按照如下的密钥编排进行更新：

1) $ \mathrm{K}\mathrm{E}\mathrm{Y} $循环左移13 bit：

$ \mathrm{K}\mathrm{E}\mathrm{Y} <<<13 $

2) 低8位$ {K}_{7}{K}_{6}\cdots {K}_{2}{K}_{1}{K}_{0} $通过S盒后将得到的结果与原数据进行替换：

$ \left[{K}_{3}{K}_{2}{K}_{1}{K}_{0}\right]\leftarrow \mathrm{S}\left[{K}_{3}{K}_{2}{K}_{1}{K}_{0}\right] $

$ \left[{K}_{7}{K}_{6}{K}_{5}{K}_{4}\right]\leftarrow \mathrm{S}\left[{K}_{7}{K}_{6}{K}_{5}{K}_{4}\right] $

3) 将$ \mathrm{K}\mathrm{E}\mathrm{Y} $中的$ {K}_{63}{K}_{62}{K}_{61}{K}_{60}{K}_{59} $与轮常数$ \mathrm{R}{\mathrm{C}}^{i} $进行异或操作并替换原比特：

$ \left[{K}_{63}{K}_{62}{K}_{61}{K}_{60}{K}_{59}\right]\leftarrow \left[{K}_{63}{K}_{62}{K}_{61}{K}_{60}{K}_{59}\right]\oplus \mathrm{R}{\mathrm{C}}^{i} $

1.2 半字节代换

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

1.3 置换层

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

2 模板攻击 2.1 模板攻击的基本思想

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

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

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

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

2.2.1 模板刻画

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

假设攻击者使用密钥$ \mathrm{k}\mathrm{e}\mathrm{y} $和明文$ {p}_{i} $计算得出中间值的汉明重量为$ \mathrm{H}\mathrm{W} $_i，在设备中重复加密$ m $次，采集到$ m $条能量迹，每一条能量迹上都选取相同的$ n $个点，这时攻击者就得到一个$ m\times n $的能耗矩阵M。假设第$ j $条能量迹为$ \{{T}_{(j, 1)}, {T}_{(j, 2)}, \cdots , {T}_{(j, n)}\}(1\le j\le m) $，令$ {M}_{(i, k)} $表示汉明重量为$ i $的均值向量模板M的第$ k $个样本点，则：

$ {M}_{(i, k)}=\frac{\sum \limits_{j=1}^{m}{T}_{(j, k)}}{m} $

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

$ {\boldsymbol{M}}_{i}=\{{M}_{(i, 1)}, {M}_{(i, 2)}, \cdots , {M}_{(i, n)}\} $

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

2.2.2 密钥恢复

攻击者在目标设备上用所求密钥对同一个明文$ {m}_{j} $进行多次重复加密，采集每一次加密所得的能量迹并求均值得出均值能量迹$ T\text{'}=\{{T}_{1}^{\mathrm{\text{'}}}, {T}_{2}^{\mathrm{\text{'}}}, \cdots , {T}_{n}^{\mathrm{\text{'}}}\} $。然后，攻击者使用最小二乘法^[20]求得能量迹$ T\text{'} $和每个模板的相似程度，根据最大似然原理^[21]，与$ T\text{'} $相似程度最高的模板对应的汉明重量$ \mathrm{H}{\mathrm{W}}_{i} $就与所求中间值的汉明重量相同。攻击者再用所有可能的密钥对该明文$ {m}_{j} $进行加密并计算得到中间值的汉明重量$ \mathrm{H}{\mathrm{W}}_{k} $，如果$ \mathrm{H}{\mathrm{W}}_{i}=\mathrm{H}{\mathrm{W}}_{k} $，则将对应的密钥加入集合$ {M}_{k} $中。通过多次选取明文$ {m}_{1}, {m}_{2}, \cdots , {m}_{j} $得出多个密钥集合$ {M}_{1}, {M}_{2}, \cdots , {M}_{k} $，最后对这些集合进行取交集操作，当交集为一个密钥时，该密钥即为正确密钥。

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

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

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

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

步骤1    选择一个用于建立模板的密钥$ k $，使用不同的明文与密钥$ k $执行加密运算，找出加密过程中使中间值的汉明重量分别为$ \mathrm{0, 1}, \cdots , 8 $的明文$ {m}_{0}, {m}_{1}, \cdots , {m}_{8} $，测得加密过程的能量迹并选择4 000个采样点。然后分别用明文$ {m}_{0}, {m}_{1}, \cdots , {m}_{8} $与密钥$ k $进行加密，对每一个明文都进行$ 1\mathrm{ }000 $次的加密操作，最后求均值得到$ 9 $种汉明重量模板$ {p}_{0}, {p}_{1}, \cdots , {p}_{8} $。

步骤2   随机选取一个明文$ {m}_{0}^{\text{'}} $，与所求密钥进行1 000次加密操作并测出能量迹，同样选择$ 4\mathrm{ }000 $个采样点求均值得出该明文的均值能量迹t。

步骤3    采用最小二乘法，将所得均值能量迹$ t $与所建模板$ {p}_{0}, {p}_{1}, \cdots , {p}_{8} $进行匹配，得出明文$ {m}_{0}^{\text{'}} $对应中间值的汉明重量$ {p}_{0}^{\text{'}} $，根据所得汉明重量计算出所有可能的中间值，最后对这些中间值进行逆运算得出所有可能的密钥集合$ {N}_{1}=\{{k}_{1}, {k}_{2}, \cdots , {k}_{n}\} $。其中，$ n $为所得汉明重量对应的所有可能中间值的个数，如表 2所示。

步骤4    选取另一个不同的明文$ {m}_{1}^{\text{'}} $重复步骤2和步骤3，得出另一个密钥集合$ {N}_{2} $，将其与步骤3中求出的集合进行取交集操作。通过多次选取不同明文$ {m}_{i} $，得出对应密钥集合$ {n}_{i} $，再进行取交集操作，直至得到的交集为一个密钥，则该密钥即为正确的密钥。

4 测试结果与分析

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

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

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

$ \mathrm{k}\mathrm{e}\mathrm{y}=0\mathrm{x}112233\cdots \mathrm{D}\mathrm{D}\mathrm{E}\mathrm{E}\mathrm{F}\mathrm{F}00 $

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

在第一次测试时，模板匹配得到$ \mathrm{H}\mathrm{W}\left(y\right)=5 $，已知明文首字节为$ 0\mathrm{x}\mathrm{A}4 $，通过筛选后的密钥集合为：

$ \begin{array}{l}\{0\mathrm{x}0\mathrm{B}, 0\mathrm{x}0\mathrm{D}, 0\mathrm{x}\mathrm{11, 0}\mathrm{x}\mathrm{16, 0}\mathrm{x}\mathrm{17, 0}\mathrm{x}\mathrm{19, 0}\mathrm{x}1\mathrm{A}, 0\mathrm{x}1\mathrm{E}, \\ 0\mathrm{x}1\mathrm{F}, 0\mathrm{x}\mathrm{21, 0}\mathrm{x}\mathrm{24, 0}\mathrm{x}\mathrm{27, 0}\mathrm{x}\mathrm{29, 0}\mathrm{x}2\mathrm{B}, 0\mathrm{x}2\mathrm{D}, 0\mathrm{x}2\mathrm{F}, \\ 0\mathrm{x}\mathrm{36, 0}\mathrm{x}\mathrm{37, 0}\mathrm{x}\mathrm{39, 0}\mathrm{x}\mathrm{41, 0}\mathrm{x}\mathrm{45, 0}\mathrm{x}\mathrm{48, 0}\mathrm{x}4\mathrm{C}, 0\mathrm{x}4\mathrm{F}, \\ 0\mathrm{x}\mathrm{51, 0}\mathrm{x}\mathrm{64, 0}\mathrm{x}6\mathrm{F}, 0\mathrm{x}\mathrm{75, 0}\mathrm{x}\mathrm{76, 0}\mathrm{x}7\mathrm{B}, 0\mathrm{x}7\mathrm{E}, 0\mathrm{x}7\mathrm{F}, \\ 0\mathrm{x}8\mathrm{E}, 0\mathrm{x}8\mathrm{F}, 0\mathrm{x}\mathrm{95, 0}\mathrm{x}9\mathrm{B}, 0\mathrm{x}\mathrm{A}\mathrm{0, 0}\mathrm{x}\mathrm{A}\mathrm{1, 0}\mathrm{x}\mathrm{A}\mathrm{5, 0}\mathrm{x}\mathrm{A}\mathrm{A}, \\ 0\mathrm{x}\mathrm{A}\mathrm{B}, 0\mathrm{x}\mathrm{A}\mathrm{E}, 0\mathrm{x}\mathrm{B}\mathrm{C}, 0\mathrm{x}\mathrm{D}\mathrm{1, 0}\mathrm{x}\mathrm{D}\mathrm{7, 0}\mathrm{x}\mathrm{D}\mathrm{C}, 0\mathrm{x}\mathrm{D}\mathrm{D}, \\ 0\mathrm{x}\mathrm{D}\mathrm{E}, 0\mathrm{x}\mathrm{E}\mathrm{1, 0}\mathrm{x}\mathrm{E}\mathrm{9, 0}\mathrm{x}\mathrm{E}\mathrm{A}, 0\mathrm{x}\mathrm{E}\mathrm{D}, 0\mathrm{x}\mathrm{E}\mathrm{E}, 0\mathrm{x}\mathrm{E}\mathrm{F}, \\ 0\mathrm{x}\mathrm{F}\mathrm{3, 0}\mathrm{x}\mathrm{F}\mathrm{D}\}\end{array} $

在第二次测试时，模板匹配得到$ \mathrm{H}\mathrm{W}\left(y\right)=4 $，已知明文首字节为$ 0\mathrm{x}96 $，通过筛选后的密钥首字节集合为：

$ \begin{array}{l}\{0\mathrm{x}11, \mathrm{ }0\mathrm{x}21, \mathrm{ }0\mathrm{x}2\mathrm{F}, \mathrm{ }0\mathrm{x}45, \mathrm{ }0\mathrm{x}48, \mathrm{ }0\mathrm{X}4\mathrm{F}, \mathrm{ }\mathrm{ }0\mathrm{x}51, \mathrm{ }\mathrm{ }0\mathrm{x}6\mathrm{F}, \\ 0\mathrm{x}\mathrm{76, 0}\mathrm{x}7\mathrm{B}, 0\mathrm{x}7\mathrm{F}, 0\mathrm{x}8\mathrm{F}, 0\mathrm{x}\mathrm{A}\mathrm{1, 0}\mathrm{x}\mathrm{A}\mathrm{5, 0}\mathrm{x}\mathrm{A}\mathrm{B}, 0\mathrm{x}\mathrm{E}9, \mathrm{ }\\ 0\mathrm{x}\mathrm{F}3\}\end{array} $

在第三次测试时，模板匹配得到$ \mathrm{H}\mathrm{W}\left(y\right)=4 $，已知明文首字节为$ 0\mathrm{x}33 $，通过筛选后的密钥首字节集合为：

$ \{0\mathrm{x}\mathrm{11, 0}\mathrm{x}\mathrm{21, 0}\mathrm{x}2\mathrm{F}, 0\mathrm{x}\mathrm{51, 0}\mathrm{x}8\mathrm{F}\} $

在第四次测试时，模板匹配得到$ \mathrm{H}\mathrm{W}\left(y\right)=4 $，已知明文首字节为$ 0\mathrm{x}\mathrm{C}\mathrm{F} $，通过筛选后的密钥首字节集合为：

$ \left\{0\mathrm{x}\mathrm{11, 0}\mathrm{x}2\mathrm{F}\right\} $

在第五次测试时，模板匹配得到$ \mathrm{H}\mathrm{W}\left(y\right)=5 $，已知明文首字节为$ 0\mathrm{x}\mathrm{F}0 $，通过筛选后的密钥首字节集合为：

$ \left\{0\mathrm{x}\mathrm{11, 0}\mathrm{x}2\mathrm{F}\right\} $

在第六次测试时，模板匹配得到$ \mathrm{H}\mathrm{W}\left(y\right)=1 $，已知明文首字节为$ 0\mathrm{x}21 $，通过筛选后的密钥首字节集合为：

$ \left\{0\mathrm{x}11\right\} $

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

5 模板攻击抵御方法

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

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

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

6 结束语

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