基于欧式距离的AES算法模板攻击

李志明，唐永中

河西学院 信息技术中心，甘肃 张掖 734000

21世纪，科技发展已经渗透到人们生活的方方面面，计算机、智能手机和智能家居已经成为每个人生活的必需品。与此同时，安全问题成为了人们关注的重点，尤其是个人信息安全和智能家居的安全问题。2018年计算机爆发的Meltdown和Spectre漏洞[1-3]，利用旁路攻击方法分析硬件泄露的信息获取私密信息。该组漏洞给行业带来巨大的损失，尽管各大厂商从软件层面封堵漏洞，但硬件设计缺陷却难以用软件的方式来弥补。旁路攻击是近年来密码分析的研究重点问题之一，主要利用设备在运行时泄露的物理信息来获取重要私密数据，这些物理信息通常为电磁、电流、声音、时间等[4-5]，这种攻击方式实现时不易被发现，且不会阻碍设备的正常运行，在破解密码算法时，有着良好的效果。

加密是保护信息安全的方式之一，现在的加密算法主要有对称加密和非对称加密算法，AES算法就是典型的对称加密算法。由于DES算法密钥较短，随着计算机计算能力的不断提升，DES算法很容易被计算机暴力破解，尽管3DES算法增强了DES算法的密钥长度，但不是一个全新设计的算法，没有解决根本问题[6]。AES算法的提出解决了DES算法的困境，算法提供128、192和256位密钥，算法强度也得到加强，在有限的时间内通过暴力破解AES算法是几乎不可能实现的。相对于非对称密钥，AES具有快速高效的特点，在众多领域使用都较为广泛。即使算法设计再完美，在硬件或软件实现时，算法运行的态势也可能会被硬件的缺陷而泄露出来，密码分析者就能够通过分析泄露的物理信息获取算法的密钥。

Cache计时攻击属于旁路攻击的一种，通过利用计算机进程共享的Cache来获取密码算法运行时从Cache中泄露的计时信息来分析加密算法的密钥，并且能够在进程建立隐蔽信道，通过隐蔽信道将获取的密钥传输到攻击进程中，达到获取加密算法密钥的目的[7]。Cache计时攻击的关键则是如何区分Cache命中与Cache失效，但在现在的计算机中，通过利用rdtsc或rdtscp指令能够轻易地获取进程运行某一个片段消耗的CPU时钟周期，从而使Cache计时攻击成为可能。由于Cache计时攻击实现的基础是基于计算机硬件设计的缺陷，所以很难去防御，这种攻击方式很早被提出，但在最近几年仍对计算机造成巨大的威胁[8-10]。

模板攻击是旁路攻击方法的一种，攻击过程分为建模和匹配两个阶段，建模阶段是通过已知明文攻击，建立Cache泄露的计时信息与密钥之间的依赖关系，匹配阶段是将采集的Cache计时信息与模板之间进行匹配，相关性越大，恢复密钥的成功性越高。2020年，樊昊鹏等人仅使用10条相同密钥加密所产生的能量即恢复出AES-128算法正确的密钥[11]；2020年，Luo等人利用模板攻击从硬件角度评估混沌分组密码系统的安全性，并证实模板攻击能够用于攻击混沌密码系统[12]。但实现模板攻击的前提较为苛刻，需要相同或者类似硬件设备，针对Cache而言，模板攻击只需要相同的处理器就能恢复出密钥的相关信息，与运行的系统关系不大，故针对Cache的模板攻击具有一定的通用性。

分析现有的AES算法Cache计时攻击，都会驱逐密码进程在Cache中的数据，并进行二次访问，以确认该Cache行是否被加密算法使用，这种攻击算法的缺点是会引起大量的Cache失效，从而易被计算机检测出来以阻止攻击。通过利用Flush+Flush攻击模型，只需要计算flush指令的时间，不会造成大量的Cache失效。将这种采集计时信息的方法用于模板攻击，使得攻击更为隐蔽，不易被发现。

1 相关基础知识

1.1 Cache信息泄露原理

在计算机的存储体系中，由于CPU和存储的不对称发展，普通存储无法满足CPU高速运转的需求，Cache的提出较好地解决了这一问题，但因为高速存储Cache的造价昂贵，在计算机中通常采用三级Cache，且容量都较小，所以Cache中只存储CPU常用或即将使用的数据。替换策略是如何从内存中合理将数据加载到Cache中，减少发生Cache失效的次数，以提高CPU的运行效率。在X86处理器中，常用的替换算法有最不经常使用（LFU）、近期最少使用（LRU）和随机替换算法[13]。

