sky's blog

Paper Summary & ABSynthe & Automatic Blackbox Side-channel Synthesis onCommo...

字数统计: 5,587阅读时长: 19 min
2020/08/11 Share

前言

这篇文章是发表在NDSS2020上,有关于微架构侧信道攻击的一篇文章。一作来自于英特尔公司,先前在硬件和底层上有比较多的研究。文章标题中的几个关键词,也在文章中有一定的体现,比如自动化、黑盒,合成等,这些都与一些现有的工作有比较大的差异。

背景知识

CPU组件存在大量的侧信道攻击,但现有的每一种侧信道攻击方式,几乎都基于白盒分析的方法。通常情况下,需要3步来完成:

  1. 首先需要能够识别出这一特定的CPU组件。
  2. 然后需要在特定的微架构上对其做逆向分析。
  3. 最后通过逆向分析得到的内容,人工构造指令序列,用以侧信道泄露信息。
    但这些方法通常都存在一些弊端,由于现有的侧信道攻击需要人工构造指令序列,而CPU会使用微架构组件来实现其指令集,并且这些微架构组件的底层细节不可见,因此需要逆向工程进行分析。随着CPU的更新换代,这些组件的数量,大小,复杂性都在增加,同时这些组件的属性可以在CPU版本之间发生变化,因此会对侧信道研究人员带来新的且冗长的逆向工作。
    同时,除去对于逆向工程的复杂性,当想要对目标程序进行侧信道攻击时,还需要对该软件有比较好的了解,清楚感兴趣的内容,其代码执行路径在何处。这一切都对攻击者有比较高的要求。除此之外,由于这些方法基于已有信息,那么对于那些未知的共享资源或者信息,则无法进行攻击。
    在此基础上,作者提出了黑盒分析的思路,他们将CPU组件当做黑盒,无需进行逆向分析。并且可以自动的找到目标软件可能感兴趣的内容的代码执行路径。文章的核心思路利用了共享资源被争用和不被争用时,会存在可测量的性能差异这一现象进行侧信道分析。
    同时本篇文章的工作可以自动的优化出在侧信道获取信息时,性能表现最好的指令序列,无需人工参与构造指令序列,并可以利用神经网络从侧信道攻击的结果中恢复密钥。

工具设计

作者以从受害者进程或者虚拟机中泄露诸如密钥等敏感数据为目的,提出了这样一种威胁模型:

  1. 攻击者可以在受害者的机器上执行代码
  2. 攻击者和受害者位于同一CPU核心上执行代码
  3. 所有最先进的侧信道保护都已启用
  4. 目标软件存在侧信道攻击的威胁
    由于作者提出的侧信道攻击的核心思路是利用共享资源在被争用和不被争用时,会存在可测量的性能差异。
    对于2条可能存在资源争用的指令,作者将写指令称为A指令,读指令称为B指令,通过使用A指令来尝试引起B指令的延迟变化,用以判断是否存在资源争用的情况。
    如下图,在writer指令执行时和不执行时,reader指令信号会存在明显的差异性。

    这里作者尝试找出2条存在可观察的资源争用信号的指令,与以往工作中人工精心挑选指令不同,这里作者通过遍历X86_64指令集来寻找最合适用于侧信道攻击的指令。这里的指令集来自于uops.info的项目。
    为了评估结果,作者建立了一个矩阵,用来反应指令B在指令A的影响下所出现的延迟相较于指令B在空指令下的延迟比例。如果延迟比大于1,那么说明指令A和B会存在资源争用的情况。
    作者对指令列表中的指令进行了一次二层嵌套for循环,用以寻找所有指令两两之间延迟比大于1的情况,从而找到所有存在资源竞争的指令对。
    为了将结果可视化的展现,作者将指令按照其使用的执行端口进行分组。按照执行端口分组的原因有2点:
  5. 执行端口本身就是一种被争用的资源
  6. 可以将相似功能的指令组合在一起
    从实验结果我们可以发现:
  7. 共享执行端口的指令不一定都是高争用,也可能是无争用的。例如skylake中P1端口。
  8. 不共享执行端口的指令一般显示低争用,但也有存在高争用的,这意味着共享资源不仅只有执行端口,可能还有其他资源。例如Xeon的P1和P5,P0和P5。
    通过比对在3种不同微架构上指令对在执行端口争用上的表现,作者总结出3个结论:
  9. 可能存在多个资源有争用问题,并非只有执行端口
  10. 在某个微架构上表现较好的基于资源争用的侧信道攻击,可能在其他微架构上不一定有效
  11. 性能表现最好的基于资源争用的侧信道攻击可能需要多个指令来引起资源争用
    在可以找到引起资源争用的指令对后,下面来介绍一下工具设计的架构。
    工具可以分为2个部分,一个是分析阶段,一个是攻击阶段。

    在分析阶段,将微架构和目标软件作为输入,通过Ground Truth引擎自动对其插入指令,每当其进行密钥操作时,就会与侧信道监听程序同步,发送与密钥相关的信号数据。
    侧信道攻击的代码Spy code最初来自于微架构的leakage map,对于leakage map每一个性能表现比较好的指令,侧信道监听程序会将它们资源争用的度量发送给合成引擎。而合成引擎则通过评估指令产生的资源争用信号,来生成可以触发更高信号质量的指令序列,循环往复,直到合成引擎生成的指令序列可以以足够高的可信度探测到密钥信息。
    在攻击阶段,利用分析阶段得到的优化后的指令序列进行侧信道攻击,并将获取的信息传递给密钥恢复引擎,用以恢复目标程序密钥。
    在进行上述方法实现时,会遇到3个挑战:
  12. 在分析阶段时,工具需要自动对目标软件进行指令插入,用以和侧信道攻击代码同步测量,收集密钥相关的真实数据,那么如何自动化的找到密钥相关的控制流分支是一个难点。
  13. 在分析阶段时,如何自动的优化侧信道攻击代码
  14. 在攻击阶段时,如何通过侧信道攻击的结果去恢复密钥信息
    那么对于第一点如何自动化插入指令的难题,作者使用了污点分析与火焰图的技术。对于第二点如何自动化优化攻击代码的难题,作者采用基于高斯朴素贝叶斯分类器的差分进化遗传算法来作为评估方法用以自动化优化指令序列。对于第三点如何恢复密钥,作者使用了RNN分类器。具体内容我们将在下一节展开。

