发布于 

针对 Base64、CRC32、MD5、SHA1 等算法的还原案例

前言

在 Android 逆向分析中，识别和还原标准算法是最基础也最高频的工作。很多时候 APP 使用的并不是自创算法，而是经过轻微伪装的标准算法。本文将通过 Base64、CRC32、MD5、SHA1 四种常见算法的还原案例，讲解如何从 SO 代码中快速识别标准算法，并给出完整的还原思路和实用工具推荐。

Base64 算法的识别与还原

Base64 原理回顾

Base64 是一种将二进制数据编码为 ASCII 字符的编码方式。编码表为 ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/，共 64 个字符。编码时，每 3 个字节（24 位）被分成 4 组、每组 6 位，映射到编码表中的字符。如果输入长度不是 3 的倍数，则用 = 填充。

识别特征

在 SO 代码中识别 Base64 编码，主要依赖以下特征：

1. 编码查表

Base64 编码的核心是一个 64 字节的查找表，内容为 ASCII 字符：

static const char base64_table[] = 
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    "abcdefghijklmnopqrstuvwxyz"
    "0123456789+/";

在 IDA 中，搜索这个字符串常量是识别 Base64 最直接的方式。

2. 解码查表

解码时通常使用一个 256 字节的反向查找表，或者使用位运算来解码：

static const int base64_decode_table[256] = {
    // 对非 Base64 字符设为 -1
    // 'A'-'Z' 对应 0-25, 'a'-'z' 对应 26-51
    // '0'-'9' 对应 52-61, '+' 对应 62, '/' 对应 63
    -1, -1, -1, -1, ...,  // 0-43
    62,                     // '+' (43)
    -1, -1, -1,             // 44-46
    63,                     // '/' (47)
    52, 53, 54, ..., 61,    // '0'-'9'
    -1, -1, -1, -1, ...,   // ':'-'@'
    0, 1, 2, ..., 25,       // 'A'-'Z'
    -1, -1, -1, -1, ...,   // '['-'`'
    26, 27, 28, ..., 51     // 'a'-'z'
};

3. 代码结构特征

Base64 编码的循环结构特征明显：以 3 字节为单位处理，通过移位和掩码操作提取 6 位数据，然后查表输出。

还原方法

识别出 Base64 后，还原非常简单：

import base64

# 编码
encoded = base64.b64encode(plaintext).decode()

# 解码
decoded = base64.b64decode(encoded_str).decode()

需要注意 APP 可能使用了 变体 Base64，例如：

  • URL 安全 Base64：+ 替换为 -，/ 替换为 _
  • 无填充 Base64：去除尾部的 =
  • 自定义字母表：将标准字母表打乱

CRC32 算法的识别与还原

CRC32 原理回顾

CRC32（Cyclic Redundancy Check）是一种校验和算法，通过多项式除法生成 32 位校验值。其核心是一个 256 项的 查表，表项由生成多项式计算得到。

最常见的 CRC32 多项式为：

  • 标准 CRC32：0x04C11DB7（以太网、ZIP、PNG）
  • CRC32C（Castagnoli）：0x1EDC6F41（iSCSI、SSE4.2）

识别特征

1. 查表法特征

CRC32 使用一个 1024 字节（256 × 4）的查找表。在 IDA 中，可以通过数据窗口找到这个表，表的值通常呈现特定的数学规律：

static const uint32_t crc32_table[256] = {
    0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
    0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
    // ... 共 256 项
};

2. 初始值和最终异或值

标准 CRC32 的初始值为 0xFFFFFFFF，计算完成后与 0xFFFFFFFF 进行异或（即取反）。这两个常量也是重要的识别线索。

3. 多项式常量

如果在代码中发现 0xEDB88320（0x04C11DB7 的反转多项式），几乎可以确定是标准 CRC32。

还原方法

import binascii

# 计算 CRC32
crc = binascii.crc32(data) & 0xFFFFFFFF

# 还原时需要确认参数：多项式、初始值、是否取反、是否反转输入/输出

对于非标准 CRC32，可以使用以下工具确认参数：

MD5 算法的识别与还原

MD5 识别特征

1. 魔数常量（初始化向量）

