针对AES最后一轮加密的Cache攻击方法

1997年1月，美国国家标准技术研究所宣布开发AES加密标准，使其成为新的联邦信息处理标准，取代旧的数据加密标准DES和3DES[1]。在AES 算法中，除最后一轮外，其他每一轮都要执行这4 种变换:字节替换、行移位、列混淆和轮密钥加，最后一轮不执行列混淆变换，且常采用流水线模式进行加密，这种加密模式需要消耗大量的运算资源且效率低下，尤其是在加密大文件或大数据量时,缺点体现更加明显。在传统PC环境下，实现对大文件的AES加密变成了查表操作，虽然需要占用内存容量，但却很大程度节省了计算单元，加快了运行速度。

Cache是位于CPU与主存DRAM间的高速缓冲存储器，是为了协调CPU处理速度快而主存储器传送数据慢的硬件结构，当进程被执行时，根据替换算法策略将循环使用的数据载入到Cache中，再次使用时从Cache中快速调用，现代CPU通常有2～3个层次的缓存结构，一级缓存、二级缓存和三级缓存，与主存地址的三种映射方法：全相联、直接映射、组组映射[2]；而Cache 计时攻击又是旁路攻击中一种重要的方法，是利用一个与密码进程共享Cache的间谍进程监测密码进程对Cache 的访问情况从而获取密钥，与其他旁路攻击手段相比，具有无需物理接触密码设备、可通过网络远程获取密钥的优点,侧通道攻击初期，最常见的攻击目标是单核CPU内的L1缓存[3-4]。2014年，Yarom等[5]首次实现了跨内核/vm的Flush+Reload攻击，在GnuPG中RSA上实现，恢复超过90%的密钥位。而后Flush+Reload攻击被应用于更多的加密库和加密算法。例如，Benger等[6]推测了对OpenSSL的ECDSA签名实现上Flush+Reload攻击的方法。同年，Irazoqui等[7] 提出了更快的攻击，在云平台中，用不到一分钟的时间内恢复整个密钥位。不久之后，Zhang等[8] 在PaaS云中验证了Flush+ Reload攻击的适用性，并获得一个用户购物车的条目数。在2015年，Irazoqui等[9]展示了从错误填充cbc的TLS包中恢复隐私数据—幸运13攻击。而后，Gruss等[10]提出了在LLC缓存上应用Flush+Reload攻击检测受害者键击的方法，他们的攻击中往往需要依赖特殊手段中断加密进程才能精确计时，本文的工作是对前人工作的拓展，将flush+reload攻击方法运用于AES最后一轮加密，并提出了一种不需要干预加密进程正常执行的攻击方法。

1 AES查表实现及flush+reload缓存攻击原理

1.1 AES查表法的实现

AES加密在OpenSSL0.9.8.b[11]中的实现方法，实际就是将AES轮加密转换为查找T表的操作，查找Te0～Te3四个表，最后一轮加密查找Te4表，解密运算需要查找表Td0～Td4，每个表都是256项的32 bits大小的值构成，即用10个1 kb大小的查找表操作代替了AES的流水线运算。在明文异或初始密钥后，共进行了9轮轮加密操作，在源代码1中展示了OpenSSL0.9.8.b中的轮加密操作，以第一轮为例，每一轮的4个32 bits的输出值，由16个查找表操作完成。

t0 = Te0[s0 >> 24] ^ Te1[(s1 >> 16) & 0xff] ^ Te2[(s2 >> 8) & 0xff] ^ Te3[s3 & 0xff] ^ rk[ 4];

#由明文异或初始密钥后的状态值s0～s3四个32 bits值作为输入；

以s0的高8bits为索引值查找Te0表，得到32 bits表项值，同理查找Te1～Te3；

之后4个表项值与轮密钥前32 bits值rk[4]进行异或运算，得到该轮输出的前32 bits值。