工具实现

前面有提到,第一个难题就是如何自动化的进行指令插入,那么指令插入肯定不能随意乱做,我们需要找到感兴趣的代码路径,在其前后插入相应指令。而本文的针对攻击目标是加密函数,因此如何自动化的找到密钥相关的代码分支,就是一个难题。
这里作者选择使用污点分析来找到这些指令的插入位置,而后结合火焰图来自动的找出密钥相关的分支。
首先简单介绍一下火焰图的概念:

假设我们程序中需要执行main函数,main函数自身的CPU执行时间为2秒,而main函数中又调用了foo1和foo2函数,因此我们需要去计算foo1和foo2的执行时间,才能得到main的完整执行时间。
此时我们会去看foo1和foo2函数的调用时间,首先foo1函数自身的cpu执行时间为1.5秒,但由于其调用了bar函数,我们又需要再去看bar函数,才能计算出foo1的完整cpu执行时间。
此时看到bar函数,发现bar函数不再调用其他函数,其自身的cpu执行时间为2.5秒,因此我们可以算出foo1的完整cpu执行时间为其本身的1.5和bar函数的2.5之和,就是4秒。
那么同理,我们也可以算出foo2函数的完整执行时间为3秒,因此main函数的完整执行时间为自身的执行时间,加上foo1的时间,再加上foo2的时间,即9秒。
这一函数调用过程我们将其画成火焰图,如下图所示。

回到工具中,这里工具ABSynthe首先会将密钥文件中的所有数据标注为污点,进行污点分析。然后使用perf record来获取目标程序所有函数的火焰图,找到其中具有显著执行时间的函数,看其是否被我们的污点标注过,如果标注过,则在这些函数位置插入指令。
如下图中:

其中scalar是被标注成污点的密钥变量,第4行为密钥相关分支。第2和5行为我们嵌入的指令。

