改进的基于掩码AES选择明文碰撞攻击方法

郑 东，王柳生，赵秉宇，张美玲

(西安邮电大学 无线网络安全技术国家工程实验室,陕西 西安 710121)

信息化时代的信息传输量巨大，会涉及到个人身份信息、网上购物支付密码等隐私信息。与密码相关的设备，如安全支付设备、智能穿戴设备和智能家居设备等也逐渐在生活中普及。随着各种密码硬件设备被应用到物联网、智慧城市、区块链和边缘计算等各行各业中，其所面临的安全威胁不应被忽视[1-2]。

1996年，Kocher等人首次提出计时攻击之后，各种侧信道攻击方法被提出。根据密码设备在运行过程中泄露信息的种类不同，可将侧信道攻击分为故障攻击[3]、能量分析攻击[4-5]、电磁辐射攻击[6]、缓存攻击[7]和声音攻击[8]等。能量分析攻击因其实现简单、花费代价小，可有效提取被加密信息中的密钥等优势，自提出以来备受关注。1999年，Kocher等人提出了差分能量分析攻击[9](Differential Power Analysis，DPA)，利用能量迹和已知的密文，通过选择函数恢复某些子密钥，但是其需要大量的能量迹。2004年，Brier等人提出的相关能量分析攻击[10](Correlation Power Analysis，CPA)，利用已知明文和猜测的密钥的假设的能量消耗，与实际能量消耗的相关性恢复密钥。

针对已知明文输入或密文输出的情况，侧信道攻击对密码设备产生了严重的威胁。如果不知道算法的输入或者输出，很多攻击都无效，比如差分能量分析攻击。2014 年，Linge等人提出了联合概率分布攻击[11]，首先针对高级加密标准(Advanced Encryption Standard，AES)算法的S盒输入输出的汉明重量(Hamming Weight，HW)，计算每个可能密钥的理论概率分布。然后从能量迹中估计的汉明重量分布与预计算好的理论联合概率分布求距离，距离最小的即为正确的密钥。文献[12]用最大似然法提升了从能量迹中提取的汉明重量的估计效率。

碰撞攻击是指在算法的某个函数中是否有不同的输入产生了相同的输出。2003年，Schramm等人[13]首先提出了针对数据加密标准(Data Encryption Standard，DES)算法S盒的碰撞攻击。文献[14]提出了针对AES算法加密中第一轮的混合列变换输出的碰撞攻击。2007年，Bogdanov等人[15]提出了针对AES算法加密中第一轮S盒输入的线性碰撞攻击，通过建立不同密钥间的关系式，用较少的能量迹恢复密钥，但计算量较大。2010年，Moradi等人[16]提出了针对带有随机掩码的AES算法S盒的相关碰撞攻击。文献[17]改进了针对带有重用掩码S盒的相关碰撞攻击，平均需要27.5个明文就可以恢复所有的密钥。2019年，Zheng等人[18]提出了假设检验法，能够在S盒输入发生碰撞时以较高的成功率检测出碰撞。2019年，Ding等人[19]提出了针对带有重用掩码AES算法的S盒输入的自适应选择明文碰撞攻击方法，假设敌手拥有和待攻击设备相同的设备建立模板，通过选择明文并与模板匹配可以降低密钥搜索空间，直到找到密钥。但是如果敌手没有了这样的可控硬件，那么就无法建立模板进行攻击。

在带有重用掩码的AES算法中，任意两个S盒输入的汉明距离(Hamming Distance，HD)和欧几里德距离(Euclidean Distance，ED)有着一一对应的关系，而密码设备电路中的各个采样点的能量消耗可以用汉明重量模型表示。基于此，改进的基于掩码AES选择明文碰撞攻击方法先求出能量迹的汉明重量模型表达式中的各个参数的值，然后根据表达式计算出不同的汉明距离所对应的欧几里德距离值，建立模板。在攻击阶段，每次选择明文攻击后与模板匹配，排除一部分不可能的密钥选项，降低密钥的搜索空间，直至找到密钥。

1 预备知识

1.1 基本符号