MD5 使用 4 个 32 位的初始化链接变量，这是最可靠的识别特征：

A = 0x67452301;
B = 0xefcdab89;
C = 0x98badcfe;
D = 0x10325476;

在 IDA 中搜索这些常量值，可以直接定位 MD5 算法的实现。

2. 常量表 T

MD5 的 64 步操作每步使用一个常量 T[i] = floor(2^32 × abs(sin(i+1)))：

static const uint32_t T[64] = {
    0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
    // ... 共 64 个值
};

搜索 0xd76aa478 这个值，是识别 MD5 的快捷方式。

3. 位移量表

MD5 的 64 步操作使用固定的循环左移量，以数组形式存储：

static const int s[64] = {
    7, 12, 17, 22, 7, 12, 17, 22,  // 第1轮
    5, 9, 14, 20, 5, 9, 14, 20,    // 第2轮
    4, 11, 16, 23, 4, 11, 16, 23,  // 第3轮
    6, 10, 15, 21, 6, 10, 15, 21   // 第4轮
};

还原案例

场景：某 APP 的 API 请求中有一个 sign 参数，怀疑是 MD5 签名。

Step 1：定位算法

使用 IDA 搜索字符串 “MD5” 或常量 0x67452301，找到 MD5 实现函数。

Step 2：确认输入

在 IDA 中查看调用 MD5 函数的上层逻辑，确认签名输入是哪些数据拼接而成：

sign = MD5(timestamp + nonce + appkey + body)

Step 3：Hook 提取参数

// Frida Hook MD5 实现
Java.perform(function() {
    var MessageDigest = Java.use("java.security.MessageDigest");
    MessageDigest.getInstance.overload('java.lang.String').implementation = function(algo) {
        console.log("[MD5] MessageDigest.getInstance: " + algo);
        var result = this.getInstance(algo);
        return result;
    };
    
    MessageDigest.update.overload('[B').implementation = function(input) {
        console.log("[MD5] update data: " + bytes2hex(input));
        this.update(input);
    };
    
    MessageDigest.digest.overload().implementation = function() {
        var result = this.digest();
        console.log("[MD5] digest result: " + bytes2hex(result));
        return result;
    };
});

Step 4：验证还原

将提取的输入数据用 Python 的 hashlib.md5() 计算，与 APP 输出对比验证。

SHA1 算法的识别与还原

SHA1 识别特征

1. 初始化常量

SHA1 使用 5 个 32 位的初始化哈希值：

H0 = 0x67452301;  // 与 MD5 相同
H1 = 0xEFCDAB89;  // 与 MD5 相同
H2 = 0x98BADCFE;  // 与 MD5 相同
H3 = 0x10325476;  // 与 MD5 相同
H4 = 0xC3D2E1F0;  // SHA1 独有

注意 H0-H3 与 MD5 相同，但 SHA1 多了一个 H4 = 0xC3D2E1F0。如果看到这 5 个常量同时出现，可以确定是 SHA1。

2. 轮常量

SHA1 在 80 轮操作中使用两个常量：

// 第 0-19 轮
#define K1 0x5A827999
// 第 20-39 轮
#define K2 0x6ED9EBA1
// 第 40-59 轮
#define K3 0x8F1BBCDC
// 第 60-79 轮
#define K4 0xCA62C1D6

搜索 0x5A827999 可以快速定位 SHA1 实现。

还原方法

import hashlib

# SHA1 哈希
sha1_result = hashlib.sha1(data).hexdigest()

# SHA1 with HMAC
import hmac
hmac_sha1 = hmac.new(key, message, hashlib.sha1).hexdigest()

IDA 插件辅助识别

FindCrypt

FindCrypt 是 IDA 最经典的密码学常量识别插件。它会扫描整个 SO 文件中的常量，自动识别已知的密码学算法。

安装和使用：

  1. 将 FindCrypt 的 .so 或 .dll 文件放入 IDA 插件目录
  2. 在 IDA 中选择 Edit → Plugins → FindCrypt
  3. 插件会列出所有识别到的密码学算法及其在代码中的位置

