ABSynthe: Automatic Blackbox Side-channel Synthesis on Commodity Microarchitectures

Background

1. 微架构组件

CPU使用微架构组件实现其指令集体系结构（ISA）。随着每一代新CPU的出现，此类组件的数量、大小和复杂性都会增加。由于这些组件对于软件不可见，因此只有通过详细的逆向工程才能发现其底层详细信息。此外，每个组件的属性可以在不同的CPU版本之间进行更改，而不会引起软件的兼容性问题，但每次都会给实施侧信道攻击带来新的冗长的逆向工程工作。

2. 同步多线程(SMT)

SMT，也称为超线程（hyperthreading），其主要目的是实现核心资源之间的跨线程共享。在多线程核心设计时，内核资源是通过以下三种方式之一拥有的：

（1）复制：每个线程有一个实例供私有使用。 对于微体系结构状态（如体系结构寄存器文件和指令指针），会发生这种情况。

（2）分区：每个线程都有一半资源的静态所有权分配。 示例包括iTLB和物理寄存器文件（PRF）。

（3）竞争性：有一个完整的资源池可用于所有线程。示例包括预留站中的执行插槽，CPU caches，load/store 缓冲区，L1 dTLB，共享TLB（STLB）和执行单元。

3. Eviction- vs. contention-based attacks

（1）Eviction based attacks：使用驱逐将目标组件置于已知状态。在执行秘密操作之后，攻击者可以检查状态以推断出任何泄漏有关秘密操作信息的更改。如Prime+Probe攻击。

• 需要对目标微体系结构组件的了解

• 主动驱逐策略，会减少攻击的隐身性，以及已存在较多可缓解的方案

（2）Contention based attacks：攻击[10，11]依赖于执行端口的可用带宽来秘密地跨线程泄漏信息。攻击者只需测量随时间变化的带宽（即每秒的操作数），并观察其波动即可推断出受害者的操作信息。

• 依赖于被动监视而不是主动驱逐，从而提高了攻击的隐身性和可被缓解的能力。

• 但是，利用策略仍然针对特定的组件，并且需要对底层微体系结构及其与目标软件的交互进行假设。

4. contention-based attacks

（1）Fetch：每个逻辑核都有其自己的寄存器文件，并且管道根据每个逻辑核上的程序计数器从内存中获取指令。为了处理性能公平，此提取在逻辑核之间进行交错。 （2）Decode：在Fetch阶段之后，解码阶段将每个指令分解为更简单的微操作（微指令）。每个微操作都执行单个任务，这种拆分是为了性能而交错它们的执行，有助于乱序执行。此后， 所有处理均在uops上完成，而不是在指令上完成。 然后，解码阶段将这些指令发送给执行调度程序。 （3）Schedule：在调度程序中，有一个同时属于两个逻辑核的微指令队列。调度程序的一项任务是将这些指令发布到执行端口，同时使性能最大化。

（4）执行端口：执行端口是执行单元的通道，执行单元是实际执行uops的地方。图2将执行单元显示为带有标记指示其功能的灰色框。例如，端口0、1、5和6可用于执行简单的算术指令，因为它们中的每一个都是ALU执行单元的通道。而端口2、3、4和7专用于基于内存的微指令（例如， load和store）。

（5）执行端口的共享（或竞争）： 在存在超线程的情况下，在调度程序中，有微指令等待分派到某个端口以执行。这些微指令实际上可能属于从任何逻辑核获取的指令，因此，这些核以非常精细的方式（在微指令级别）共享执行引擎（EE）。

Overview

主要内容

• 展示了x86_64 ISA的不同微体系结构的第一个完整的同步多线程（SMT）泄漏图。泄漏图显示了不同的x86_64指令之间的复杂相互作用，并允许进行大量观察。
  • 首先，有许多不同的微体系结构组件会泄露秘密信息并允许进行基于竞争的实际攻击。
  • 其次，通过测试不同的指令，可以对任意不同的微体系结构组件进行争用，而无需了解竞争组件或微体系结构，从而为攻击自动化提供了便利。
  • 第三，在一个微体系结构上产生可观察到的竞争的指令在其他微体系结构上不一定可以这样做。这意味着基于竞争的攻击并不总是可以在具有不同微体系结构的不同处理器之间移植。