设AES-128算法的明文输入为P={p1,p2,…,p16}，密钥为K={k1,k2,…,k16}，那么S盒的输入表示为xi=pi⊕ki，输出表示为yi=S(pi⊕ki)，其中，pi∈P，ki∈K，i为S盒下标索引，1≤i≤16。

ti,q=si,qWH(x)+β+ri,q

(1)

如果从能量迹中截取到的关于S盒操作的采样点段已经对齐，那么常量si,q是与i无关的，可以简化为sq。

针对S盒的碰撞攻击是指不同的明文输入产生相同的输出，通过建立关于两个密钥的等式，进而恢复出密钥。例如，S1和S2的输入是相等的，即p1⊕k1=p2⊕k2，k2=k1⊕p1⊕p2，那么这两个密钥的搜索空间就降低到了28。如果其他密钥与k1都建立了类似的等式，那么整个密钥的搜索空间就从2128变成了28，遍历搜索k1就能恢复出所有的密钥。

密码设备在处理相同的中间值时，消耗的能量被认为是相似的，因此，两个能量迹中涉及相同中间值的片段往往被用来检测碰撞。将这两个能量迹片段(已经求过平均)分别表示为{t1,1,t1,2,…,t1,l}和{t2,1,t2,2,…,t2,l}，两个片段之间的相似程度可以用最小二乘法(least square method，LSM)描述，也就是其欧几里德距离可表示为

(2)

如果D小于某个阈值，就表示检测到了碰撞。

为了抵御侧信道攻击，边缘计算或其他密码设备中所采用的密码算法会采取一些措施，掩码方案[17]就是其中应用较为广泛的一种。带有掩码的AES算法的S盒被定义为S′(xi⊕m)=S(xi)⊕M，其中，m是S盒的输入掩码，M是S盒的输出掩码，输入和输出的掩码在AES算法每轮执行前随机产生，且至少在一轮加密中的16个S盒中使用相同的输入输出掩码，重用掩码方案如图1所示。

图1 重用掩码方案

1.2 自适应选择明文碰撞攻击

模板攻击是利用密码设备对处理不同的数据消耗的能量有不同的特征刻画模板，在攻击阶段将已知明文输入的能量消耗特征与模板匹配，以获得密钥的信息。自适应选择明文碰撞攻击[18]就是一种针对重用掩码AES算法的模板攻击，假设敌手拥有一个和待攻击设备相同的设备，则可控制明文密钥建立模板。下面将以S1和S2为例进行说明。

在建立模板阶段，令p1=k1=k2=0，p2的输入空间范围为{0,1,…,255}，使S1和S2之间输入的汉明距离h遍历{0,1,…,8}。对于每个明文p2：使用带掩码的AES算法加密明文n次，由于在攻击阶段的距离需要与模板匹配，为了降低噪声的影响，n需足够大；从每条能量迹截取两个S盒输入段子能量迹；使用最小二乘法对两段子能量迹求距离，这个距离对应了模板中的汉明距离，即h=DH(x1,x2)。这样就建立9个汉明距离对应欧几里德距离的模板。

Ding等人的理论依据是带有重用掩码的任意两个S盒之间的输入汉明距离和欧几里德距离存在以下关系[18]。

定理1如果l是固定的，Δ的取值范围为{0,1,2,…,8}。对于任意的x1，x2∈{0,1,2,…,255}，DH(x1,x2)=Δ，则期望值可表示为

(3)

式中，E(·)为期望函数。

2 改进的选择明文碰撞攻击方法

2.1 能量迹的数学表达式

汉明重量为一个字节数据的二进制形式中1的数量，8比特的数据x可表示为x=x7x6x5…x0，则有

(4)

如果x是均匀分布且相互独立的，那么WH(x)与x的个数之间的关系如表1所示。

表1 均匀分布x的汉明重量与数据个数的关系

为了方便后文描述，能量迹的数学表达式(1)可重新表示为

t=sWH(x)+β+r

(5)

研究能量迹各采样点的方差[16]可以知道，方差较小的部分是噪声或是与设备算法输入无关的常量消耗，方差较高的部分反映了处理数据的不同，是与操作数据有关的采样点，那些与S盒输入有关的采样点被称为兴趣点。

对式(5)两边求方差，一方面固定能量消耗β的方差为0，另一方面噪声部分与操作的数据无关，由此可得能量迹的方差为

