Skip to content

overview

算法逆向工程（Algorithm Reverse Engineering）是逆向工程领域中的核心技能之一，旨在从已编译的二进制程序（如 EXE, ELF, SO, APK）中提取核心逻辑、加密流程或数据处理规则。它不依赖源码，而是通过分析汇编代码、内存状态和输入输出关系来还原算法的数学本质。

一、 核心分析方法论

算法逆向通常采用三种视角的结合：静态分析、动态分析与黑盒分析。

1. 静态分析 (Static Analysis)

静态分析是指在不运行程序的情况下，通过反汇编工具查看代码结构。

  • 控制流分析 (Control Flow Analysis)：通过观察函数的调用图（Call Graph）和控制流图（CFG）来理解程序的执行骨架。循环、分支和递归结构是算法的骨架。

  • 数据流分析 (Data Flow Analysis)：追踪数据在寄存器和内存之间的传递过程。关注关键变量（如密钥、标志位）的来源（Source）和去向（Sink）。

  • 特征码识别：通过搜索特定的字节序列或字符串来快速定位标准算法（如 Base64 索引表、AES S-盒）。

2. 动态分析 (Dynamic Analysis)

动态分析是指在程序运行时，使用调试器监控其行为。

  • 单步调试：逐条执行指令，观察寄存器（如 RAX, EAX）和内存的变化，验证静态分析的猜想。

  • 参数监控：在函数入口处下断点，记录传入参数和返回值。

  • 内存转储 (Dump)：当算法涉及复杂的内存变换（如解密后的代码或动态生成的表）时，直接将内存数据导出进行分析。

3. 黑盒分析 (Black-box Analysis)

黑盒分析将算法视为一个数学函数 \(f(x) = y\)，不关注内部实现，仅关注输入与输出的对应关系。

  • 线性探测：输入 \(1, 2, 4, 8\) 等特殊值，观察输出变化，判断是否为位运算。

  • 差分分析：改变输入的某一位，观察输出改变了多少位，以此判断算法的混淆程度（如雪崩效应）。

二、 常见算法特征识别 (Feature Recognition)

识别算法是逆向工程的第一步。标准算法通常具有独特的“指纹”。

1. 魔数与常量 (Magic Numbers & Constants)

大多数标准加密和哈希算法依赖特定的数学常数。

  • MD5：初始化向量 0x67452301, 0xEFCDAB89 等。

  • SHA-1 / SHA-256：特定的初始化哈希值（H0-H7）和轮常数（K）。

  • AES：S-Box（替换表）和逆 S-Box，通常表现为 256 字节的查找表。

  • CRC32：多项式常量 0xEDB88320。

  • 黄金分割比：0x9E3779B9 (常见于 TEA/XTEA 系列算法)。

2. 运算指令特征

  • XOR (异或)：最基础的加密操作。如果代码中出现大量的 XOR 指令，通常与加密或哈希有关。

  • Shift / Rotate (移位/循环移位)：SHL, SHR, ROL, ROR。频繁的移位操作通常出现在哈希函数（混淆数据）或流加密中。

  • Mod (取模)：大数取模运算（div 指令后取余数）是 RSA、ECC 等公钥加密算法的核心特征。

3. 结构特征

  • Feistel 网络：将数据分为左右两半，交替处理，常见于 DES、TEA。

  • SP 网络 (Substitution-Permutation)：包含替换（S-Box）和置换（P-Box）层，常见于 AES。

三、 常见算法分类与逆向策略

1. 编码算法 (Encoding)

编码不是加密，而是数据的格式转换，通常可逆且无密钥。

  • Base64：特征是 64 个字符的索引表 A-Z, a-z, 0-9, +, /。逆向时寻找自定义的索引表（换表 Base64）。

  • Hex：将一个字节转换为两个十六进制字符。

2. 摘要/哈希算法 (Hashing)

将任意长度输入转换为固定长度输出，不可逆。

  • 特征：初始化特定常数，经历多轮循环压缩，无解密过程。

  • 逆向策略：识别算法类型（MD5, SHA, CRC），通过彩虹表碰撞或长度扩展攻击，而非尝试解密。

3. 对称加密 (Symmetric Encryption)

加密和解密使用同一密钥。

  • 流密码 (Stream Cipher)：如 RC4。特征是对密钥生成密钥流（Key Stream），然后与明文进行 XOR。

  • 分组密码 (Block Cipher)：如 AES, DES。特征是明文按块处理（如 16 字节），有多轮复杂的置换和替换。

  • 逆向策略：重点在于提取密钥 (Key) 和初始向量 (IV)，以及确定加密模式（ECB, CBC, GCM）。

4. 非对称加密 (Asymmetric Encryption)

使用公钥加密，私钥解密。

  • RSA：涉及大整数幂取模运算。特征是存在模数 \(N\) 和指数 \(e\)（通常为 65537）。

  • 逆向策略：通常需要提取公钥 \(N\)，尝试分解质因数得到 \(p, q\)，进而计算私钥 \(d\)。

5. 自定义算法 (Custom Algorithms)

开发者自行设计的逻辑，通常涉及位运算、矩阵变换或自动机。

  • 逆向策略：只能通过手动重构代码（将汇编还原为 C/Python），理解其数学逻辑，编写逆算法（Decryptor）或使用约束求解器（如 Z3）求解。

四、 代码混淆与反混淆 (Obfuscation)

为了防止算法被逆向，开发者会使用混淆技术。

  1. 控制流平坦化 (Control Flow Flattening)：将层级化的 if-else 或 while 结构打碎，装入一个巨大的 switch 状态机中，使控制流图变得极其复杂（被称为“上帝节点”）。

  2. 垃圾代码 (Junk Code/Dead Code)：插入永远不会执行的代码，或无效的计算指令，干扰分析者的视线。

  3. 指令替换：用复杂的指令序列替换简单的指令（如用 a = (a ^ b) + 2* (a & b) 替换 a = a + b）。

  4. 虚拟机保护 (Virtualization/VM)：程序内置一个解释器，将真实代码编译为自定义的字节码（Bytecode）。逆向时需要先分析出这个虚拟机的指令集架构。

五、 核心工具栈

  1. 静态分析工具：

    • IDA Pro / Ghidra：工业级反汇编与反编译工具，能将汇编转换为类 C 伪代码。

  2. 动态调试工具：

    • x64dbg / OllyDbg：Windows 平台的用户态调试器。

    • GDB：Linux 平台的调试器。

  3. 动态插桩工具：

    • Frida：通过编写 JavaScript 脚本，在运行时 Hook（钩住）特定函数，修改参数或打印返回值，绕过复杂的内部逻辑。

  4. 算法识别插件：

    • FindCrypt / Signsrch：IDA 的插件，自动扫描代码中的加密常量和魔数。

六、 总结：算法逆向的标准工作流

  1. 定位 (Location)：通过字符串交叉引用、API 调用（如 GetWindowText）或动态调试，找到处理关键数据的函数入口。

  2. 识别 (Identification)：使用插件或经验判断是否为标准算法。如果是标准算法，直接提取密钥；如果是自定义算法，进入下一步。

  3. 分析 (Analysis)：结合静态阅读伪代码和动态调试验证，理解算法的数学变换逻辑。

  4. 还原 (Reconstruction)：用高级语言（Python/C++）重写算法逻辑。

  5. 求解 (Solution)：编写解密脚本（逆运算）或利用数学性质（如模逆元、异或的自反性）获取原始数据。