基于ARM处理器的AES缓存攻击技术研究

Research on AES Cache Attack Technology Based on ARM Processor

摘要: Cache攻击是一种强大的攻击工具，能够根据Cache泄露的内存访问模式获取用户的私密信息，比如用户的键盘输入、加密的密钥等。在Intel x86平台上，已经有针对AES、DES加密算法的Cache攻击实现，但是在Android平台上，由于Cache结构、指令集、Cache替换策略等与Intel x86有很多差别，因此攻击难度较大。本文基于Android平台，以AES加密算法作为攻击对象，通过引入假设检验，降低随机误差对实验结果的影响，最终获取AES全部密钥。最后对AES异步攻击方式进行探索。

Abstract: Cache attack is a powerful attack tool that can access the user’s private information based on the memory access mode revealed by the Cache, such as the user’s keyboard input, encryption keys, etc. On Intel x86 platform, there have been Cache attack implementations aiming at AES, DES encryption algorithm, but on the Android platform, the structure of the Cache, instruction Set and Cache replacement strategy have a lot of differences from that of Intel x86, so Cache attack on mobile devices is difficult. This paper reduces the impact of random error of the experimental results on the Android platform by introducing hypothesis testing, eventually getting all AES key bytes. Then this paper explores the asynchronous attack mode.

2. 相关技术

2.1. 计时方式

由于Cache攻击是通过监测访存与访缓存之间的时间差异来进行攻击的，因此首先需要能够在目标平台上获取到精确的计时方式。本文采用的是POSIX提供的clock_gettime计时接口，它能够返回当前系统时间，精确到纳秒，调用方式如表1所示。

get_time方法能够返回精确的系统时间，图1通过POSIX提供的接口测量访存和访问Cache的时间差距。该实验首先通过get_time函数统计50,000次Cache命中(蓝色柱状图)和Cache缺失(红色柱状图)的时间，然后将测量得到的时间统计到一张图中。其中图表的横坐标表示统计时间，单位为纳秒，纵坐标为在单个时间点上统计的次数。

从上图可以看出，红色圆柱相对于蓝色圆柱有向右的偏移，反映到访问时间则是Cache命中需要时间比Cache缺失的时间短，也反映了POSIX计时方式的有效性。

2.2. 驱逐策略

为了获取Android平台上程序的内存使用情况，需要启动另外一个程序，通过不断的探测内存映射到的Cache Set，根据访存时间的多少判断该Set有没有被被攻击程序使用到。探测的方式为：1) 攻击程序通过读取大量内存空间中数据将某个Cache Set中存储的数据驱逐到内存中，此时新读取的数据占据了

Table 1. POSIX timing

表1. POSIX计时

Figure 1. Cache hit and miss experiment

图1. Cache命中与未命中实验

该Cache Set中所有的Cache line；2) 被攻击程序运行，其运行期间的访存操作可能会将数据缓存到待探测的Cache Set中；3) 攻击程序检测第一阶段缓存到Cache中的数据是否还保存在Cache Set中，其判断依据是访问数据的时间，如果数据还在Cache中，则访问数据将从缓存中获取数据，因此时间较短。

为了获取高效的Cache驱逐策略，本文依据Gruss et al. [11] 提出的表2所示的获取驱逐的思想，通过表2算法，在Android平台上对可能的驱逐策略组合进行测试，最终选择驱逐效果最好的参数组合进行攻击。

3. 同步攻击

AES攻击

AES执行过程中对各个Table的查表操作是对其进行Cache攻击的切入点，对于相同的密钥k，对于不同的明文p进行加密时，根据计算，会访问到各个Table中不同索引位置，如果Cache中没有缓存相应位置的数据时，会将该数据以及其周围的数据加载到其内存所对应的Cache Set的某一个line中，加载的数据块大小与Cache line大小相等。本文针对Lenovo k51c78测试机进行实验，其Cache line大小为64字节，Table中的每项数据为4字节。加密过程中每次访问Table中的数据时，会将其周围共16个数据项加载到同一个Cache line中。因此，如果T₀中起始数据所在内存对应Cache中某一Set a中某一Cache line的起始位置，则T₀中索引前16项的数据都将映射到Set a中，而索引第16至第32项数据将映射到Set a + 1中，Table中索引为i的数据将映射到的 Set索引为a + (i/16)。