V(t)=V[sWH(x)+β]+V(r)=s2V[WH(x)]+V(r)

(6)

式中，V(r)为噪声r的方差。假设数据x的每一个比特位是均匀分布的，那么x的汉明重量服从二项分布B(8,1/2)，则有

(7)

根据式(6)和式(7)，s可以表示为

(8)

对式(5)两边求数学期望，WH(x)的数学期望为4。对于固定能量消耗β，其数学期望就是其本身。噪声r服从均值为0的正态分布。因此可得

E(t)=sE[WH(x)]+E(β)+E(r)=4s+β

(9)

一旦确定了s，那么β可以表示为

β=E(t)-4s

(10)

式中，E(t)是用兴趣点处泄露能量值的平均值估计。

至此，在无掩码的情况下，式(5)中的几个参数都已经得到求解。

然而，在有掩码的情况下，式(5)变为

t=sWH(x⊕m)+β+r

(11)

密码设备的能量消耗主要与被处理数据的汉明重量有关，而不同的汉明重量代表了不同的能量消耗。因此，将利用估计的方法区分兴趣点处所代表的汉明重量。

这种区分方法依赖于能量迹中泄露的质量，只在噪声较小的情况下才有效。通过降低噪声，比如使用4阶累积量[21]方法，排序效果会更好。利用降低噪声的方法可以得到较为准确的排序，但部分元素会被排序在错误的位置，此时需要更多的能量迹减小错误带来的影响。

取出兴趣点处汉明重量为4的能量迹子集合，对式(11)两边求方差，由于sWH(4)的方差为0，固定能量消耗β的方差也为0，而噪声部分与操作的数据无关，由此可以得到

V(Tl)=V(r)

(12)

在不对能量迹进行排序的情况下，对式(11)两边求方差，得到

V(t)=V[sWH(x⊕m)+β]+V(r)=s2V[WH(x⊕m)]+V(r)

(13)

每轮的掩码是随机产生的，假设掩码m是均匀分布的，对于任意的x∈[0,255]，x⊕m在[0,255]上仍是均匀分布的(x是固定的)，即x⊕m的每一个比特位是均匀分布的，x⊕m的汉明重量服从二项分布B(8,1/2)，则有

(14)

根据式(13)和式(14)，可以将s表示为

(15)

对式(11)两边求数学期望，对于固定的x和均匀分布的掩码m，WH(x⊕m)的数学期望仍为4，可得

E(t)=sE[WH(x⊕m)]+E(β)+E(r)=4s+β

(16)

如果s被确定了，那么β可以表示为

β=E(t)-4s

(17)

其中，E(t)仍是用带有重用掩码的AES算法加密固定明文的兴趣点处泄露能量值的平均值估计。

至此，在有掩码的情况下，能量迹数学表达式(5)中的参数σ、β、s均已求解出。

2.2 基于理论计算的模板攻击

针对S盒的碰撞攻击，距离不仅指的是S盒之间的欧几里德距离，还包括汉明距离。接下来，将充分利用S盒的欧几里德距离和汉明距离之间的关系，排除部分不可能的明文输入找到碰撞。

2.2.1 基本思想

以S1和S2为例，将p1固定为一个常量，例如p1=0，p2的目标值表示为β2。令k1⊕k2=Δk，那么目标值β2=p1⊕Δk。改进的基于掩码AES选择明文碰撞攻击具体步骤如下。

步骤1计算式(1)中未知变量的值，并根据式(3)计算9个不同汉明距离对应欧几里德距离期望值，建立模板。

步骤2固定p1=0，初始化p2的候选值空间范围为0～255。

步骤3从p2的取值范围中随机选择一个元素，计算x1和x2之间的欧几里德距离，使用这个欧几里德距离与模板匹配，得到x1和x2之间估计的汉明距离，等价于DH(p2,β2)。

步骤4根据步骤3中的汉明距离更新p2的取值范围。

步骤5重复步骤3和步骤4，直到p2的取值范围只剩一个值，那么这个值就是β2。

2.2.2 攻击场景

改进的基于掩码AES选择明文碰撞攻击方法包括模板建立和攻击两个阶段。

图2 建立模板流程