• 提出了ABSynthe，一个在给定的微体系结构和给定的软件目标上自动合成新的侧信道攻击的系统。
  • 首先，为了自动检测给定软件目标中与秘密有关的控制流，采用类似于DATA的污点分析[12]。依靠性能监视计数器来确定目标分支，从而进一步优化分析。 一旦ABSynthe识别了目标分支，它就会尝试从泄漏映射中找到一系列指令，以最大程度地从目标分支泄漏信息。（找到导致信息泄露的目标分支）
  • 其次，ABSynthe依靠一种遗传算法来找到指令的组合，这些指令可产生最佳竞争以从目标软件中泄漏出最大量的信息。结果是高度优化的特定于目标的指令序列，其性能要优于最近工作中使 用的任何单个指令[10，11]。通过使用许多不同的加密函数和商用CPU体系结构（英特尔， AMD，ARM），证明了ABSynthe在合成本地和虚拟环境中的实际跨线程攻击方面很有效。（产生最大程度地导致信息泄漏的最佳指令序列）
  • 最后，ABSynthe使用循环神经网络（RNN）使用合成攻击来完成密码密钥位流的完全恢复。拥有ABSynthe结果后可以使用基本的后处理技术来恢复最终的密钥。（设计实现攻击）

Contention based side channel

1. 生成leakage map的方法

• 定义： 表示指令B在指令A的影响下经历的干扰因子；指令B称为reader指令（观察其延迟），指令A称为writer指令（如果有的话，这会引起延迟差异），以及 将特定微体系结构的泄漏图矩阵化。任何大于1.0表示A产生了竞争且B经历过竞争。
• 的计算方法：测量在同级线程上同时执行指令A时指令B的等待时间，并将此等待时间表示为指令B同时执行NOP的一个因数，即
• 方法：为了使结果可视化，根据相应指令的执行端口使用率对 的行和列进行分组。

2. 生成leakage map的具体算法

3. 生成的leakage map和结论

• 有多个独立的竞争来源
• 在一个微体系结构上基于竞争的侧信道在另一个微体系结构上可能无法正常工作
• 基于最佳竞争的侧信道可能需要来自多个指令的竞争

Design

1. ABSynthe Overview

• 在分析阶段，ABSynthe将给定的微体系结构和目标软件作为输入。 然后，它会自动生成一个插桩后的二进制文件，该二进制文件在执行秘密操作时便会与间谍程序同步。
• Synthesis Engine（合成引擎）旨在通过基于基于竞争的测量值生成新的指令序列来提高信号质 量。这些新的指令序列反复完善Spy code（间谍代码），直到合成的侧信道可以有足够的置信度 检测到秘密信息。
• 在分析阶段之后，ABSynthe使用同步步骤对秘密比特进行分类，攻击阶段使用间谍代码和 ABSynthe的Secret Recovery Engine（秘密恢复引擎）来泄漏秘密信息，而不用与受害者软件同步（使其适合实际攻击）。

2. 三个挑战

C1：在分析阶段，ABSynthe需要自动对目标软件插桩，以使测量值与间谍代码同步，以收集ground truth。 C2：在分析阶段，ABSynthe需要针对给定的微体系结构自动优化侧信道。 C3：在攻击阶段，ABSynthe需要使用优化的侧信道使用不同步运行的受害者二进制文件恢复秘密信息。

3. C1：自动化查找依赖秘密的分支

• 插桩的依据：（对于加密软件而言）

  • 假设该操作会在与密钥大小相关的多次迭代中，在相当大部分的执行时间内执行与秘密相关的分支。

  • 其次，分支指令应取决于秘密。

• 步骤：
  • 首先使用启用了DFSan（动态污点分析技术）的LLVM构建代码，然后让ABSynthe污染密钥文件中的所有数据。
  • ABSynthe使用perf record对目标程序进行profiling（概要分析），以查找具有明显累积执行时间的所有函数，并向它们插桩，该插桩代码会测试分支条件是否受到污染。
  • 对于最后的ground-truth插桩，ABSynthe会选择所有被污染且根据密钥大小执行大量操作的分支（每次都没有相同的分支结果）。
  • 最后，ABSynthe还会对已插桩分支的父循环的顶部进行插桩，以使间谍区分出数量不等的未执行的秘密分支。