攻击程序通过对自身内存进行访问，能够获取到其他程序使用Cache的情况。在攻击过程中，通过Moritz Lipp et al. [11] 介绍的Prime + Probe攻击方式，其中Prime + Probe为Cache攻击的基本策略之一，其分为两个步骤：Prime阶段通过读取能够映射到某个Set中的数据将该Set中之前的数据驱逐到内存中，Probe阶段则监测Prime阶段读取的数据是否还缓存在Cache中。

因此，攻击程序首先通过Prime方法读取其内存空间的数据占用Cache中指定Set中的所有line，然后调用AES加密程序，待加密程序执行完毕之后，执行Probe方法，根据Probe访问时间判断Prime阶

Table 2. Evicting Algorithm

表2. 驱逐策略算法

段读取的数据是否还保存在Cache中。若均还在Cache中，则表示AES加密过程中的多轮查表操作没有访问到能够映射到该Set的数据。反之，若Probe阶段探测到之前读取的数据不在Cache中，则表明AES加密过程中的某一轮查表操作或其他访存操作访问到了能够映射到该Set的数据。为了简化攻击操作，假设AES加密过程中除了查表操作外不存在其他访存操作。因此，假设已知AES中各个索引表的起始地址对应的Cache Set索引，当攻击程序同时对Cache中的所有Set进行监控时，就能够监测到AES加密过程中访问了T₀、T₁、T₂、T₃中哪些区域的数据。

为了方便讨论，本文将以目标机Lenovo k51c78为例，讨论以其作为被攻击设备，设计针对AES加密算法的攻击的方案。该目标机的L2 Cache大小为512KB，及共有512个Set，Cache组织为16路组相联。因此每个Set共有16个Cache line，每个Cache line能缓存64字节的数据。被攻击的AES加密程序有T₀、T₁、T₂、T₃ 4个主要的索引表，其中每个索引表包含256个数据项，可将其视为有256个元素的数据，其中每个数据项为4字节，并且假设已知索引表的首地址a对应的Cache Set索引i，为了方便讨论，假设a的取值满足a%64 = 0，表示索引table的首地址映射到Cache line的起始位置，效果如图2所示。因此，能够求得索引表中任意索引位置n对应的Cache Set位置，其表示当该位置数据被访问时其将被缓存的Cache Set号。由于攻击程序通过Prime + Probe只能探测到被攻击程序访问Cache Set的情况，并不能区分访问了Cache Set中哪些line，更不能获取Cache line中偏移的情况，因此通过Prime + Probe攻击程序并不能区分对索引表T₀中索引0到索引15数据项的访问(对0到15项的任意一项的访问都将一整块的数据缓存到了Cache中)。

本文设计通过假设验证的方式来实现获取AES密钥，其破解过程分为两轮，第一轮获取密钥中每个字节的前4位，称为第一轮攻击，第二轮获取密钥中每个字节的后四位，称为第二轮攻击。

第一轮攻击

第一轮攻击首先计算出AES加密过程中第一轮的查表索引，结合AES内存空间中各个查表索引Table

Figure 2. The map between AES table and Cache

图2. AES索引表与Cache映射情况

的首地址，计算得到对AES进行攻击时需要检测的Cache Set。本文的实验中假设AES加密明文为p，密钥为k，并假设T₀、T₁、T₂、T₃的首地址对应的Cache Set号为 $s_0$ 、 $s_1$ 、 $s_2$ 、 $s_3$ ，因此可以计算得到