FindCrypt 内置了对以下算法的识别：

  • AES（S-box, 逆 S-box, T-table）
  • DES/3DES（S-box, IP, FP 置换表）
  • MD5（初始化常量, T 表）
  • SHA1/SHA256（初始化常量, K 表）
  • RC4（初始化代码特征）
  • Blowfish、CAST、Camellia 等

KANAL（从 CryptoAudit 工具集）

KANAL 是 FindCrypt 的增强版本，能识别更多算法变体：

KANAL 支持的算法包括但不限于：
- AES, DES, 3DES, Blowfish, Twofish, Serpent, RC4, RC5, RC6
- MD5, SHA1, SHA256, SHA512, RIPEMD160
- RSA, DSA, ECC
- CRC32, Adler32
- Base64, HMAC, PBKDF2

使用建议：先用 FindCrypt/KANAL 快速扫描一遍 SO 文件，确定使用了哪些算法，然后再针对性地进行深入分析。

通过 Hook 确认算法类型

当静态分析不确定算法类型时，可以使用 Frida 进行动态验证。

Hook Java 层 MessageDigest

Java.perform(function() {
    var MessageDigest = Java.use("java.security.MessageDigest");
    
    MessageDigest.getInstance.overload('java.lang.String').implementation = function(algo) {
        console.log("[*] MessageDigest algorithm: " + algo);
        return this.getInstance(algo);
    };
});

Hook Native 层函数

对于 SO 中自实现的算法，可以在关键位置设置 Hook：

// Hook MD5 的 Update 函数，监控输入数据
Interceptor.attach(Module.findExportByName("libnative.so", "md5_update"), {
    onEnter: function(args) {
        var data = args[1];
        var len = args[2].toInt32();
        console.log("[MD5] update: " + hexdump(data, {length: len}));
    }
});

使用 LibFuzzer 进行碰撞测试

对于不确定的哈希算法，可以准备已知的输入-输出对来验证猜测。例如，输入空字符串和 “abc”，对比标准算法的输出：

输入 MD5 SHA1
“” d41d8cd98f00b204e9800998ecf8427e da39a3ee5e6b4b0d3255bfef95601890afd80709
“abc” 900150983cd24fb0d6963f7d28e17f72 a9993e364706816aba3e25717850c26c9cd0d89d

完整还原案例：某 APP 签名算法

场景：某 APP 的登录接口需要传递 sign 参数。

Step 1：抓包分析

抓包发现 sign 是一个 32 位十六进制字符串，长度为 32 字符，初步判断可能是 MD5（128 位 = 32 hex）。

Step 2：Hook 确认

使用 Frida Hook MessageDigest.getInstance()，确认算法为 MD5。

Step 3：追踪输入

Hook MessageDigest.update() 和 MessageDigest.digest()，发现签名输入为：

sign = MD5(appkey + timestamp + nonce + password_md5)

其中 password_md5 是用户密码的 MD5 值。

Step 4：编写还原脚本

import hashlib
import time
import random
import string

def generate_sign(appkey, password, timestamp=None, nonce=None):
    if timestamp is None:
        timestamp = str(int(time.time()))
    if nonce is None:
        nonce = ''.join(random.choices(string.ascii_lowercase + string.digits, k=8))
    
    password_md5 = hashlib.md5(password.encode()).hexdigest()
    raw = appkey + timestamp + nonce + password_md5
    sign = hashlib.md5(raw.encode()).hexdigest()
    
    return sign, timestamp, nonce

# 使用示例
sign, ts, nonce = generate_sign("app_key_123", "user_password")
print(f"sign={sign}&timestamp={ts}&nonce={nonce}")

Step 5：验证

将生成的请求参数发送到服务器，对比响应结果确认签名正确。

小结

标准算法的识别和还原是 Android 逆向中最常见的工作。核心方法是：通过常量特征快速识别算法类型，通过 Hook 提取算法参数（密钥、IV、输入数据），然后直接调用标准库函数完成还原。 工具链方面，IDA 插件（FindCrypt/KANAL）+ Frida Hook + Python 标准库的组合可以覆盖绝大多数场景。对于非标准算法变体，需要在识别出基础算法后，对比标准实现和实际实现的差异来完成还原。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章
快来参与讨论吧