Differential Computation Analysis

cryptoxcryptox
2 min read

DCA attack on white-box cryptography is a type of side-channel attack that exploits the statistical correlation between intermediate values and key bits. It can be seen as a software version of differential power analysis (DPA) that does not require physical access to the device. It can implement without detailed knowledge about white box design. In the white-box model, the DCA attack can observe everything without any measurement noise.

DCA Attack Technology

Dynamic binary analysis (DBA),a technique often used to improve and inspect the quality of software implementations, to access and control the intermediate state of the white-box implementation.One approach to implement DBA is called dynamic binary instrumentation (DBI).

The idea is that additional analysis code is added to the original code of the client program at run-time in order to aid memory debugging, memory leak detection, and profiling.

The most advanced DBI tools, such as Valgrind and Pin, allow one to monitor, modify and insert instructions in a binary executable. analysis of obfuscated code.

Flow

  1. Collect software execution traces of the white-box implementation using binary instrumentation tools

  2. Apply a selection function to each trace to obtain intermediate values

  3. Compute the correlation between intermediate values and key hypotheses

  4. Recover the key by finding the highest correlation

Software Execution Traces

观察可以通过检测二进制文件或检测负责二进制文件执行的仿真器来实现。

我们通过使用一些可用的动态二进制检测(DBI)框架选择了第一种方法。 简而言之,DBI通常使用称为即时编译的技术将要分析的二进制可执行文件视为虚拟机的字节码。 机器代码的这种重新编译允许在保留原始计算效果的同时对代码执行转换。

DBI框架,如PIN和ValGrind,执行另一种转换:它们允许通过编写插件或挂钩到重新编译过程的工具,在机器代码指令之间添加自定义回调。 这些回调可用于监视程序的执行和跟踪特定事件。 PIN和Valgrind的主要区别在于,Valgrind使用了一个名为VEX的独立于体系结构的中间表示(IR),它允许编写与IR支持的任何体系结构兼容的工具。 我们为两个框架开发(并发布)了这样的插件

First Step

用任意明文跟踪白盒二进制文件的一次执行,并随时间记录所有访问的地址和数据。 尽管跟踪器能够跟踪任何地方的执行,包括外部库和系统库,但如果加密操作碰巧在那里处理,我们将范围缩小到主可执行文件或伴生库。存在ASLR地址随机化,随机安排可执行文件、其数据、堆、堆栈和其他元素(如库)的地址空间位置。 为了使获取完全可复制,我们只需禁用ASLR,因为白盒模型使我们能够控制执行环境。 如果ASLR不能被禁用,那么重新排列所获得的跟踪将只是一个麻烦。

Second Step

可视化跟踪以理解分组密码在哪里被使用,并通过计数重复模式的数量来确定实现了哪个(标准化的)密码原语:例如,10轮AES-128,14轮AES-256或16轮DES。

为了可视化跟踪,我们决定用类似于[50]中提出的方法的图形来表示它。在许多现代平台上,通常会分别遇到文本段(包含指令)、数据段、未初始化数据(BSS)段、堆,最后是堆栈。 虚拟地址空间非常稀疏,所以我们只在有东西要显示的地方显示内存带。 Y轴是从上到下的时间轴。 黑色代表正在执行的指令的地址,绿色代表正在读取的内存位置的地址,红色代表正在写入的地址。

Third Step

一旦我们确定了我们的目标算法,我们就保持ASLR禁用,并用随机的plaintexts记录多个跟踪,可选地使用一些标准,例如,在哪些指令地址范围内记录活动。 这对于执行我们不感兴趣的其他类型操作的大型二进制文件特别有用(例如,当白盒实现嵌入到更大的框架中时)。 如果白盒操作本身需要很多时间,那么我们可以将捕获的范围限制在记录第一轮或最后一轮的活动,这取决于我们是从密码的输入还是输出发起攻击。 集中在第一轮或最后一轮是类DPA攻击中的典型情况,因为它将被攻击的密钥部分限制在一次单个字节内,如第3节所述。 在图给出的例子中 读取访问模式使得识别DES轮变得很简单,查看相应的指令(黑色)有助于定义合适的指令地址范围。 当在初始跟踪(第一步)中记录所有内存相关信息时,我们在这一步中只记录单一类型的信息(可选地用于有限的地址范围)。 典型的示例包括从内存中读取字节的记录,或写入堆栈的字节的记录,或访问内存地址的最低有效字节的记录