第一轮需要监测Cache Set号： $s_0+\left(p_0\oplus {\hat{k}}_0\right)/16$ 、 $s_0+\left(p_4\oplus {\hat{k}}_4\right)/16$ 、 $s_0+\left(p_8\oplus {\hat{k}}_8\right)/16$ 、 $s_0+\left(p_{12}\oplus {\hat{k}}_{12}\right)/16$ 、 $s_1+\left(p_1\oplus {\hat{k}}_1\right)/16$ 、 $s_1+\left(p_5\oplus {\hat{k}}_5\right)/16$ 、 $s_1+\left(p_9\oplus {\hat{k}}_9\right)/16$ 、 $s_1+\left(p_{13}\oplus {\hat{k}}_{13}\right)/16$ 、 $s_2+\left(p_2\oplus {\hat{k}}_2\right)/16$ 、 $s_2+\left(p_6\oplus {\hat{k}}_6\right)/16$ 、 $s_2+\left(p_{10}\oplus {\hat{k}}_{10}\right)/16$ 、 $s_2+\left(p_{14}\oplus {\hat{k}}_{14}\right)/16$ 、 $s_3+\left(p_3\oplus {\hat{k}}_3\right)/16$ 、 $s_3+\left(p_7\oplus {\hat{k}}_7\right)/16$ 、 $s_3+\left(p_{11}\oplus {\hat{k}}_{11}\right)/16$ 、 $s_3+\left(p_{15}\oplus {\hat{k}}_{15}\right)/16$ 。

在获得第一轮攻击访问的Cache Set之后，通过攻击程序检测这些Set的访问情况。首先，通过Prime操作占用指定的Set，然后执行AES加密算法，最后通过Probe测量时间判断Prime阶段读入的数据是否还在Cache中。由于单次实验获取的时间作为度量分会映入计时方式导致的误差，因此可以针对每个明文进行多次实验，最后取平局值或通过KS检验与Cache hit情况下的时间进行度量。

本文通过假设检验方式破解用户密钥，首先假设密钥的取值，然后根据密钥的假设值以及明文计算得到一组访问索引，对索引进行计算可以得到对应的Cache Set访问索引，最后通过对这组Set进行监测，判断其在AES算法执行过程中的访问情况。本文在进行第一轮攻击的验证过程中，假设密钥k为k = (0 × 00, 0 × 11, 0 × 22, 0 × 33, 0 × 44, 0 × 55, 0 × 66, 0 × 77, 0 × 00, 0 × 11, 0 × 22, 0 × 33, 0 × 44, 0 × 55, 0 × 66, 0 × 77)，根据第一轮攻击方式对其进行攻击获取密钥如图3、图4所示。

图3、图4中从左到右从上到下表示密钥k第0字节到第15字节的攻击结果，图中横坐标表示密钥字节前4位的假设值，纵坐标表示可疑度的高低，其中可疑度越高表示可能性越大，因此，本轮攻击得到的密钥的每个字节的前四位为：(0 × 0, 0 × 1, 0 × 2, 0 × 3, 0 × 4, 0 × 5, 0 × 6, 0 × 7, 0 × 0, 0 × 1, 0 × 2, 0 × 3, 0 × 4, 0 × 5, 0 × 6, 0 × 7)。可见第一轮攻击能够获取到密钥所有字节的前4位。

第二轮攻击

第二轮攻击过程与第一轮攻击过程类似，同样适用假设检验的方法。通过计算可以得到AES在第二轮中的访问索引如表3所示。

在进行攻击的过程中，首先将第一轮攻击的结果带入到假设的密钥 $\hat{k}$ 中，并结合表3，然后通过假设检验的方式分组对密钥字节的后四位进行假设，并确保假设值能够遍历密钥的取值空间。通过同时假设 $k_0,k_5,k_{10},k_{15}$ 后四位的取值就能得到访问索引 $n_2$ ，通过对 $k_3,k_4,k_9,k_{14}$ 同时进行假设就能够得到访问索引 $n_5$ ，通过对 $k_2,k_7,k_8,k_{13}$ 同时进行假设，就能得到访问索引 $n_8$ ，通过同时对 $k_1,k_6,k_{11},k_{12}$ 的后四位进行假设就能够得到访问索引 $n_{15}$ 。

与第一轮攻击相同，在获取到AES查表索引后就能计算得到在执行Cache攻击中需要监测的Cache Set号。在攻击过程中，首先假设密钥值为 $\hat{k}$ ，当对明文p进行加密时，通过计算得到访问的Cache Set号。然后攻击程序通过Prime + Probe检测该Set的访问情况，为了降低偶然因素对实验结果的影响，检测过程执行多次，最后通过KS检验将其与一组模板样本进行比对，最后得到该密钥 $\hat{k}$ 的可疑度，其中模板样本中的数据为所有检测的地址都Cache命中的时间。其中KS检验为假设检验中的一种，可以判断两个分布是否为同一个分布，其返回0到1的值，越靠近0表示两个分布越相似。