• 插桩标记的作用：
• 循环顶部的检测CRYPTLOOP_START（）通过将标记写入共享内存来指示开始处理密钥位。
• 每当采用依赖于秘密的分支时，只需将相应的值写入共享内存即可通过CRYPTLOOP_VALUE（1）发出信号。
• 间谍代码将读取这些值，并将它们与侧信道信号一起收集以进行训练和评估。

4. 优化侧信道

• 目标：尝试在潜在的多个资源上同时创建竞争，在参数内合成性能最好的侧信道攻击。因此，需要为上一步中插桩的软件目标找到正确的指令序列。

• 方法：进化搜索算法，算法输入为可在各种微体系结构组件上引起竞争的指令，将效果最好的指令作为种子集。进化搜索算法改变合成指令序列的配方来找到最佳性能的指令序列。

  

• 进化搜索算法
  • 使用高斯朴素贝叶斯（Gaussian Naive Bayes，GNB）分类器来确定给定的指令序列是否给出能够区分目标正在执行的各种代码路径的信号测量。
  • 在信号值上训练分类器，信号值是一个包含220个时延测量的向量（特征）。用从插桩获得的真实数据来标记它们，真实数据是在测量信号时目标正在执行的代码路径。作为示例，将这些代码路径标记为0和1（标签）。
  • 为了提高准确性，首先对给定指令序列的原始测量结果进行了归一化步骤。从所有测量 值中减去平均时延，然后将每个测量值除以得出信号单位方差。
  • 最后，使用75个目标执行来训练GNB（提供经验准确的结果）。通常，每次执行都会提 供数百个代码路径示例，从而提供了一组训练集，例如19200个’0’值和9600个’1’值。然后，观察训练后的GNB分类器在25个目标执行的单独训练集上的表现如何。根据该测试，计算出f1 score。将此f1 score用作遗传算法的适应度函数。

• 优化侧信道（多个指令组合）的步骤带来的效果：图（a）单个指令和图（b）多个指令组合，进行比较，图（b）中-1,0,1三者信号分得很清楚，效果很明显

  

5. C3：秘密值恢复

• 问题： 现实的攻击需要使用从未知位置开始的许多连续的子信号来处理捕获的信号。为了在实际设置中获得秘密恢复，需要识别与特定秘密值相对应的许多样本的子信号，并仅提取单个值。主要原因是因为之前将样本的时间序列表示为向量，分类器在每个位置为其赋予了相同的含义。但是，当分析长捕获时，样本可能随着时间的推移失步。

• 解决方法： 为了在不存在同步的情况下检测与秘密值相对应的信号，使用LSTM RNN。该网络不仅可以显着改善同步分类，而且在信号的时间变化较小时也很健壮，从而可以实现非同步的秘密恢复。

• 具体方法： （1）设计两个LSTM模型（用Tensorflow的Keras接口实现） （2）训练模型权重的方法：

  • 组装带标签的训练集。训练样本的特征是时延值，已对其进行了归一化处理，其处理方式与上述高斯Naive-Bayes分类器相同。
  • 在训练集中包括2种样本。 第一种是时延信号，其中开始时间与目标根据真实数据正在处理代码路径的时刻一致。第二种类型是从一条路径的起点与另一条路径的起点之间的某个地方开始的信号。我们用插桩未使用的特殊额外标签对此进行标记。
  • 与高斯分类器一样，我们在目标的75次执行上训练模型，通常对第一个同步类型的每次执行给出384个代码路径。另外，还添加了相等数量的不同步的特殊训练样本。

  （3）结果的处理： 训练2个不同的LSTM模型并且仅当它们都预测相同秘密值时才接受秘密值预测，如果预测失败则通过暴力破解的方法对损失值进行补偿（ignore, insert 0, insert 1）

Evaluation

1. 评估内容