当CPU从Cache中读取数据失败时，数据会从内存加载到Cache中，从而导致读取数据的时间较长。密码程序加解密时，由于频繁使用S盒，在程序运行时则会将S盒数据加载到Cache中，以提高CPU运行效率。在intel处理器中，使用rdtsc或rdtscp指令能够提供CPU时钟周期级别的精准计时，这为Cache计时攻击提供了工具。不考虑指令消耗的CPU时钟周期，Cache命中与失效的时间消耗如图1所示。从图1中，很容易区分Cache命中与失效，在命中与失效的时间消耗之间设置一个阈值，时间消耗高于阈值为Cache失效时消耗的时钟周期，低于阈值为Cache命中时消耗的时钟周期。通过使用clflush指令来刷新指定的Cache行，针对一个确切的Cache行地址，利用Cache命中或失效确认该地址是否被密码进程使用。

图1 Cache命中与失效的时间消耗Fig.1 Time consumption of Cache hits and failures

1.2 AES算法快速实现

AES算法是对称密钥算法的一种，算法的加密和解密流程是相反的操作。在AES算法运行过程中，除了第一轮和最后一轮略有不同外，算法每一轮加密由字节代替（SubBytes）、行移位（ShiftRows）、列混淆（MixColumns）和轮密钥加（AddRoundKey）4个步骤组成[14]。Cache计时攻击的目标是算法实现过程中的字节替换，计时攻击能够获取算法运行时使用S盒的轨迹，通过分析密文生成过程和输入已知的明文，来获取AES算法的密钥[15]。

但是在AES算法软件实现过程中存在矩阵运算，导致效率较低，所以现代的计算机一般不采用这种实现方式，而采用AES算法快速实现来代替原有的实现方式。快速实现算法主要通过将AES算法每一轮的3个操作（字节代替、行移位、列混淆）合并成一个查询T-tables操作来提高运行效率，由于传统实现最后一轮加密操作中没有列混淆操作，最后一轮则单独生成一个单表，所以T-tables一般有5个表，分别为T0、T1、T2、T3、T4，并且T4表能够通过掩码的方式由T0、T1、T2、T3计算得到。在主流的开源密码库OpenSSL中，v.0.9.7-v.0.9.8b版本中的AES算法实现使用了5个查询表，在之后的实现中，T-tables由4个表组成，T4表直接从其他表中得到[16]。分析OpenSSL的T-tables实现，得到T0、T1、T2、T3中的每一个表共有256个元素，且每个元素占用4个字节，将T-tables加载到Cache中，将占用4 KB的Cache空间。一个Cache大小为64 B，则存储整个T-tables将消耗64个Cache行。

设一个16个字节的明文为p=(p0,p1,…,p15)和16个字节的密钥为k=(k0,k1,…,k15)，r为加密的轮数，Kr为第r轮加密的一个密钥单词（32位），且：

在算法加密的开始，先将明文与密钥进行异或，得到初始状态x=(x0,x1,…,x15)：

在128位密钥的AES算法中，前9轮加密过程中包括字节代替、行移位和列混淆，所以前9轮需要查询的T-tables有T0、T1、T2、T3，第r+1轮的状态值x与第r轮加密的状态值关系为：

在第10轮加密中，由于没有列混淆操作，所以要使用T4表，AES快速实现方法在整个加密过程中只需要160次T表查询操作和160次异或操作，相比原始AES算法的实现而言，效率非常高[15]。

综合分析AES快速实现的过程，查询表索引与原始密钥有着很强的联系，在算法加密开始，明文与密文异或后得到初始状态值x，然后进行第一轮加密，如果能够获取第一轮加密查询T表的索引值，加上又能够控制明文p，通过索引值与明文p异或将直接得到密钥。

1.3 欧式距离

欧式距离是两点之间的直线距离，设X(x1,x2,…,xn)，Y(x1,x2,…,xn)是N维空间中的两个点，用d表示两点之间的欧式距离，则有：

欧式距离能够用来计算不同样本之间的绝对距离来衡量样本之间的相似性。在Cache计时攻击过程中，样本为地址行的命中与失效序列，且只有命中和失效两种可能，将命中置为1，失效置为0，形成样本序列，通过计算采集的样本与密钥模板之间的欧式距离，得到样本与每一个密钥模板的相关性，利用相关性强弱来分析密钥。

2 攻击原理与实现

2.1 Flush+Flush攻击模型

Flush+Flush攻击模型是对Flush+Reload攻击模型的改进，Flush+Reload攻击模型攻击步骤有3步：

