李志峰 高玉琢

摘 要：时序驱动Cache攻击是指通过分析处理器中加密算法的不同执行时间来恢复密钥，从而实现对密码系统的攻击。文章针对AES加密算法进行时序驱动Cache攻击分析：首先介绍了Cache结构和信息泄露原理，指明对算法执行过程中泄露信息的利用，描述了AES算法，对基于碰撞的时序驱动Cache攻击和基于模板的时序驱动Cache攻击进行针对AES算法的攻击分析。需要特别指出的是，AES查表操作的实现方式是主流计算机硬件系统的固有特性，目前对这类攻击难以规避，且攻击可以应用于大多数的AES实现软件。

关键词：AES;侧信道攻击;碰撞攻击;模板攻击

0 引言

传统的密码分析是通过数学理论对密码的数学结构进行分析，而侧信道攻击主要是对密码系统的实现以及运行过程中产生的侧信息，如运算时间、电磁波、能量功耗等进行攻击。基于高速缓存（Cache）的侧信道攻击是利用了在加密过程中对Cache访问时系统所泄露的信息来对密码算法进行攻击，从而获得算法的密钥。自2002年Page[1]提出了基于高速缓存的侧信道攻击方法以来，研究者们分析了Cache访问时所能利用到的不同信息，包括Cache访问轨迹、整体加密时间或者Cache访问模式。时序驱动的Cache攻击是利用密码算法执行时间所反映出的与密钥信息的相关性来对密码系统进行攻击。根据其在数据采集和处理方式上的不同，可以将这种时序驱动攻击方法分为基于碰撞的攻击和基于模板的攻击。本文将针对AES加密算法分析研究这两种攻击方法的具体实现。

1 Cache信息泄露原理

1.1  Cache结构

CPU缓存（Cache）是CPU中的快速存储区域，位于CPU和内存之间，用来存储应用程序的数据和指令，作用是减少内存访问，提高程序的执行速度。缓存中的数据是CPU即将访问的，因此避免了直接从内存读取而耗费大量时间。在现代计算机中，Cache以层次结构方式实现。一般Cache分为3级，分别为L1 Cache、L2 Cache和L3 Cache（last level Cache，LLC），其中L1 Cache是最接近CPU的一层，所以对L1 Cache的访问是最快的。一般情况下，L1 Cache又分为指令Cache和数据Cache，分别存放进程的指令和数据，而L2和L3 Cache不作区分。高级别的Cache比低级Cache大得多，并且包含低级 Cache 的内容。

1.2  Cache信息泄露

CPU通过使用Cache缓存数据来对访问内存加速。当CPU读取数据时，访问Cache的速度与访问内存的速度相差约两个数量级[4]，从而造成访问数据时由于数据所在位置不同（Cache命中与否）出现显著的时间差异。Cache侧信道攻击就是利用密码系统运算在执行过程中Cache命中与否时产生的侧信道信息结合算法实现的特性进而分析获得算法的密钥。当CPU需要进行内存读写时，它首先访问Cache，在Cache中进行查找相关数据。如果访问的数据在Cache中，则直接对Cache读写，这就是一次Cache命中（hit）。如果在Cache中没有找到所需数据，则访问内存，同时将数据读入Cache中，以备下次访问，这就是一次Cache失效（miss）。因此，当Cache命中时，它的访问时间比Cache失效时短很多（见图1）。

时序驱动Cache攻击利用了密码算法运行时整体执行时间由于Cache活动而造成的时间差异进而恢复出密钥，且不同方法的利用方式不同。内部碰撞攻击利用同一个Cache line中查找表条目的访问会产生内部碰撞，内部碰撞的发生导致更多的Cache命中，从而使得执行时间更短。攻击者通过控制输入的明文信息，根据执行时间即可推断出密钥部分比特信息。模板攻击是通过在与目标机器完全相同的机器上运行相同的密码算法实现，针对查找表的每个输入，在学习机器上获取加密时的极值点对应的输入值，以确定目标机器上的密钥信息[2]。

2 AES加密算法

AES（Advanced Encryption Standard）加密算法[3]支持128，192或256比特的不同长度的密钥。本文将研究128比特的密钥。AES加密是一个迭代过程：每轮接受一个16字节的输入分组Xi和一个16字节的轮密钥Ki来生成一个16字节的输出Xi+1。每一轮都在Xi上执行代数操作：字节替换、行移位和列混淆（最后一轮没有列混淆），以及和轮密钥进行异或。在迭代固定的轮数之后，最终的输出Xi+1即为密文。

