OLLVM_RC4 算法的还原案例
背景：OLLVM 混淆下的 RC4 算法还原
在实际的 Android 逆向工程中，我们经常遇到被 OLLVM（Obfuscator-LLVM）混淆的 Native 函数。OLLVM 不会改变算法的语义，但会极大地扭曲代码的控制流，使得静态分析变得极其困难。本文以 RC4 算法为例，讲解如何在 OLLVM 混淆下还原算法逻辑。
RC4 是一种广泛使用的流加密算法，结构简洁（仅 KSA + PRGA 两个阶段），但在 OLLVM 混淆后，即使是如此简单的算法，代码也可能变得面目全非。
RC4 算法标准实现回顾
在开始分析之前，先回顾 RC4 的标准实现。理解标准的算法结构是还原的基础。
KSA（Key-Scheduling Algorithm）
KSA 负责使用密钥初始化 S-box（256 字节的置换表）：
void rc4_ksa(uint8_t *S, const uint8_t *key, int key_len) {
int i, j;
// 第一步：S-box 初始化为 0-255
for (i = 0; i < 256; i++) {
S[i] = i;
}
// 第二步：使用密钥打乱 S-box
j = 0;
for (i = 0; i < 256; i++) {
j = (j + S[i] + key[i % key_len]) % 256;
// 交换 S[i] 和 S[j]
uint8_t temp = S[i];
S[i] = S[j];
S[j] = temp;
}
}PRGA（Pseudo-Random Generation Algorithm）
PRGA 负责生成密钥流，并与明文进行 XOR 加密：
void rc4_prga(uint8_t *S, uint8_t *data, int len) {
int i = 0, j = 0;
int k;
for (k = 0; k < len; k++) {
i = (i + 1) % 256;
j = (j + S[i]) % 256;
// 交换 S[i] 和 S[j]
uint8_t temp = S[i];
S[i] = S[j];
S[j] = temp;
// 生成密钥流字节并加密
data[k] ^= S[(S[i] + S[j]) % 256];
}
}RC4 的代码特征
标准 RC4 实现有以下可识别的特征：
- 256 次循环：KSA 和 PRGA 中都有 256 次的循环
- S-box 数组：256 字节的
uint8_t数组 - 取模 256 操作：
(i + 1) % 256或等价的& 0xFF - 交换操作：频繁的
S[i]和S[j]交换 - XOR 加密：
data[k] ^= S[(S[i] + S[j]) % 256]
这些特征即使经过 OLLVM 混淆后，在底层指令层面仍然保留，是我们识别算法的关键。
OLLVM 混淆对 RC4 的影响
OLLVM 是基于 LLVM 编译器框架的代码混淆工具，它通过在编译阶段修改 IR（中间表示）来改变代码的控制流。OLLVM 主要使用三种混淆 Pass：
1. 控制流平坦化（Control Flow Flattening）
控制流平坦化是 OLLVM 最核心也最具破坏性的混淆。它将函数的基本块（Basic Block）打乱，放入一个巨大的 switch-case 结构中，通过一个状态变量控制执行顺序。
原始代码的控制流图：
┌──────────┐
│ Entry │
└────┬─────┘
↓
┌──────────┐
│ Init S │
└────┬─────┘
↓
┌──────────┐ ┌──────────┐
│ Loop i │────→│ Swap │
└────┬─────┘ └────┬─────┘
│ │
↓ ↓
┌──────────┐ ┌──────────┐
│ Inc j │────→│ Loop End │
└──────────┘ └──────────┘OLLVM 混淆后的控制流图：
┌──────────┐
│ Entry │
└────┬─────┘
↓
┌──────────────────────────────┐
│ while(1) { │
│ switch(state_var) { │
│ case 0: Init S; state=3; break; │
│ case 1: Inc j; state=5; break; │
│ case 2: Loop End; return; │
│ case 3: Loop i; state=1; break; │
│ case 4: Init i; state=0; break; │
│ case 5: Swap; state=3; break; │
│ default: state=?; break; │
│ } │
│ } │
└──────────────────────────────┘对于 RC4 的 KSA 循环，原本清晰的 for(i=0; i<256; i++) 循环体被打散成多个基本块，通过不连续的 case 值串联，极大的增加了分析难度。
2. 虚假控制流（Bogus Control Flow）
虚假控制流在函数中插入永远不会执行的代码路径：
// 原始代码
result = a + b;
// OLLVM 插入虚假分支
if (a != a) { // 永远为假
result = a - b; // 永远不执行
// 可能还有更多虚假代码
if (b > a) {
result = a * b;
}
} else {
result = a + b; // 实际执行
}3. 指令替换（Instruction Substitution）
OLLVM 将简单的运算替换为等价但更复杂的表达式：
// 原始
a = b + c;
// 替换为
a = b - (-c);
// 原始
a = b * 2;
// 替换为
a = b + b;
// 或
a = b << 1;
// 原始
a = b ^ c;
// 替换为
a = (~b) & c) | (b & (~c));静态分析方法
在 IDA 中识别 S-box 操作
面对 OLLVM 混淆的代码，静态分析的第一步是识别算法的特征模式。
1. 查找 256 字节循环
RC4 的 KSA 中有两个 256 次循环。在 ARM 汇编中，循环通常表现为比较和条件跳转：
; 标准循环结构（可能被 OLLVM 打散）
CMP R0, #256 ; 比较 i < 256
BGE loop_end ; 不满足条件则跳出
; ... 循环体
ADD R0, R0, #1 ; i++
B loop_condition ; 继续循环在 OLLVM 混淆后，比较和跳转可能分散在不同的基本块中，但 CMP Rx, #0x100（256）和 ADD Rx, Rx, #1 的组合仍然存在。
2. 识别 S-box 交换操作
S-box 交换的底层模式是三条指令：
LDRB R2, [R_base, R_i] ; 加载 S[i]
LDRB R3, [R_base, R_j] ; 加载 S[j]
STRB R2, [R_base, R_j] ; S[j] = S[i]（先存）
STRB R3, [R_base, R_i] ; S[i] = S[j]（后存）在 IDA 中搜索这种 “加载两个字节 → 交叉存储” 的模式，可以快速定位 S-box 操作。
3. 识别 XOR 加密操作
PRGA 中的 XOR 加密：
; data[k] ^= S[(S[i] + S[j]) & 0xFF]
LDRB R6, [R_base, R_i] ; S[i]
LDRB R7, [R_base, R_j] ; S[j]
ADD R8, R6, R7 ; S[i] + S[j]
AND R8, R8, #0xFF ; & 0xFF
LDRB R9, [R_base, R8] ; S[(S[i] + S[j]) & 0xFF]
LDRB R10, [R_data, R_k] ; data[k]
EOR R10, R10, R9 ; XOR
STRB R10, [R_data, R_k] ; 存回IDA 中的分析技巧
技巧一：使用 IDA 的交叉引用
找到 S-box 数组的定义位置（通常是一个 256 字节的 .bss 或 .data 段分配），然后查看所有引用该数组的代码位置。RC4 的 KSA 和 PRGA 都会频繁引用这个数组。
技巧二：识别循环不变量
KSA 中的 key[i % key_len] 有一个循环不变量——key_len 在整个 KSA 过程中不变。在 OLLVM 混淆后的代码中，如果某个寄存器的值在循环前后始终不变，它很可能是 key_len。
技巧三：利用函数调用图
RC4 函数通常会调用一些辅助函数（如内存分配、字符串操作等）。通过函数调用图定位这些辅助函数，再反向追踪调用者，可以找到 RC4 的主函数。
动态分析方法
静态分析 OLLVM 混淆代码效率较低，动态分析方法可以快速获取关键数据。
Frida Hook 追踪密钥流
// Frida 脚本：追踪 RC4 加密过程
// Hook S-box 交换操作
var base_addr = Module.findBaseAddress("libnative.so");
// 定位 KSA 函数
var ksa_addr = base_addr.add(0x1234);
Interceptor.attach(ksa_addr, {
onEnter: function(args) {
console.log("[*] RC4 KSA called");
console.log(" S-box addr:", args[0]);
console.log(" Key addr:", args[1]);
console.log(" Key len:", args[2].toInt32());
// Dump 密钥
var key_len = args[2].toInt32();
var key = Memory.readByteArray(args[1], key_len);
console.log(" Key:", hexdump(key, {length: key_len}));
},
onLeave: function(retval) {
console.log("[*] RC4 KSA completed");
// Dump S-box 初始化后的状态
var sbox = Memory.readByteArray(this.context.r0, 256);
console.log(" S-box after KSA:", hexdump(sbox, {length: 256}));
}
});
// Hook PRGA 函数
var prga_addr = base_addr.add(0x5678);
Interceptor.attach(prga_addr, {
onEnter: function(args) {
console.log("[*] RC4 PRGA called");
console.log(" Data addr:", args[0]);
console.log(" Data len:", args[1].toInt32());
// 记录加密前的明文
var len = args[1].toInt32();
var plaintext = Memory.readByteArray(args[0], len);
console.log(" Plaintext:", hexdump(plaintext, {length: len}));
},
onLeave: function(retval) {
console.log("[*] RC4 PRGA completed");
// 记录加密后的密文
var len = this.context.r1.toInt32();
var ciphertext = Memory.readByteArray(this.context.r0, len);
console.log(" Ciphertext:", hexdump(ciphertext, {length: len}));
}
});Frida 追踪密钥流字节
如果无法精确定位 KSA/PRGA 函数入口，可以通过更底层的方式追踪：
// 追踪 XOR 操作来识别密钥流
Interceptor.attach(base_addr.add(0x8A00), { // XOR 指令地址
onEnter: function(args) {
console.log("[XOR] R0:", this.context.r0.toString(16),
"R1:", this.context.r1.toString(16),
"Result:", (this.context.r0 ^ this.context.r1).toString(16));
}
});通过收集多次 XOR 的输入和输出，可以推断出密钥流的值。
完整还原步骤
以下是对 OLLVM 混淆的 RC4 函数进行完整还原的步骤：
第一步：识别 KSA
静态线索：
- 函数开头有 256 次循环（
CMP Rx, #0x100） - 循环体中有一个递增的赋值操作（
S[i] = i） - 紧接着是第二个 256 次循环，包含 S-box 交换操作
动态验证：
- Hook 函数入口，传入已知的密钥
- 观察 S-box 的变化：第一个循环后 S-box 应为
{0, 1, 2, ..., 255} - 第二个循环后 S-box 应为经过密钥打乱的状态
第二步：确认 PRGA
静态线索：
- 循环计数器通常从 0 递增到数据长度
- 包含两次 S-box 交换（每次迭代两次）
- 最终有 XOR 操作与数据进行加密
动态验证：
- 传入已知明文和已知密钥
- 收集加密后的密文
- 用标准 RC4 验证密文是否匹配
第三步：提取密钥
方法一：静态分析密钥传递链
追踪密钥参数的来源。在 OLLVM 混淆的代码中，密钥可能是：
- 硬编码在代码中的常量
- 通过函数参数传入
- 通过字符串解密动态生成
- 从网络或其他输入源获取
方法二：动态 Hook 提取
// 在 KSA 入口处提取密钥
Interceptor.attach(ksa_addr, {
onEnter: function(args) {
var key = Memory.readUtf8String(args[1], args[2].toInt32());
console.log("[+] RC4 Key:", key);
console.log("[+] RC4 Key (hex):",
Memory.readByteArray(args[1], args[2].toInt32()));
}
});第四步：验证还原结果
还原出密钥和算法后，编写独立的验证脚本：
# 验证还原的 RC4 实现
def rc4_decrypt(data, key):
# KSA
S = list(range(256))
j = 0
for i in range(256):
j = (j + S[i] + key[i % len(key)]) % 256
S[i], S[j] = S[j], S[i]
# PRGA
i = j = 0
result = bytearray()
for byte in data:
i = (i + 1) % 256
j = (j + S[i]) % 256
S[i], S[j] = S[j], S[i]
result.append(byte ^ S[(S[i] + S[j]) % 256])
return bytes(result)
# 使用提取的密钥验证
ciphertext = bytes.fromhex("1a2b3c4d5e6f")
key = b"my_secret_key"
plaintext = rc4_decrypt(ciphertext, key)
print("Decrypted:", plaintext)完整案例分析
目标信息
- 目标 APP：某即时通讯应用
- 目标函数：
libnative.so中的msg_encrypt函数 - 混淆方式：OLLVM（控制流平坦化 + 指令替换）
- 保护算法：RC4
分析过程
1. IDA 静态分析
在 IDA 中打开 libnative.so，找到 msg_encrypt 函数。函数控制流图极其复杂：
- 包含 80+ 个基本块
- 分发器中 case 值不连续（0, 3, 7, 2, 5, …）
- 大量
CMP和条件跳转
2. 识别关键模式
通过搜索 CMP Rx, #0x100，找到了 KSA 的 256 次循环。通过搜索 EOR 指令并结合 S-box 数组的引用，定位了 PRGA 的 XOR 加密操作。
3. Frida 动态验证
发送一条消息"hello"，Hook KSA 入口：
[*] RC4 KSA called
Key: 0xB4F2E8C1A6D3... (32 bytes hex)4. 完整还原
最终还原出的 msg_encrypt 伪代码：
void msg_encrypt(char* plaintext, int len, uint8_t* output) {
// 密钥是硬编码在 SO 文件中的 32 字节常量
uint8_t key[32] = {0xB4, 0xF2, 0xE8, 0xC1, 0xA6, 0xD3, ...};
uint8_t S[256];
// KSA
for (int i = 0; i < 256; i++) S[i] = i;
int j = 0;
for (int i = 0; i < 256; i++) {
j = (j + S[i] + key[i % 32]) & 0xFF;
uint8_t t = S[i]; S[i] = S[j]; S[j] = t;
}
// PRGA
int ii = 0; j = 0;
for (int k = 0; k < len; k++) {
ii = (ii + 1) & 0xFF;
j = (j + S[ii]) & 0xFF;
uint8_t t = S[ii]; S[ii] = S[j]; S[j] = t;
output[k] = plaintext[k] ^ S[(S[ii] + S[j]) & 0xFF];
}
}总结
OLLVM 混淆虽然极大地扭曲了代码的控制流，但不会改变底层的数据操作语义。通过关注算法的宏观结构（256 次循环、S-box 交换、XOR 加密等特征），结合静态分析识别模式和动态 Hook 验证，可以有效地还原被混淆的 RC4 算法。核心策略是"抓大放小"——不求理解每一行混淆后的代码，而是通过特征匹配定位关键操作。
本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。