（1）利用clflush指令刷新攻击进程与密码进程共享的Cache行。

（2）然后触发运行密码进程。

（3）访问共享的Cache行并判断是否发生Cache失效。

这种攻击模型准确度很高，但面临的一个问题就是会触发大量的Cache失效，使得攻击容易被硬件计数器检测出来，从而阻断攻击。Flush+Flush攻击模型只需要通过测量clflush指令的执行时间来判断某个Cache行是否缓存S盒数据，不会触发大量的Cache失效。Flush+Reload攻击模型需要多次重载数据，这种操作可能会引发预处理，提前将数据加载到Cache中，从而使测量方法失效。而Flush+Flush攻击模型不需要多次触发运行密码进程，不会引发CPU预处理，攻击步骤如图2所示，首先间谍程序找到与密码进程的共享主存地址，如图2步骤1所示；然后触发运行密码进程，使用的相应S盒数据则会加载到相应的Cache中，间谍程序通过刷新每一个被监控的Cache行，利用Cache命中和失效来判断Cache行是否被加载数据，确认AES算法进程查询T-tables的情况，如图2步骤2所示，灰色代表被驱逐的Cache行，且该Cache行表示为密码进程从内存加载到Cache中的数据。

图2 Flush+Flush模型攻击步骤Fig.2 Step of Flush+Flush model attack

与Flush+Reload攻击模型相比较，Flush+Flush攻击模型能够在攻击的时候监视同一页中的多个地址，并且攻击过程中不会引发大量的Cache失效，从而难以被性能计数器检测出。通过多次实验证明，一次clflush指令消耗的时钟周期大概在100~200个，然而触发一次Cache失效则需要250个时钟周期，与Flush+Reload攻击模型相比，因为不会触发大量的Cache失效，攻击过程消耗的时钟周期会更少。

2.2 模板建立与攻击实现

攻击的对象为OpenSSL 1.02算法库，该版本中的AES算法实现的方式是基于T-tables表快速实现的，并且只有4个T表[17]。当AES算法查询S盒时，就需要将S盒加载到Cache中，通过Cache计时攻击，利用Cache命中与失效的关系，获取加密时查询S盒的值，即pi⊕ki，再利用S和工作原理xi=pi⊕ki，攻击的目标为加密的第一轮，故i=0，且p0为已知明文，故能够得到初始密钥k0。

首先获取OpenSSL地址活动情况，利用mmap函数映射OpenSSL地址到共享内存中，然后通过触发AES算法并检测OpenSSL地址数据是否被缓存到Cache中，如算法1所示。

算法1检测活动地址

输入：OpenSSL映射初始地址*addr，OpenSSL地址空间addr_space

输出：OpenSSL活动地址*addr_live

由于OpenSSL加密库包含多种算法，所以不能确定AES算法的地址，使用算法1确定AES算法的地址。为了简化实验获取准确的结果，算法运行在单核中，不使用并行运算来对算法进行加速，将OpenSSL加密库映射到内存中，在Cache行对齐的情况下，首先在不加密的情况下获取OpenSSL地址的Cache使用情况，然后使用16字节的随机明文和密钥进行100次加密操作，在Intel i7-4720HQ处理器、Kali Linux 2017.3的版本中平均一次加密所需要的时间约为340个CPU周期，如果发生Cache失效，则会对加密的时间影响很大，因为每一次失效至少需要消耗200个左右CPU周期，通过这个明显的时间差异就能够准确地获取查询T表的索引值信息。通过检测OpenSSL的地址，比较加密和无加密两次采集得到的Cache活动，得到82个Cache行的活动与加密有关，并且在这82个Cache行中，有18个Cache行在每次加密中的命中率都为100%，因此这18个Cache行与查询的T表没有直接关系。剩下的64个Cache行的命中率基本在92%左右，通过分析AES算法快速实现的方法，在加密的时候，不是T表每一个地址都需要被访问，并且访问的地址取决于明文。4个T表在内存中需要占用4 KB的存储空间，每一个Cache行为64 Byte，故4个T表在Cache中需要占用64个Cache行，所以剩下的64个Cache行一定是AES算法的4个T表。

确认AES算法的T表的位置后，使用Flush+Flush模型进行攻击，因为T表占用64个Cache行，一个Cache行能够容纳16个字节，分析查询T表的索引值，通过监视64个Cache行来获取每次加密时Cache访问的情况，通过固定密钥，使用随机明文进行加密，采集64个地址的Cache计时信息来建立密钥模板。建立模板如算法2所示。

算法2建立模板

输入：AES算法初始地址*addr，地址空间addr_space，随机明文p，循环攻击次数N