与第一轮攻击相同，第二轮攻击使用假设检验的办法，并引入KS检验降低实验误差。本文实验设置密钥k为(0 × 00, 0 × 11, 0 × 22, 0 × 33, 0 × 44, 0 × 55, 0 × 66, 0 × 77, 0 × 00, 0 × 11, 0 × 22, 0 × 33, 0 × 44, 0 × 55, 0 × 66, 0 × 77)，由于第一轮攻击获取了每个密钥字节的前4位，因此还有16 * 4位数据等待获取。通过本节介绍的方法，获取得到的结果如表4、表5、表6、表7所示。

以上各图表示Cache攻击第二轮攻击的结果，其中每个表的每一行的前4项表示假设密钥字节组合，

Figure 3. The result of AES first 8 bytes in first round attack

图3. AES第一轮攻击前8字节结果

Figure 4. The result of AES last 8 bytes in first round attack

图4. AES第一轮攻击后8字节结果

Table 3. The indices of AES in second round

表3. AES第二轮访问索引

Table 4. The result of ( k 0 , k 5 , k 10 , k 15 ) in second round

表4. 第二轮攻击结果 $\left(k_0,k_5,k_{10},k_{15}\right)$

Table 5. The result of ( k 4 , k 9 , k 14 , k 3 ) in second round

表5. 第二轮攻击结果 $\left(k_4,k_9,k_{14},k_3\right)$

Table 6. The result of ( k 8 , k 13 , k 2 , k 7 ) in second round

表6. 第二轮攻击结果 $\left(k_8,k_{13},k_2,k_7\right)$

比如表4中最后一行表示假设 $\left(k_0,k_5,k_{10},k_{15}\right)$ 的值为 $\left(0,5,2,7\right)$ ，最后一列表示该组合的度量分，其中度量分数表示同一行4个密钥组合的可疑度，可疑度越高表示该行的密钥组合为真实的密钥值的可能性越高，因此可疑度最高的行就是Cache攻击估计的结果。可见 $\left(k_0,k_5,k_{10},k_{15}\right)$ 每个字节后四位取值为 $\left(0,5,2,7\right)$ 的可疑度为0.9533185，由于每4个字节后四位组合共有65,536种可能性，因此表中仅仅列出可疑度最高的7中组合。其中每个表中可疑度最高的组合就是攻击结果，因此可以获得AES每个字节的

Table 7. The result of ( k 12 , k 1 , k 6 , k 11 ) in second round

表7. 第二轮攻击结果 $\left(k_{12},k_1,k_6,k_{11}\right)$

后四位为(0 × 0, 0 × 1, 0 × 2, 0 × 3, 0 × 4, 0 × 5, 0 × 6, 0 × 7, 0 × 0, 0 × 1, 0 × 2, 0 × 3, 0 × 4, 0 × 5, 0 × 6, 0 × 7)，与第一轮攻击获取的前4位组合起来得到攻击结果 $\hat{k}$ =(0 × 00, 0 × 11, 0 × 22, 0 × 33, 0 × 44, 0 × 55, 0 × 66, 0 × 77, 0 × 00, 0 × 11, 0 × 22, 0 × 33, 0 × 44, 0 × 55, 0 × 66, 0 × 77)，与设置的密钥k相同，因此成功获取了全部密钥信息。

4. 异步攻击设计

上一章节介绍的攻击方式是同步攻击，与异步Cache攻击不同，同步攻击中被攻击程序对攻击程序来说是可控的，也就是说攻击程序能够控制被攻击程序何时执行，并知道被攻击程序何时执行完毕，以攻击AES高级加密算法为例，攻击程序能够触发AES加密程序的执行，并能够获取被加密的明文。但对于异步攻击来说，被攻击程序是完全不可控的，攻击程序只知道被攻击程序正在执行，因此攻击难度大大增大。