在实现时，使用查找表方法来计算AES，总共需要使用 5个查找表：T0，T1，T2，T3，T4。除最后一轮使用表T4之外，其余AES每一轮的计算都使用表T0，T1，T2，T3。因此，每轮AES加密可以通过将Xi拆分为16个字节x0，x1，…，x15，将Ki拆分成16字节k0，k1，…，k15，并通过下面的公式进行计算：

对于最后一轮的AES，将T0，T1，T2，T3替换成表T4，得到密文C。

近年来的研究表明，由于AES的查找表结构，即在执行加密操作时需要查表的操作，使其面临着基于时序驱动的Cache攻击威胁。

3 时序驱动Cache攻击

时序驱动Cache攻击通过分析密码设备的缓存活动泄露出来的已经执行的一组操作和操作所消耗的时间来推导加密系统在计算中涉及的参量。由于时序驱动的Cache攻击所需要的设备和测量的较为简单，使得该类攻击适用范围较广。

3.1 通用模型分析

时序驱动的Cache攻击在实际操作中是研究分组密码查表时Cache访问命中和失效所泄露的侧信道信息与表项数据的函数依赖关系进而分析出密钥[4]。侧信道泄露信息M是可以采集的，通过寻找M和x之间的某种函数关系可以建立函数M=f（x），此时可以得到逆函数x=f-1（M），对M进行分析可以预测查表索引x。由x、明文P、密文C、相关密钥k以及他们之间存在的函数关系g（P/C，x）可以推斷出相关密钥k，结合密钥扩展恢复主密钥K。攻击通用模型如图2所示。

3.2 碰撞攻击

时序驱动Cache碰撞攻击原理为，攻击者利用加密AES算法某次查找同一个查找表时Cache中会发生的访问命中或者失效导致的显著时间区别对加密整体执行时间的差异的影响来进行密钥分析[5-6]。AES加密算法两次查表操作如图3所示。图中pi和pj为明文的两个字节，ki和ki为两次查表操作的相关密钥字节，xi和xj为两次查同一个查找表的索引。攻击者首先要获取大量明文样本的加密时间，即大量xi和xj的加密执行时间，然后将两次查找同一个查找表的pi和pj的所有可能异或值作为横坐标，共256种可能值，同时计算每种可能值对应的平均加密执行时间作为纵坐标的函数值，绘制一条曲线。平均执行时间最短即函数值最小的点对应的横坐标值即为这两次查表操作相关的两个密钥字节的异或值。这是因为执行第一次查表操作时发生Cache miss，系统将对应的Cache line加载到缓存中，当第二次查表操作时，如果两次查表操作的索引值相同，即xi=xj，则会发生Cache hit，在大量样本的情况下，此时的平均执行时间最小。

本文将分析AES加密操作的第一轮攻击实现。加密的         16次查表操作索引可以表示为：

式中，pi，ki，xi分别为第i次查表相关的明文字节、密钥字节和索引字节。

AES加密第一轮分别查找4次T0，T1，T2和T3表，共16次查表操作。在T0表中，如果两次查表索引相同，则第二次查表发生Cache hit，此时便有：

因为pi⊕pj已知，所以此时获得了ki⊕kj的值，此时可以恢复查找T0表的相关的任意4个密钥字节6组异或值结果，即k0⊕k4，k0⊕k8，k0⊕k12，k4⊕k8，k4⊕k12。同样，对于查找T1，T2，T3表，由式（1）所执行的查表操作，可以分别恢复出每个表中的6组值，这样第一轮攻击共可以获得24组密钥相关字节异或值，最后通过穷举等方法可以实现密钥的恢复。

当考虑到Cache访问的局部性原理时，实际可获取12×（8-logδ2）位密钥。因为主存和缓存的数据交换单位为Cache line大小，所以在实际查找表的过程中，发生碰撞的索引项高位（8-logδ2）总是相同的，其中δ表示每个Cache line中可存储查找表元素的个数。

3.3 模板攻击

模板攻击主要利用AES加密算法查找S盒时不同索引时对应的执行时间对整体执行时间的影响进行密钥分析[7-8]。在时序驱动的Cache模板攻击中，攻击者需要搭建一台同目标密码服务器相同配置环境，采集在已知密钥前提下的大量样本的平均加密时间，并计算每个查表索引对应256个可能值的平均时间下的标准差，得到一条模板曲线;然后在相同配置环境下的目标密码服务器环境上，在未知密钥情况下采集大量的样本的加密时间，再预测每个密钥字节候选值，计算每个查表索引的256个可能值的平均时间下的标准差，得到另外一条实际加密的曲线;最后通过计算这两条曲线的匹配度相似度，从而得到正确密钥的候选值，因为正确密钥的候选值对应的两条曲线匹配相似度较高。下面对AES加密算法的第一轮加密操作进行模板攻击分析。