攻击固定p1=0，初始化p2的取值范围为0～255，表示为C0={0,1,2,…,255}。无需遍历明文，通过循环的方式降低候选值数量。改进的选择明文碰撞攻击在每个循环中的具体步骤如下。

步骤1从C0中随机选择一个元素作为p2。

步骤2加密带有掩码的AES算法n次，将采集到的能量迹表示为{Tj|j=1,2,…,n}。

步骤4使用LSM计算x1和x2之间的欧几里德距离Dj，并对n次加密结果Dj求平均，即

(18)

此时，D对应模板中ξΔ的汉明距离h=DH(p1,p2)。

步骤5将得到的欧几里德距离与模板进行匹配，得到估计的汉明距离

(19)

h就是x1和x2之间汉明距离的估计值，也就是DH(p2,β2)=h。

步骤6将满足条件与p2异或汉明距离为h的候选值明文p放到集合C中，即C={p|DH(p,p2)=h}，并更新p2的集合C0=C0∩C。

步骤7重复上面的过程，直到C0中只有一个元素(攻击成功)，或C0是一个空集合(攻击失败)。

改进的选择明文碰撞攻击流程如图3所示，其中|C0|表示C0中的元素数量。

图3 改进的选择明文碰撞攻击流程

3 实验结果及分析

利用ChipWhisperer[22]平台完成对能量迹的采集工作，线下使用Matlab对数据进行处理分析。

3.1 对两个密钥字节的攻击

在建立模板阶段，利用式(3)求出两个S盒之间汉明距离{0,1,2,…,8}对应的欧几里德距离期望值(模板值)分别为{1.380×10-4，1.875×10-4，2.370×10-4，2.865×10-4，3.360×10-4，3.855×10-4，4.350×10-4，4.845×10-4，5.340×10-4}，如图4所示。

图4 9个汉明距离对应的模板值

在攻击阶段，设置k1=135，k2=78。令p1=0，在每个循环中，选择明文加密次数n=1 000。在第一次循环中，随机选择明文p2=104，得到D=2.751×10-4，与模板匹配得到的汉明距离为3，即DH(p2,β2)=3，更新p2的候选值集合，|C0|中的元素数量降到了56个。在第二次循环中，从更新后的集合C0中随机选择p2=237，得到D=2.238×10-4，即DH(p2,β2)=2，更新集合，|C0|中的元素数量降到了15个。在之后的循环中，每次都从集合C0中随机选择一个元素作为p2，得到相应的距离D和与模板匹配的汉明距离DH(p2,β2)，仿真实验结果如表2所示。

表2 实验的中间值数据

从表2中可以看到，在第5次循环中，C0中只剩下了201一个值，其他候选值都在前面的循环中被排除了，而k1⊕k2=135⊕78=201，攻击成功并得到了正确的目标值。

图5给出了在5次循环中选择明文攻击后与模板匹配得到的汉明距离值，其中，黑色星号表示x1和x2之间的欧几里德距离结果，虚线表示模板。

图5 在攻击中使用的5个明文匹配模板

图6给出了每次循环后存活的候选值数量，在第一次循环后，剩下了56个候选值，在第二次循环后，剩下了15个候选值，在第三次循环后，剩下了6个候选值，在第四次循环后，剩下了3个候选值，最后一次循环，只有一个候选值201被保留下来。

图6 攻击中每个循环后存活的候选值数量

(20)

在仿真实验中发现，平均需要5.2个明文找到目标值，也就是说，平均使用5.2个明文就可以检测到碰撞。

3.2 对两个密钥字节的攻击成功率对比

在不同噪声标准差环境下，改进的基于掩码AES选择明文碰撞攻击(表示为LSM)，自适应选择明文碰撞攻击(表示为DLSM)和相关碰撞攻击[17](Collision-Correlation Attack，CCA)等3种攻击方法在σ=0.002 94和σ=0.006时的成功率对比分别如图7和图8所示。

图7 σ=0.002 94时3种攻击方法的成功率对比