• ABSynthe的间谍程序能否将与单个秘密位对应的对齐的执行轨迹代码可靠地分类为正确的秘密位？
• 是否可以完全无误地在没有任何对齐的情况下完整捕获秘密密钥操作，并将其可靠地映射回原始秘密比特？
• 如何将ABSynthe中的指令序列黑匣子生成与基于竞争的最新攻击（如PortSmash [10]和 SMoTherSpectre [11]）进行比较？
• ABSynthe是否具有强大的信号捕获能力，而不是感兴趣的执行区域？ 我们是否可以检测到感兴趣的区域在哪里，即正在处理秘密密钥位（我们训练了分类器以检测这些秘密位）？
• 合成的攻击对抗噪声的鲁棒性如何？
• 是否可以将该系统推广到不仅检测与秘密有关的代码访问，而且还检测与秘密有关的数据访问？

2. 评估结果

• 分类可靠性

  结果表明，ABSynthe成功地合成了不同平台和软件目标上的侧信道。 此外，在某些情况下， ABSynthe的DE算法可以通过同时在多个资源上创建竞争来合成更好的侧信道。EdDSA 25519-secure在考虑侧信道的情况下进行了显着设计，没有太大的收获，但是对于其他算法，DE甚至在整个VM上都显着改善了信号。 这些结果表明，使用ABSynthe的自动化可用来测试密码函数对基于竞争的侧信道攻击的敏感性。

• 未对齐的秘密位序列恢复

  在许多情况下，LSTM分类器获得了很好的F1分数，这意味着对于秘密密钥位的信号很强。ABSynthe的合成端到端侧信道仅使用一次跟踪捕获和适度的暴力破解就可以100％成功地帮助恢复密钥，即使加密函数已嵌入整个应用程序中也是如此。另外，使用ABSynthe的未对齐秘密恢复分析，一种针对特定案例的简单启发式方法可有效恢复任意秘密密钥。

• 与手动发现的序列比较

  

  与PortSmash [10]和SMoTherSpectre [11]建议使用手动发现的指令序列来利用基于竞争的侧信道相比，根据本文的分类器，ABSynthe的自动DE算法在分类可靠性方面要比其他所有序列大得多，其方法是找到为给定目标创造最大竞争的指令。

• 依赖秘密的数据访问

  结果表明，仅通过观察缓存访问并具有基本的真实数据，ABSynthe就能区分秘密。ABSynthe的性能取决于目标及其cache set号。

• 鲁棒性

  • 如果我们在执行目标程序的过程中捕获了侧信道信号，我们是否可以自动识别感兴趣的区域，即在其中处理秘密密钥位的区域？

    评估结果：检测算法将处理未经训练的数据，并且可能会发生伪造的比特预测。结果表明尽管存在许多伪造的加密比特预测，但感兴趣区域中的预测密度却明显更高。

  • 如果间谍进程，目标进程或两者同时被并行计算周期性地中断，我们是否仍可以对结果信号进行密钥恢复？

    评估结果：仅干扰间谍程序有影响，因为这会干扰信号采集，但干扰目标进程却没有任何显著影响， 因为密钥恢复过程对于信号中的噪声插入具有鲁棒性。另外，即使对间谍程序的最小干扰也会产生影响，并且随着添加更多干扰，成功率会逐渐降低。总而言之，假设攻击者完全控制了其间谍进程，即使受害者的执行噪音很大，ABSynthe仍可以成功恢复秘密密钥。

Discussion

局限性

• 目标软件：本文假定了目标软件花费大量时间进行秘密计算，这是加密软件的情况，但不一定是其他软件的特征，在其他情况下，需要手动对目标软件进行标记（即找到秘密分支，插桩的方法）。
• 架构：ABSynthe要求以一种方便的格式定义ISA，以便为不同的微体系结构构建泄漏图。 尽管对于x86_64来说这已经很容易获得，但是在ABSynthe中支持新架构将需要方便的ISA 定义。未来的工作可以使用ARM机器可读体系结构（MRA）将本文的x86_64泄漏映射扩展到ARM（即合成最佳竞争的指令的方法）。
• 密钥恢复：本文中拥有ABSynthe结果的分析通过执行特定的处理，即使一次捕获，也可以从ABSynthe恢复的密钥位流中实现完全密钥恢复。 未来工作的一个有希望的方向是也将这个处理过程自动化，研究可能适用于各种（密码）程序的暴力启发式方法。

---

• Previous
  组会纪要
• Next
  组会纪要