每当该分支被执行时,CRYPTLOOP_VALUE会发出信号,往共享内存中写入一个值,然后侧信道程序除了搜集侧信号信号以外,还会读取该值,用于后续的训练。
在搜集信息时,同样会存在难点,由于同步传输数据,本身就会产生噪音,影响侧信道的测量。
这里为了避免这一问题,作者使用了软同步策略,利用一个内存共享页来实现共享内存通道。同时让spy code持续监视目标共享内存位置,并将每个延迟测量值标记为样本值。
那么对于第2个难题,如果想造成一次效果较好的侧信道攻击,那么执行的指令序列的构造非常重要,之前的工作这一构造通常由人工完成。而在本篇文章里,作者使用差分进化算法来自动化的优化构造指令序列,该算法的输入为可以在微架构组件上产生资源争用的指令,这里作者选择了性能表现最好的指令作为种子。
同时作者希望算法可以自由的选择最终的指令序列,但又希望其生成的指令序列是有效的,因此作者提前设计了一种配方,让算法在寻找性能最好的指令序列时,对这些配方进行mutate。

首先我们来看一下配方的构成,第一个参数是Repeat number,这一参数用来定义指令序列需要执行的次数,范围为1~20次。指令序列的执行时间可以作为探测目标程序密钥操作的一种信号,执行时间需要在可观测和高分辨率中做一个衡量,因此指令序列执行次数非常重要。

第2、3参数代表是否在执行指令序列前或执行指令序列后存在内存屏障。如果存在内存屏障,可以保证内存通信时,不会因为乱序执行而使测量时间的指令出现噪音。但相应的,也可能会降低指令序列执行时间的分辨率。因此需要将这一参数保留,让算法来选择是否要其存在。
第4、5、6、7参数是用于来创建资源争用的。每个参数定义了特定信道所需的指令数量。

最后位置的参数用来规定使用哪种方式将指令块合并到一起。这里作者提出了3种合并方式:

  1. 串联,即将简单的将配方中的指令块连接在一起。
  2. 交错,即将来自不同块的指令交错连接在一起。
  3. 串联后的随机洗牌,即将配方中的指令块简单连接在一起后,再进行随机洗牌

    同时差分进化遗传算法需要一个适应度函数来进行评估当前指令序列的质量,看该指令序列是否能够产生可区分目标程序执行到不同代码路径的度量信号。
    这里作者使用了高斯朴素贝叶斯分类器来进行评估。原因是该分类器在不需要调参的情况下表现良好,同时其在training和evaluation时具有线性的时间复杂度,可以保证差分进化遗传算法能够快速进行。
    然后作者使用信号值来训练该分类器,这些信号值来自于目标程序执行到某个代码路径时,我们的指令序列产生的信号,我们根据我们之前对目标程序插入的指令,来标记其对应是否执行的该代码路径,例如0和1。
    同时作者为了证明优化指令序列的重要性,在目标程序Broadwell-NIST-P256上进行了对比实验。
    优化前:

    优化后:

    我们可以看到,在仅使用性能最好的单一指令时,PCA图分界不够明显,特征不够明显。而在使用算法优化后的指令序列时,PCA图分界比较明显,因此说明这样的指令序列获取的信号度量更加具有特征性。
    第3个难题是在之前的训练中,由于数据的搜集一直是保持同步的,因此我们可以容易知道程序开始的起点位置和长度,因此分类器可以简单的得到相关的密钥值。但是在真实世界的攻击中,我们获取的信号很可能是多个从未知位置开始的连续信号,这就比较困难。同时在长时间捕获信号的过程中,很容易失去同步。因此之前标记对应代码执行路径和延迟时间的方式在这里不可行。
    为了解决这一问题,作者使用时间序列为向量,选择了一种专门针对时间序列数据的LSTM RNN算法,该算法在不完全同步的情况下具有鲁棒性,在信号发生微小时间偏移时,允许非同步的恢复密钥。
    作者同时提到,可以有方法验证恢复密钥的正确性,例如目标程序在签名操作时,会使用密钥。那么作者也将恢复的密钥用于一次签名操作,如果签名相同,则说明密钥正确,否则则说明密钥错误。然后作者发现,恢复的密钥往往都是不正确的。可能是密钥某bit位丢失,或者是恢复错误。
    但是每次密钥恢复错误时,可能都需要对上百个bit位进行爆破,以找到正确的密钥,但这样的操作显然不可取,例如一个384bit的密钥,如果有n个bit猜测错误或者丢失,那么需要进行384^n次爆破,这显然不可行。
    但这里作者提到,由于考虑了时间序列问题,现在的算法的返回值是(time, secret),因此可以容易知道哪一位可能存在丢失或错误。因为丢失的时候,2个bit位之间会形成较大的时间间隙,而错误的时候,2个bit位之间会出现很窄的时间间隙。对于每一个可能出问题的bit位,一共只有3种情况,第一种是该位正常,忽略,第二种是该位丢失或错误应该改为0,第3种是该位丢失或错误,应该改为1。因此在密钥恢复错误的情况下,如果有n个位置错误,那么只需要进行3^n次爆破来恢复密钥。
    考虑到上述原因,作者为了解决这一问题,使用了2个LSTM模型,在恢复密钥时,如果2个模型预测值相同,那么才会接受。
    这两个模型,第一个是三层LSTM嵌套的模型,第二个模型是LSTM接一个激活函数RELU的全连接层*3的模型。这两个模型都用0.2的 dropout 来缓解过拟合问题 并且由于是个多分类任务,输出都用的softmax layer。然后它使用集成学习(Ensemble)的方式把两个模型组合在一起,以获得更好的效果。
    这里的训练数据特征是延迟值,训练集的样本分为两类,一类是从程序已知的开始位置开始,另一类是从程序未知的开始位置开始。