输出：检测地址命中与失效状况template[256][256]，初始值0

算法2中循环攻击次数N要满足8位大小明文的所有可能都出现一次，以消除未知明文带来的不确定性，在模板最后阶段需要设置一个阈值，将值大于1的视为Cache命中并置为1，否则为0。通过算法2监控指定的地址，并使用随机明文不断地触发AES算法加密操作，来获取在密钥不变的情况下的密钥模板。在现实攻击过程中，首先使用算法1检测AES算法初始地址，然后通过算法2获取目标运行时的计时信息，最后计算与已知的AES算法密钥的Cache模板的欧式距离，距离最小即为算法的密钥，如算法3所示。

算法3攻击实现

输入：AES算法初始地址*addr，地址空间addr_space，随机明文p，循环攻击次数N

输出：与每个密钥模板的距离Distance[256][256]，初始值0

3 实验与结果分析

实验环境为kali linux 2017.3版本操作系统，硬件平台CPU为4核8线程的Intel i7-4720HQ，内存为16 GB，攻击的目标为OpenSSL 1.02版本的AES算法，采用选择明文攻击方式。一个Cache行有16个查询表，首先攻击第一个Cache行，通过使用随机的明文和固定的密钥，采集有效的Cache计时信息来建立模板，一个明文字节有8位，确保每一个明文信息出现一次，即至少需要触发28=256次加密操作，并建立相应的密钥模板。通过改变密钥的值，建立256个密钥模板，在攻击AES算法时，监控64个Cache行，获取的Cache计时模板，通过与模板进行对比，从而获取AES算法的密钥。

为了建立一个准确的模板，实验通过触发10 000次加密操作，当密钥字节k0=0x00时获取的Cache计时模板如图3所示，纵坐标表示明文，横坐标表示监测地址，黑色表示在该监测的地址中发生Cache命中。当密钥字节k0=0xA5时获取的Cache计时模板如图4所示。

图3 k0=0x00的Cache计时模板Fig.3 Cache timing template of k0=0x00

图4 k0=0xA5的Cache计时模板Fig.4 Cache timing template of k0=0xA5

选择采集的任意一个Cache计时信息，计算与所有模板的欧式距离，如图5所示，与0x8A模板的距离最小，且远小于其他值，可断定该值为AES算法的密钥。

图5 Cache计时信息与模板之间的距离Fig.5 Distance between Cache timing information and template

攻击AES算法时，准确度取决于模板的准确性，当使用少量的加密操作来建立模板时，由于攻击过程中，容易受到其他进程的影响，并且存在系统和硬件的干扰，攻击的准确率较低，通过提高触发加密操作的次数，来建立更精准的模板。在上述实验中，获取每一个密钥模板需要10 000次加密操作，显然这种方式效率很低，为了找到最小加密次数，以256次加密次数为基数进行实验，实验结果如图6所示，模板攻击准确率达到100%需要6×28次加密操作。

图6 模板攻击准确率与采集样本数量关系Fig.6 Relationship between template attack accuracy rate and number of samples collected

Flush+Flush攻击模型不会触发大量的Cache失效，在Intel i7-4720HQ处理器中，在相同的时间内，运行攻击程序触发的Cache失效如表1所示。

表1 不同攻击模型触发Cache失效次数Table 1 Times of Cache miss in different attack models

无攻击情况下由于其他进程的影响，也会发生Cache失效，然而使用Flush+Flush攻击模型攻击时，发生Cache失效的次数不到无攻击时的4倍，然而在Flush+Reload攻击模型中，发生Cache失效次数为无攻击时的22倍，是Flush+Flush攻击模型的5.86倍，通过实验证明，Flush+Flush攻击模型不会触发大量的Cache失效。

4 结论与展望

研究以OpenSSL算法库中的AES算法快速实现为对象，利用Flush+Flush攻击模型采集Cache计时信息，建立AES算法每一个密钥的模板，基于欧式距离度量样本与密钥模板之间的相关性来获取算法的密钥。实验证明，在采集的模板足够准确时，攻击准确率能达到100%，且触发Cache失效次数仅为Flush+Reload攻击模型的17%，而且攻击更为隐蔽，不易被检测出。建立准确的模板时，需要大量地触发加密操作，如果在目标机建立模板很容易被检测出来，为了防止这种问题就需要在攻击前建立模板，如果攻击对象的系统或者OpenSSL的版本不一样，就容易造成模板失效，下一步研究重点应放在如何提高攻击的普适性，以适应不同的系统和OpenSSL版本，达到攻击的目的。