t1 = Te0[s1 >> 24] ^ Te1[(s2 >> 16) & 0xff] ^ Te2[(s3 >> 8) & 0xff] ^ Te3[s0 & 0xff] ^ rk[5];

t2 = Te0[s2 >> 24] ^ Te1[(s3 >> 16) & 0xff] ^ Te2[(s0 >> 8) & 0xff] ^ Te3[s1 & 0xff] ^ rk[6];

t3 = Te0[s3 >> 24] ^ Te1[(s0 >> 16) & 0xff] ^ Te2[(s1 >> 8) & 0xff] ^ Te3[s2 & 0xff] ^ rk[7];

以128 bits的输入值中的8 bits为索引16次查找Te0～Te3表，与密钥扩展得到的轮密钥进行异或，得到4个32 bits的表项值，连接成为128 bits就得到了单轮的输出值，并作为下一轮的输入值。

#endif /* ?FULL_UNROLL */

* apply last round and

* map cipher state to byte array block:

(Te4[(t0 >> 24) ] & 0xff000000) ^

(Te4[(t1 >> 16) & 0xff] & 0x00ff0000) ^

(Te4[(t2 >> 8) & 0xff] & 0x0000ff00) ^

(Te4[(t3 ) & 0xff] & 0x000000ff) ^

#以第9轮加密输出t0～t3四个32 bits为输入值，取其高8 bits为索引值查找Te4表得到32 bits的表项值，而后提取表项值的前8 bits；

以t1中间16～23 bit为索引查找Te4表得到32 bits的表项值，提取中间的8 bits值，同理索引t2、t3提取另外两个8bits的表项值；

四个8 bits的表项值连接为32 bits值与轮密钥r[0]异或运算，得到32 bits的密文值，同理s1～s3。

在第9轮加密操作执行之后，源代码2展示了OpenSSL0.9.8.b中实现的最后一轮加密操作，只执行了16次查找Te4表的操作，而实际Te4表就是将8 bits表项值重复4次扩展成为32 bits长度的表项值，在源代码3中展示了OpenSSL 0.9.8b中Te4表的一部分。

最后一轮加密就是将第9轮加密输出作为本轮的输入按8 bits大小划分，以8 bits为索引查找表Te4，得到32 bits大小的表项值，并压缩到8 bits大小，然后由16个8 bits的表项值连接成为128 bits的值，异或最后一轮密钥值得到密文输出值。

1.2 flush+reload的攻击原理

在当代操作系统和管理程序中允许不同进程/用户共享相同的物理内存的。所有Linux操作系统都实现了内核相同页面的合并Kernel Samepage Merging(KSM)机制，它合并属于不同进程的重复只读内存页，KSM内核守护进程ksmd扫描用户内存，寻找可能在用户之间共享的页面，为这些页面创建签名。这些签名保存在重复数据删除表中。当发现两个或多个具有相同签名的页面时，将对它们进行完全交叉检查，以确定它们是否相同。为了创建签名,当在候选项中发现重复的页面签名并对内容进行交叉检查时，ksmd会自动使用写时复制(COW)标记其中一个重复的页面，并在进程/用户之间共享它，同时删除另一个副本。此外，VMware实现的透明的页面共享Transparent Page Sharing(TPS)，这是与KSM类似的机制，也允许不同的vm共享内存。

攻击的先决条件：

① 由于KSM机制，间谍进程和受害者(加密进程)实现主存或页面共享。

② 支持clflush指令，能够从所有缓存层次结构中驱逐数据。

③ 使用rdtsc指令能够得到精准的时间戳，或者在屏蔽指令mfence/lfence指令下得到的精确CPU周期。