3.3.1 模板搭建

攻击者使用一台与目标密码服务器相同配置的加密设备，在已知密钥和明文的前提下，进行加密操作。

（1）用已知密钥K'对大量随机明文进行加密，明文数量为n，收集加密时间并将其存储在数组S[i]（0≤i≤n）中。

（2）密钥K'共16个字节，AES第一轮加密共进行16次pi⊕ki（0≤i≤15）索引值的查表操作，根據每个索引的候选值将S[i]划分为256个值，并计算每个值的平均加密时间同所有256个值的平均加密时间的差，将其存储在平均加密时间标准差二维模板矩阵S'[i][j]中，其中0≤i≤15，（0≤j≤255）。

3.3.2 获取目标密码服务器实际加密操作时间信息

（1）对目标密码服务器，在未知密钥前提下对大量随机明文执行加密操作，明文数量为n，把采集到的加密时间存储在数组T[i]（0≤i≤n）中。

（2）第一轮加密操作共进行16次索引查表，首先预测每次查表操作时的密钥字节ki，共有256个候选值。对于每个ki候选值，计算n个明文样本对应的pi⊕ki值，并将T[i]划分为        256个值，计算每个值的平均加密时间和所有256个值的平均加密时间的差，并将其存储在平均加密时间标准差三维匹配矩阵T'[i][j][k]，其中0≤i≤15，0≤j≤255，0≤k≤255。

3.3.3 模板匹配

匹配方法如下，如果kj=a（0≤a≤255），则有：

（1）计算匹配矩阵0≤k≤255同模板矩阵0≤j≤255的相关性，得到的256个候选值对应的相关性系数矩阵R[a]（0≤a≤255）。

（2）将相关性系数矩阵R[a]绘制一条相关性曲线，曲线中的最高点对应的a值即为正确的ki值。

（3）按照上面的步骤依次获取所有的ki值，通过进一步分析恢复初始密钥K。

4 结语

时序驱动的Cache攻击由于其采集方法简单，平台适用性强，因此可以冲破外界环境条件的限制完成攻击。但其所需样本量大，一般要百万计，同时数据处理和分析比较复杂，如模板攻击需要大量的数据样本制作模板曲线。近些年随着Cache攻击研究的深入，越来越多的数学方法应用到侧信道信息处理和密钥分析中，如用隐马尔科夫模型、支持向量机、神经网络等，这些方法的引入不仅提高了数据分析精度以及密钥推算的准确度，还提高了密钥分析效率，是未来访问驱动的Cache攻击的重要研究方向。

[参考文献]

[1]PAGE D.Theoretical use of cache memory as a cryptanalytic side-channel[J].IACR Cryptology ePrint Archive，2002（169）：1-23.

[2]IRAZOQUI G，EISENBARTH T，SUNAR B.Cross processor cache attacks[C].Proceedings of the 11th ACM on Asia Conference on Computer and Communications Security，2016：353-364.

[3]JOAN D，VINCENT R.The design of Rijndael：AES-the advanced encryption standard[M].Berlin：Springer，2002.

[4]BOGDANOV A，EISENBARTH T，PAAR C，et al.Differential cache-collision timing attacks on AES with applications to embedded CPUs：//Cryptographers Track at the RSA Conference[C].Berlin：Springer，2010：235-251.

[5]趙新杰，王韬，矫文成，等.一种新的针对AES的访问驱动Cache攻击[J].小型微型计算机系统，2009（4）：797-800.

[6]BONNEAU J，MIRONOV I.Cache-collision timing attacks against AES[C].International Workshop on Cryptographic Hardware and Embedded Systems.Springer，Berlin，Heidelberg，2006：201-215.

[7]BERNSTEIN D J.Cache-timing attacks on AES[EB/OL].（2005-04-14）[2021-05-20].http：//cr.yp.to/antiforgery/cachetiming-20050414.pdf.

[8]吴克辉，王韬，赵新杰，等.一种基于Cache的AES计时模板攻击方法[J].军械工程学院学报，2011（2）：65-68.

（编辑 何 琳）