Scorpion

Aligot

Joan Calvet, José M. Fernandez, and Jean-Yves Marion. 2012. Aligot: cryptographic function identification in obfuscated binary programs. In Proceedings of the 2012 ACM conference on Computer and communications security (CCS '12). Association for Computing Machinery, New York, NY, USA, 169–182. DOI:https://doi.org/10.1145/2382196.2382217

研究的问题： 识别混淆后的二进制文件的密码函数

特色：

• 之前的静态分析检测常量或 machine language instructions，不适用于混淆后的
• 检测密码函数的 I/O 关系，抗混淆（即使混淆后，输入输出也是可知的）

解决方法：

I/O 关系对足够确定多数密码函数

1. 收集目标程序的执行路径 (程序在系统上运行期间所做的一系列操作)

   Windows x86 Pin

   收集 dynamic instruction D，用元组表示，包括以下部分：

   • 内存地址 A [D]
   • 在 A [D] 执行的机器指令 I [D]
   • I [D] 读写内存地址 Ra [D],Wa [D]
   • I [D] 读写寄存器 Rr [D],Wr [D]

   执行路径 T 便是一系列动态指令序列 D1……Dn

   T/ins 是机器指令序列，T/Ins = I1…… In 如果对任意 k 属于 [1，n]，使得 I [Dk] = Ik

2. 从执行路径中提取密码相关代码以及 I/O 参数：

   通常，可以将代码划分为函数，但是函数的概念也只是基于编译器特性（调用约定、prologue 和 epilogue code 等）的一种启发式定义，而这在混淆后的代码中是不可靠的。因此为混淆后的加密代码构建了特定的抽象。

   循环是加密函数经常用到的，但也不只加密函数会用到。所以需要准确定义加密代码中的循环

   simple loop 定义

   比如下图中 a 表示混淆工具 control-flow flattening, 每次循环可能执行不同逻辑。

   b 表示一种可以被用作混淆的编译器优化技术 unrolling，三条同样的指令执行了三次。

   采用 instruction-centric loops 定义循环：机器指令的重复。所以 a 不应被视为循环，b 应该被视为循环。

   nested loop 定义

   比如图 a 的情况，B 作为内嵌的循环可能不会与外层循环循环同样的次数，这样外层循环就不会被视为循环，但实际上外层循环应该被视为循环。因此检测到循环实例后就会用循环标记代替其代码，图 b 可以被替换为 AXCAXC

循环识别算法：

依次处理执行路径的机器指令，并将其存入链表 history 的尾部。

假设 history 中有指令 I1,I2,I1,I3，现在正要处理的指令为 I1，该指令在 history 中出现两次（都可能是 loop 的开始），因此创建两个 loop 实例 L1,L2，指针指向下一条待执行的指令。然后将 I1 加入 history 中。

再假设下一条指令是 I3. 此时 L1 就会被舍弃，因为其期望的指令不是 I3。而 L2 的指针继续移动，指向 I1。

此时可以确定 L2 已经循环了两次，因此将其替换为循环标记符 X 属于 Lid。假设下一条指令为 I4，而 L2 等待的指令为 I1，因此 L2 从 running loop instances 中移除并 register

参数：循环实例的参数是高级函数实现的参数对应的低级

• 属于 L 的相同参数的 bytes 要么在内存中相邻，要么同时在同一个寄存器中
• 属于 L 的相同参数的字节由 BODY [L] 中的相同指令以相同的方式 (读或写) 操作
• 属于 L 的输入参数的字节被 L 中的代码读取，而属于 L 的输出参数的字节被 L 中的代码写入

** 参数收集算法：** 先根据上述前两个条件收集参数，然后根据第三条将参数分为输入输出。然后确定参数的值：输入参数为第一次被读取的值，输出参数为最后一次被写入的值。最后，得到 INm (L) and INr (L)(分别为内存和寄存器中的值）,OUTm (L) and OUTm (L)

比如：一次一密 xor 的程序 P

首先，收集程序 P 的执行路径，然后识别循环体。检测到了一个 loop 实例。

收集循环的参数，同时还提取一些与这些实现有关的参数，将在最后进行对比时发挥作用。

• eax:4,ebx:4,esp:4：内存地址
• ecx:4：counter value
• 12FFC0（起始地址）:4（字节数）：与 sizetodecrypt 循环前的初始化本地向量有关
• edx:4：中间存储器

loop data flow：我们认为每个可能的加密实现都包含一个循环。然而，密码函数实际上可以由几个非嵌套循环组成，例如 RC4 [34]。因此，单靠上述的循环不足以完全捕获它们，所以使用 data flow 对参与相同加密实现的循环实例进行分组。

• 定义：和 def-use chains 差不多，如果 L1 的输出参数用作 L2 的输入参数，那么称循环实例 L1 和 L2 连通。为了简单起见，只考虑内存参数，因为寄存器参数需要在循环实例之间的顺序代码中进行精确的污染跟踪。实际上，我们的假设是，对内存中输入和输出的所有处理都是通过循环处理的。

  在不同的密码函数之间组合的情况下，即一个函数的输出用作另一个函数的输入，它们将被分到相同的 loop data flow 中，因此需要考虑所有子图。

1. 与已知密码函数（pycrypto）比较：如果 loop data flow 与密码函数有同样的输入输出，则认为实现了同样的密码函数。

   首先，生成所有可能的 I/O 值，比如上例有 5 个长度为 4，22 个长度为 8 的值。（实际应用中，逆向分析者可以去掉明显依赖于实现的参数，比如内存地址）

   然后，对每个加密参考实现程序 Pf，从生成的可能的输入值中选择合适的值输入。Pf 如果只需要定长的参数，便只选择正确长度的参数

   最后，运行 Pf，如果其输出的值在之前生成的可能的输出值中，便成功找到。

TEA 特征：常量 delta，标准实现为 0x9E3779B9

MD5：输入被分为 512bit 的块

RSA: 模乘运算，用到 loop，Montgomery 算法优化模乘运算、deconding routine (PolarSSL)

样本：

B1：TEA 用 MSVC 编译，没有优化

B2：和 B1 类似，但 delta 用以下两条指令混淆，因此算法语义一样但是 delta 不再是静态可见常量

mov reg,delta;
add reg,delta/2;

B3:RC4 用 MSVC 编译，没有优化

B4:AES(OpenSSL)

B5:B4 用 AsProtect 打包

B6：md5（OpenSSL)

B8:RSA(PolarSSL),AsProtect

B1 有的工具没有识别出 TEA，可能是其本身没有实现该算法的功能。但是 B2 只有 Aligot 能识别，其余工具可能只是基于静态 delta 的值

恶意软件对 TEA 作了些修改，再实现之后命名为 Russian-TEA，也可以成功识别。

SBank 也是类似，但是因为有静态 delta，所以其余工具可以识别

性能：

• 自己的样本都基本在 20min 以内

• trance size 并不总是意味着更长处理时间。

• 如果 loop 很少，那么 history 更大，性能会更差

• 比较环节，性能主要取决于 LDP 的数量以及参数数量

不足：

• 局限于特定的执行路径（一个程序 P，输入为 K，C（密文），输出 C’(明文)，但不是 P 的所有执行路径都实现了密码函数，但确定具体的执行路径由逆向人员完成）
• 需要密码函数的参考实现
• 参数编码后便难以识别