实验评估

作者使用了libgcrypt 1.6.3和libgcrypt 1.8.5中的加密函数EdDSA 25519、EdDSA 25519-hardened、EdDSA 25519-secure (1.8.5 only)、RSA、ECDSA P-256作为攻击目标进行实现评估。值得注意的是,EdDSA 25519-hardened中已经对侧信道攻击有了基本的防御机制,而EdDSA 25519-secure对于侧信道的防御机制被认为是最先进的。
作者在4个不同的微架构上进行了测试,使用F1分数来评估工具的性能。

这里值得注意的是,在ARM上,作者是人工编写的指令序列。这里原因是,对于ARM没有完整的leakage map,无法遍历测试。而另外3个x86微架构,作者测试了所有可能的指令,并使用了4条最好的指令序列。这也体现出,作者的工具要比人工编写指令序列性能高的多。
同时注意到红框部分,由于这一条表现的性能非常好,作者选用其进行测试,看其在信息不同步的情况下,对密钥的恢复能力如何。

作者对这些目标在信息不同步的情况下,进行了7次测试。可以发现再非GPG的情况下,正确恢复密钥的准确率在100%,而在GPG情况下有一定错误。即在无外部提示或者分析人员设置的情况下,密钥相关分支完全由工具自动的进行识别。
同时作者将自己工具优化生成的指令序列与其他工作人工构造的指令序列进行了性能比对。

可以发现工具自动优化得到的指令序列,性能高于其他人工构造的指令序列。
同时从两个维度来验证工具的鲁棒性。首先是能否自动的找到我们感兴趣的分支,即密钥相关的内容。
这里作者选择在完全无侧信道防御的EdDSA 25519算法上进行了7次测试,可以发现在密钥相关程序开始时和其他时候有显著的差异。说明工具在我们感兴趣的区域预测密度显著较高,证明了工具的可靠性。

第二个维度,作者从被干扰的情况下,测试工具的鲁棒性。这里作者使用usleep函数,来干扰cpu的执行时间,干扰量为0.1%~30.6%。

这里我们可以发现2个点,第一点是即使目标程序存在噪音,密钥恢复的准确度都不会有太多变化,这是因为我们前面介绍过,密钥的恢复算法具有鲁棒性,可以抵御干扰。第二点是,我们的侧信道程序上如果出现噪音,则会受到影响,因为这涉及到了信号采集问题,如果信号不能准确采集,那么则无法进行密钥的恢复。
当然工具也有一些局限性。
首先工具要求目标软件会在加密运行时花费较长时间。同时密钥需要从文件系统中进行加载,否则无法进行自动污点分析。
第二点是工具需要目标微架构的指令集定义格式易于创建leakage map,才能使用工具的方法自动生成并优化指令序列。这一点在x86上比较容易获得,但是对于ARM还不行。
第三点是工具在后续的处理阶段,可以有更为自动化的方式,通过暴力破解启发式的方法来应用于各种程序。

后记

本篇文章第一个创建了在x86微架构上完整的leakage maps,并实现了一个全自动的侧信道攻击,其可以利用资源竞争的方式,对各种平台,各种环境上的加密程序来进行侧信道攻击。对于前人工作具有比较高的创新性,同时为后续侧信道攻击测试提供了便捷性。

点击赞赏二维码,您的支持将鼓励我继续创作!
CATALOG
  1. 1. 前言
  2. 2. 背景知识
  3. 3. 工具设计
  4. 4. 工具实现
  5. 5. 实验评估
  6. 6. 后记