尽管上一章介绍的针对AES的同步攻击能够非常有效的恢复所有密钥，然而其需要攻击程序与被攻击的AES加密算法之间有交互，AES加密过程的明文对被攻击程序来说是可见的，且被攻击程序能够在加密过程之前或之后执行代码。本文探索针对AES高级加密技术的异步攻击，由于攻击程序不能控制加密的内容，攻击程序将在加密程序在相同的核上执行攻击程序，且他们之间没有显式的交互，攻击程序对加密程序仅有的了解是明文的分布情况，在本文中，假设明文是字母的组合。攻击程序将通过对自己内存空间的数据进行读取来获取攻击程序对Cache的使用情况，并依此破解AES的部分信息。

与同步攻击类似，异步攻击同样是通过假设验证的方式来破解AES密钥，首先假设AES密钥值为k，由于对于确定的明文p和密钥k就能够确定AES加密过程中访存情况，然而由于在异步攻击过程中，明文p是未知的，攻击者仅仅知道明文的分布情况，比如明文p全是字母，由于字母的ascii码十进制在141到172之间，转换16进制则在61到7A之前，因此如果假设明文仅仅为小写字母的组合，且分布完全随机的话，则明文的前四位为6的概率为15/26，前四位为7的概率为11/26。所以在第一轮攻击中可以假设明文前四位为6，及明文的十六进制设为p = 0 × 6*，其中*从0~F中取值，假设密钥十六进制表示为k = 0 × nm，其中n和m均从0~F中取值，则k异或p则得到AES在执行加密过程中的对T-table的访问索引，AES加密过程中会经过10轮变换，每一轮都密钥变换都需要查表，其中第一轮查表索引I = p^k，其他轮的变换要相对复杂很多，因此当明文和密钥已知时，通过简单的异或操作就能求出第一轮查table的索引，当知道Table的首地址，以及首地址映射的Cache Set时，就能推测出第一轮查表操作访问的内存映射的Cache Set。在针对AES的Cache异步攻击工程中，由于明文为小写英文字母的组合，因此p = 0 × 6*，假设的k = 0 × nm，则第一轮访问索引为i = 0 × 6* ^ 0 × nm。通常一个内存块大小64字节，一个table项大小为4字节，因此索引的后4位对应在字节块中的偏移，映射到Cache中则对应索引再Cache line中的索引，前4位则影响第一轮加密过程中访问table数据映射到的Cache Set号。当进行异步攻击时，由于明文p的前4位为0 × 6，当假设的密钥k遍历其取值空间时，计算0 × 6^ 0xn，并根据AES table首地址映射到的Set索引，相加就能得到预期的Cache访问情况，并验证该Set在aes运行期间的访问情况就能获取此轮假设密钥k值得度量分数，当获取到所有密钥取值的度量分时，进行排序，度量分最高的假设即为破解得到密钥值。

为了获取密钥假设值k的度量分，在执行异步攻击时，可以首先获取Cache Set的访问频率，并将其类比为代表密钥值k的可疑度，或称之为度量分m。对于Cache中的每一个Set，攻击程序通过一个循环不断的获取该Set的访问情况，监测该Set有没有在被攻击AES加密过程中被访问到(具体的监测方式为：首先执行Prime操作，通过读取若干与该Set相关的地址占据该Set中的所有line，再执行Probe操作，检查在Prime阶段读取的数据是否还保存在该Set中，判断方式为比较Probe操作所花的时间，若所花的时间较短，则该Set没有被AES加密过程访问到，否则表示该Set被AES加密过程访问到了)。当只有攻击程序使用Cache时，所有的访存操作均能命中Cache，因此Probe获取的访问时间很快。然而，当被攻击的AES加密操作访问到某被监听的Set时，则会导致攻击程序映射到Cache中的某些line被驱逐到内存中，则该Set的监控时间相对较长。因此攻击者可以通过度量Set的被访问的次数来表示其度量分。

5. 结束语

移动设备安全关乎用户的隐私安全、财产安全甚至生命安全，然而由于Cache的设计缺陷，攻击者能够在不获取额外权限的情况下，通过对本地内存空间地址监测，获取到被攻击程序在运行期间的内存访问模式，并能够依此分析出用户的私密信息，包括用户的输入、加密算法密钥等。在本文的实验中，通过KS检验减少计时误差以及Cache替换策略对度量假设密钥可疑度的影响，成功获取了AES加密算法的全部密钥字节。因此，Cache相关漏洞应该得到系统设计人员以及软件开发人员的重视，以降低泄露用户私密信息的风险。