由图7可以看出，当σ=0.002 94时，CCA方法在6 000条能量迹时只有73.8%的成功率，LSM方法达到95%的成功率需要5 800条能量迹，DLSM方法需要5 850条能量迹，LSM方法和DLSM方法均要优于CCA方法。LSM方法和DLSM方法攻击的成功率比较接近，DLSM方法各个汉明距离的模板值基本成等差数列，与LSM方法通过计算得到的模板值比较接近。

图8 σ=0.006时3种攻击方法的成功率对比

由图8可以看出，当σ=0.006时，LSM方法在12 000条能量迹时只有65.6%的成功率，而DLSM方法可以达到85%的成功率，这种情况下LSM方法比DLSM方法的攻击成功率低19.4%。

根据自纠错能力[18](Self-Correction，SC)，验证改进的攻击方法建立模板攻击成功率的极限。在不同噪声标准差情况下，有无纠错能力的改进的基于掩码AES选择明文碰撞攻击(分别表示为SC_LSM和LSM)、有无纠错能力自适应选择明文碰撞攻击(分别表示为SC_DLSM和DLSM)和CCA等5种攻击方法在σ=0.002 94、σ=0.006、σ=0.009和σ=0.012时的成功率对比分别如图9至图12所示。

图9 σ=0.002 94时5种攻击方法的成功率对比

由图9可以看出，当σ=0.002 94时，LSM方法在4 000条能量迹时只有90%的成功率，SC_LSM方法达到95%成功率需要3 360条能量迹，增加纠错能力后，攻击成功率有明显提升。SC_DLSM达到95%的成功率需要3 511条能量迹，SC_LSM和SC_DLSM的攻击成功率仍然比较接近，这说明通过理论计算得到的模板与使用与待攻击设备相同的设备建立的模板，在低噪声情况下，无论是否使用纠错能力，改进的攻击方法和自适应选择明文碰撞攻击方法的成功率比较接近。

图10 σ=0.006时5种攻击方法的成功率对比

由图10可以看出，当σ=0.006时，SC_LSM方法在8 000条能量迹时只有80%的成功率，而SC_DLSM方法的成功率达到了94.4%，此时SC_LSM方法比SC_DLSM方法攻击的成功率低14.4%。

图11 σ=0.009时5种攻击方法的成功率对比

进一步增加噪声标准差，由图11可以看出，当σ=0.009时，SC_LSM方法在16 000条能量迹时达到了 89.6%的成功率，而SC_DLSM方法攻击的成功率只有81.4%，SC_LSM方法比SC_DLSM方法攻击的成功率高8.2%。

图12 σ=0.012时5种攻击方法的成功率对比

由图12可以看出，当σ=0.012时，SC_LSM方法在32 000条能量迹时有80.8%的成功率，SC_DLSM方法攻击的成功率只有67.8%，SC_LSM方法比SC_DLSM方法攻击的成功率高13%。

综合以上情况，噪声标准差增加到一定范围以后，改进的攻击方法攻击成功率优于自适应选择明文碰撞攻击方法。说明通过与待攻击设备相同的设备建立模板只在一定噪声范围内比较准确，噪声一旦达到了某个阈值，会影响模板的准确度，不同汉明距离对应的欧几里德距离不成线性关系。而通过理论计算得到的模板，只要参数估计准确，无论在什么样的噪声环境下，其模板的汉明距离对应的欧几里德距离一定呈成线性关系，在低噪声和某些高噪声环境下，可以更好地刻画密码设备中的能量消耗特征，并且改进的攻击方法不需要与目标设备一模一样的可控硬件建立模板，因而在实际应用中更加灵活。

4 结语

改进的基于掩码AES选择明文碰撞攻击方法利用汉明重量模型，较为准确地刻画了电路中的能量消耗。通过求解能量迹数学表达式，得到各个参数，利用参数计算出9个汉明距离对应的9个欧几里德距离期望值，从而建立了针对掩码AES任意两个S盒输入的9个汉明距离对应9个欧几里德距离的模板。仿真实验结果表明，在不同噪声环境下，改进的攻击方法在低噪声环境下恢复密钥所需要能量迹的数量和自适应选择明文碰撞攻击方法相当。在噪声标准差增加到一定范围后，改进的攻击方法建立的模板更为准确，在相同能量迹数量的情况下攻击成功率更高，并且不需要敌手拥有一个和待攻击设备相同的设备建立模板这一限制条件。