这种通用方法为我们提供了最好的折衷办法,即尽可能快地安装攻击,并最大限度地减少软件跟踪的存储。 如果存储不是一个问题,可以直接跳到第三步并记录完整执行的跟踪,这对于没有太多开销的可执行文件来说是完全可以接受的,正如在第5节的几个示例中可以看到的那样。 这种幼稚的方法甚至可能导致创建一个完全自动化的获取和密钥恢复设置。

Fourth Step

在步骤3中,我们获得了一组软件跟踪,这些跟踪由(部分)地址实际数据列表组成,每当指令访问它们时,这些地址或数据就会被记录下来。 为了转移到一个适用于通常的DPA工具的表示,我们将这些值(通常是字节)序列化为1和0的向量。 这一步对于利用我们记录的所有信息至关重要。 为了理解它,我们将其与针对相同类型信息的经典硬件DPA设置进行比较:内存传输。

当使用DPA时,一个典型的硬件目标是一个带有一个8位总线到存储器的CPU,该总线的所有八条线将在低电压和高电压之间切换以传输数据。 如果可以在功耗的变化中观察到泄漏,它将是一个模拟值,与在该存储器总线上传输的字节中等于1的比特的总和成正比。因此,在这种情况下,最基本的泄漏模型是CPU和内存之间传输字节的汉明权重。 然而,在我们的软件设置中,我们知道确切的8位值,为了利用它,我们希望单独攻击每一位,而不是它们的总和(如汉明权重模型中的那样)。 因此,我们执行的串行化步骤(将观测值转换为1和0的向量)就好像在硬件模型中,每条对应的总线都一个接一个地单独泄漏。

执行DPA攻击时,电源跟踪通常由采样的模拟量组成。 在我们的软件设置中,我们正在处理单个位的完美泄漏(即,没有测量噪声),这些位只能取两个可能的值:0或1。 因此,从硬件角度来看,我们的软件跟踪就像我们在用针探测每一条单独的线路一样,这需要大量的样品制备,如芯片贴片和聚焦离子束(FIB)铣削和修补操作,以挖穿金属层,从而在不影响芯片功能的情况下到达总线线路。 比外部侧通道获取更强大和更具侵入性的东西。

当使用软件跟踪时,在时间轴上与传统的功率跟踪有另一个重要的区别。 在物理侧通道跟踪中,模拟值以固定速率采样,通常与受攻击设备的内部时钟无关,时间轴线性表示时间。 在软件执行跟踪中,我们只在相关时记录信息,例如每次在堆栈上写入一个字节时,如果这是我们记录的属性,而且比特被序列化,就像它们是顺序写入的一样。 人们可能会观察到,给定这种序列化和按需采样,我们的时间轴并不代表实际的时间尺度。 但是,DPA攻击不需要适当的时间轴。 它只要求在比较两个跟踪时,在程序执行相互比较。 图2a和2b分别说明了用于DPA和DCA的跟踪之间的差异。

Fifth Step

一旦获得并形成了软件执行跟踪,我们就可以使用常规的DPA工具来提取密钥。 我们将在下一节中展示DPA工具的结果,以及密钥的恢复。

AES

SM4

Reference

[1] Bos, Joppe W., et al. "Differential computation analysis: Hiding your white-box designs is not enough." Cryptographic Hardware and Embedded Systems–CHES 2016: 18th International Conference, Santa Barbara, CA, USA, August 17-19, 2016, Proceedings 18. Springer Berlin Heidelberg, 2016. —Best paper award

0
Subscribe to my newsletter

Read articles from cryptox directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Written by

cryptox
cryptox