图1展示了flush+reload的攻击方法，在step1中的Cache中数据块是在间谍进程和受害者间主存或页共享的，step2间谍进程通过clflush指令将该数据块从缓存中清除，step3中受害者执行加密进程，会将加密进程所使用的数据从共享主存中加载到缓存中，在step4中间谍进程重载了该数据块的主存地址，在step3之前和step4之后使用rdtsc指令记录时时间戳，如果这个数据块被加密进程所使用的，那么发生命中，检测为低的重载计时值，否则被监测到高的重载计时差值，进而遍历所有的共享地址空间，就能够得到加密时使用数据对应的活动地址集，即Te表的地址集(由于轮密钥生成操作与明文无关，轮密钥生成运算只执行一次后就直接使用，而加密查找Te表的操作要持续执行，所以在连续执行加密进程时，不用考虑Td0～Td4进入到cache中)。

2 攻击原理及步骤

① 在加密进程持续执行时，使用flush+reload基本方法判断共享主存中活动的地址集，即加密进程数据的地址，通过对源代码的学习，可以知道加密进程的数据就是表Td0～Td4、Te0～Te4、rcon的数据，rcon是拥有10个32 bits表项值的小表，加密进程不加载表Td0～Td4(Td表用于解密)，可以得到Te0～Te4地址；

② 对Te4表中第一个cacheline大小的数据块进行监控，使用flush+reload方法，记录重载监控内存块的和时间和对应的密文(< Cι[],t >)；

③ 筛选计时小于阈值即发生cache命中的密文，与监控地址内的数据Te4，共同恢复最后一轮的密钥。

2.1 获得加密进程活动地址集方法

使用mmap函数映射共享空间，在共享空间地址中查看加密操作的活动地址集。

在算法1中描述了如何获取Te0～Te4的表地址；其中，rdtsc函数由mfence/lfence屏障指令和rdtsc计时指令构成，确保指令顺序执行。

2.2 利用flush+reload方法求解密文值对应的监测计时

间谍进程对Te4表中一个Cacheline长度的数据块进行监控，在加密进程执行前对其flush操作，在加密进程执行后测量reload该Cacheline的用时t，常用加密库中加密用到的数据都经过优化，几乎都是对齐的，故不需要求解偏移地址，如果未对齐也可以选择监控Te4表中占用的第二个Cacheline数据进行实验，在实验中只需要监测Te4表中一个Cacheline大小的数据块，共16个32 bits的表项值的数据块，存储在密文字节向量(< Cι[],t >)，使用字典中键值对X= dict(′Cι[]′:t)的数据类型的采集，在算法2描述了求解该键值对的过程。

1:Input:byte *Te4[0], #以*Te4地址为例获取计时

long unsigned int Plaintext[] #明文

2:Output:X= dict(′Cι[16]′:t) #使用键值对dict的数据结构，采集密文及对应监测地址的重载时间

3:P[16]= Plaintext.split(16) #将明文按16个字节长度分割

4:flush(*Te4[0]) #将*Te4[0]地址数据从cache中驱逐

5:Cι[16] = Encryption(P[16]) #执行加密进程

6:st = rdtsc() #记录时间戳

7:reload (*Te4[0]) #重新将*Te4[0]地址数据载入到cache中

8:ed = rdtsc() #记录时间戳

9:t=ed-st #记录重载时间

10:return X= dict(′Cι[16]′:t) #返回密文和其对监控地址的重载计时

2.3 密钥恢复算法

Cι表示M组密文中的第ι组密文，定义一个阈值，提取小于时间阈值的多组密文值Cι′，这些密文在最后一轮加密时使用了监控的Cacheline内的数据，即发生了Cache命中，Cι′=(c0,…,c15),在源代码2中以s0为例展开：

s0 =(Te4[(t0 >> 24)] & 0xff000000) ^(Te4[(t1 >> 16) & 0xff] & 0x00ff0000) ^(Te4[(t2 >> 8) & 0xff] & 0x0000ff00) ^(Te4[(t3) & 0xff] & 0x000000ff) ^rk[0];

rk[0]代表32 bits的密钥值，按8 bits长度展开，则

rk[0]=( k0,k1,k2,k3)；

代入k0到s0中，以32 bits分割s0则

c0= Te4[(t0 >> 24)] & 0xff000000^k0；

在源代码3中，由于采取重复值扩展，可得

Te4[(t)] & 0xff000000= Te4[(t)] & 0x00ff0000=

Te4[(t)] & 0x0000ff00=Te4[(t)] & 0x000000ff；

用16个8 bits长度的A0…A15代替最后一轮四个32 bits 输入值t0～t3，那么t0 >> 24代表最后一轮输入的第一个byte值，可表示为A0，则

c0= byte(Te4[(A0)])^k0，那么有

k0= byte(Te4[(A0)])^c0

得到了恢复最后一轮密钥值一般公式：

ki=byte(Te4(Aj)) ^ c i，其中k i代表最后一轮第i位byte密钥值，Aj代表行移位操作产生的偏移。

恢复密钥简码如算法3所示，对于每组发生命中的密文值，需要在被监控Cacheline数据块中的16个表项值和16个密钥位置间进行定位，会产生256个算数值。

1:Input:long unsigned int X[],long unsigned int Threshold

3:int Count_key[] #定义密钥值的统计数

4:byte Y[][16] #定义一个m行16列的密文数组

5:Cι[16] = Ciphertext.split(16) #将密文按16字节长度分割

6:forι= 0 to M do #筛选发生cache命中的密文

8: Y[m][16] ← Cι[16]

10:for i=0 to 15 do#循环恢复最后一轮16位密钥字节

11: int Count_key[16]={0}

12: for ι′ = 0 to m do #使用m个命中密文计算

13: for j = 0 to 15 do

#每次命中，可能来源于被监控cacheline大小的内存块中的16个字节，每个内存块中字节都要计算

14: Count_key[Y[ι′][i] ^ Te4[0][j]]++

#统计相同密钥值的计数

17:k[i] = Count_key.index(max(Count_key[])) #最大计数值对应的索引数据，就为第i个密钥字节的正确值

19:return K9[]={k[0],k[1],…,k[15]}#K9最后一轮的密钥值

图2展示了对最后一轮密钥的第二个字节k1的攻击，对Te4表的第1组64 byte大小的数据块Te4[0]进行监控，在加密进程执行后，从M组密文中收集reload时间小于阈值的m组，即发生命中，这些密文在加密的最后一轮使用了被监控的数据块，对这些密文值进行图2中的运算，其中只有一个是正确的数值，通过对计算值Count_key[Y[ι′][i] ^ Te4[0][j]]的统计，最多的共有解max(Count_key[])对应的Y[ι′][i] ^ Te4[0][j]为正确的密钥值，如下：

中ι′代表m组命中密文组中的第ι′个，对应的max(Count_key[k])为4，是实验中计数最多的，即k1 = b3。

3 实验结果

实验是在Ubuntu16.04.3系统中，以OpenSSL0.9.8.b加密库中AES算法为攻击目标，实验设备为Intel i5-4590四核心、3.3 GHz的CPU处理器，该处理器有3层Cache结构，每个core上的存储结构相同，一个L1数据缓存和L1指令缓存，都为32 kb大小、一个256 kb大小的L2缓存，四个core共用一个6 MB大小的L3缓存。其每个Cacheline大小为64 bytes，每个Te4表中的元素为4 bytes，所以1次攻击可以检测16个表值是否发生命中，图3展示了对命中、未命中两种情况各10 000次攻击数量的计时分布，通过实验可以观测到Cached数据重载计时相对集中，主要因为缓存技术成熟，L1、L2、L3缓存速度差异不明显，导致缓存不同层级间的计时差异不到5个CPU周期，Cached数据计时平均值在5个周期，而Uncached数据重载计时相对分散，平均值在26个周期，差距在11个周期，取阈值(2tCached+tUncached)/3等于11，恰好能区分97%以上的计时值，这个阈值是通过图4中实验得出的最优解。

为了获得准确的密钥值，本实验取103量级的共有解作为密钥值，图4表示了恢复正确密钥与密文数据量之间的关系，在获得280×103组密文数据量后，就能够完整的恢复最后一轮密钥值，而理论需要256×103组密文，是实际值的91.5%，对比图3的97%分辨率差距6.5%左右，证明在加密进程不同于单纯的数据替换，在加密进程执行时，系统的其他进程会产生额外的噪声影响，且密文数据在280×103之前显示为逐渐上升的曲线，证明最后一轮16个密钥字节中的部分密钥字节先达到103量级，优先被确认恢复，不同于理想的所有密钥字节的平行恢复，这是因为产生命中密文的相关密钥位置是随机的，命中密文不是平均使用16个密钥字节的，更加符合实际情况。

4 结论

本文工作是从OpenSSL0.9.8.b的AES加密实现代码中找到了可实施Cache攻击的薄弱点，提出了一种通用性强、不依赖偏移地址、不需干预加密进程、不需加密前明文数据预处理的攻击方法。实验表明对比使用Flush+Flush攻击方法，Flush+Reload攻击具有更好的分辨率，FF方法的数据替换只能区分93%的计时，本文提出的攻击方法能够分辨97%以上的计时值，且Cached与Uncached数据计时差异明显。不需要特殊手段中断加密进程，使得此攻击更加有效、更加适用于真实的加密环境。在加密进程执行时进入缓存的数据只有明文和T表的数据，也可对明文进行标记，使其区别于T表的数据作为明文输入，执行更加精准的攻击，然而此攻击依赖于加密算法单次访问Te4表，如果多次访问，就要去除更大体量的噪音值，下一步将完善此进程，应用与其他加密算法库实现的AES查表法。

[1]DAEMEN J,RIJMEN V.AES the advanced encryption standard[J].The Design of Rijndael,2002(3)：71-74.

[2]PATTERSON D A,HENNESSY J L,GOLDBERG D.Computer architecture:a quantitative approach[M].Morgan Kaufmann Publishers Inc.2008.

[3]RISTENPART T,TROMER E,SHACHAM H,et al.Hey,you,get off of my cloud:exploring information leakage in third-party compute clouds[C]//Proceedings of the 16th ACM conference on Computer and communications security.ACM,2009:199-212.

[4]ZHANG Y,JUELS A,REITER M K,et al.Cross-VM side channels and their use to extract private keys[C]//Proceedings of the 2012 ACM conference on Computer and communications security.ACM,2012:305-316.

[5]YAROM Y,FALKNER K.Flush+reload:a high resolution,low noise,L3 Cache side-channel attack[C]//Proceedings of the 23rd USENIX conference on Security Symposium.San Diego:Association,2014:719-732.

[6]BENGER N,VAN DE POL J,SMART N P,et al.“Ooh Aah…Just a Little Bit”:A small amount of side channel can go a long way[C]//International Workshop on Cryptographic Hardware and Embedded Systems.Springer,Berlin,Heidelberg,2014:75-92.

[7]IRAZOQUI G,INCI M S,EISENBARTH T,et al.Wait a minute! A fast,Cross-VM attack on AES[C]//International Workshop on Recent Advances in Intrusion Detection.Springer,Cham,2014:299-319.

[8]ZHANG Y,JUELS A,REITER M K,et al.Cross-tenant side-channel attacks in PaaS clouds[C]//Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security.ACM,2014:990-1003.

[9]IRAZOQUI G,INCI M S,EISENBARTH T,et al.Lucky 13 strikes back[C]//Proceedings of the 10th ACM Symposium on Information,Computer and Communications Security.ACM,2015:85-96.

[10]GRUSS D,SPREITZER R,MANGARD S.Cache template attacks:Automating attacks on inclusive last-level caches[C]//24th {USENIX} Security Symposium({USENIX} Security 15).2015:897-912.

[11]GULLASCH D,BANGERTER E,KRENN S.Cache games：Bringing access-based cache attacks on AES to practice[C]//2011 IEEE Symposium on Security and Privacy.IEEE,2011:490-505.