发布于 

FRIDA辅助分析非标准算法

什么是非标准算法

在 Android 逆向分析中，我们遇到的加密算法大致可以分为两类：标准算法和非标准算法。

  • 标准算法：AES、DES、RSA、MD5、SHA 系列等被广泛使用的密码学算法，有公开的规范和实现
  • 非标准算法：开发者自行实现的加密方案，包括魔改标准算法、白盒加密、自定义迭代加密等

非标准算法是逆向分析中最具挑战性的部分，因为没有现成的算法库可以直接调用，必须完整还原其实现逻辑。

非标准算法的常见类型

类型 描述 难度
魔改 AES/DES 修改 S-Box、调整轮数、改变 Feistel 结构 ★★★
自定义迭代加密 多轮 XOR + 位移 + 查表的组合 ★★★★
白盒加密 将密钥编码到查找表中，隐藏密钥 ★★★★★
自定义哈希 非 MD5/SHA 的自定义摘要算法 ★★★
流密码变体 RC4 改进版、自定义 LFSR ★★★★
多算法组合 AES + 自定义变换 + Base64 变种 ★★★★

非标准算法的识别特征

在分析 SO 文件时，以下特征可以帮助我们识别非标准算法的存在：

1. 大表查表

// Hook 内存读取，检测异常的查表行为
function detectLargeTableAccess(moduleName) {
    var mod = Process.findModuleByName(moduleName);
    var readCount = 0;
    var readPatterns = {};

    // Hook 目标函数
    var funcAddr = mod.base.add(0x1A2B);
    Interceptor.attach(funcAddr, {
        onEnter: function (args) {
            readCount = 0;
            readPatterns = {};
        }
    });

    // 监控该模块内的内存读取
    // 通过在关键点 Hook 来统计
    var checkPoints = [0x1A40, 0x1A55, 0x1A68, 0x1A80];
    checkPoints.forEach(function (off) {
        Interceptor.attach(mod.base.add(off), {
            onEnter: function (args) {
                readCount++;
                // 记录每次读取的地址模式
                var addr = this.context.x0;
                var modAddr = addr.sub(mod.base);
                readPatterns[modAddr.toString()] =
                    (readPatterns[modAddr.toString()] || 0) + 1;
            }
        });
    });

    // 延迟输出分析结果
    setTimeout(function () {
        var entries = Object.keys(readPatterns);
        console.log("\n[查表分析]");
        console.log("总读取次数: " + readCount);
        console.log("不同地址数: " + entries.length);

        if (entries.length > 100 && readCount > 500) {
            console.log("⚠️ 大量查表行为，可能是自定义 S-Box 或白盒加密");
        }
    }, 3000);
}

2. 异常的迭代次数

// 追踪循环次数
function traceLoopIterations(moduleName, loopStartOffset) {
    var mod = Process.findModuleByName(moduleName);
    var loopAddr = mod.base.add(loopStartOffset);
    var iterationCount = 0;
    var maxIterations = 0;

    Interceptor.attach(loopAddr, {
        onEnter: function (args) {
            iterationCount = 0;
            this._startTime = Date.now();
        },
        onLeave: function (retval) {
            var elapsed = Date.now() - this._startTime;
            if (iterationCount > maxIterations) {
                maxIterations = iterationCount;
            }
            console.log("[循环] 迭代次数: " + iterationCount +
                        " 耗时: " + elapsed + "ms");

            if (iterationCount > 16) {
                console.log("⚠️ 迭代次数异常多，可能是自定义加密算法");
                console.log("   标准 AES: 10/12/14 轮");
                console.log("   标准 DES: 16 轮");
                console.log("   标准 MD5: 64 步");
            }
        }
    });

    // 追踪循环体的每次执行
    var loopBodyAddr = mod.base.add(loopStartOffset + 0x10);
    try {
        Interceptor.attach(loopBodyAddr, {
            onEnter: function (args) {
                iterationCount++;
            }
        });
    } catch (e) {
        // 可能不是函数入口，无法 Hook
    }
}

3. 奇怪的常量

// 检测函数中使用的非常量
function detectUnusualConstants(moduleName, funcOffset, funcSize) {
    var mod = Process.findModuleByName(moduleName);
    var startAddr = mod.base.add(funcOffset);

    // 已知的魔数常量
    var knownConstants = {
        0x637C777B: "AES S-Box 前缀",
        0x67452301: "MD5 初始值 A",
        0xEFCDAB89: "MD5 初始值 B",
        0x98BADCFE: "MD5 初始值 C",
        0x10325476: "MD5 初始值 D",
        0x5A827999: "SHA-1 常量 K0",
        0x6ED9EBA1: "SHA-1 常量 K1",
        0x01010101: "AES/DES 填充"
    };

    console.log("[常量检测] 扫描 " + funcOffset +
                " - 0x" + (funcOffset + funcSize).toString(16));

    // 通过读取内存来扫描常量
    var pattern = [];
    for (var offset = 0; offset < funcSize; offset += 4) {
        try {
            var val = startAddr.add(offset).readU32();
            if (knownConstants[val]) {
                console.log("  [已知] 0x" + val.toString(16) +
                            " @ +0x" + offset.toString(16) +
                            " → " + knownConstants[val]);
            }
            // 检测大数值常量（可能是自定义的）
            if (val > 0x10000000 && val < 0xFFFFFFFF &&
                !knownConstants[val]) {
                // 可能是自定义常量
            }
        } catch (e) {}
    }
}

使用 Frida 追踪算法执行过程

参数→运算→输出的完整追踪

// 算法执行过程追踪器
function traceAlgorithmExecution(moduleName, funcOffset) {
    var mod = Process.findModuleByName(moduleName);
    var funcAddr = mod.base.add(funcOffset);

    Interceptor.attach(funcAddr, {
        onEnter: function (args) {
            console.log("\n[算法执行开始]");
            console.log("时间: " + new Date().toISOString());

            // 记录输入参数
            this._input = {
                arg0: args[0],
                arg1: args[1],
                arg2: args[2] ? args[2].toInt32() : 0
            };

            // 尝试读取输入数据
            try {
                var inputLen = args[2].toInt32();
                if (inputLen > 0 && inputLen < 4096) {
                    console.log("[输入] 长度: " + inputLen);
                    console.log(hexdump(args[0], { length: inputLen }));
                }
            } catch (e) {}

            // 保存初始寄存器状态
            this._initialRegs = {
                x0: this.context.x0,
                x1: this.context.x1,
                x2: this.context.x2
            };
        },
        onLeave: function (retval) {
            console.log("\n[算法执行结束]");
            console.log("[输出] 返回值: " + retval);

            // 尝试读取输出缓冲区
            try {
                var outputLen = this._input.arg2;
                if (outputLen > 0 && outputLen < 4096) {
                    console.log("[输出缓冲区]");
                    console.log(hexdump(this._input.arg0, {
                        length: outputLen
                    }));
                }
            } catch (e) {}
        }
    });
}

traceAlgorithmExecution("libcrypto.so", 0x4A20);

追踪中间运算结果

在算法的关键运算节点设置 Hook，记录中间值：

// 在算法的多个关键点记录运算结果
function traceIntermediateValues(moduleName, tracePoints) {
    var mod = Process.findModuleByName(moduleName);
    var callIndex = 0;

    tracePoints.forEach(function (point) {
        var addr = mod.base.add(point.offset);
        var label = point.label || ("0x" + point.offset.toString(16));

        try {
            Interceptor.attach(addr, {
                onEnter: function (args) {
                    callIndex++;
                    var ctx = this.context;

                    // 记录关键寄存器的值
                    var snapshot = {
                        index: callIndex,
                        label: label,
                        x0: ctx.x0.toInt32(),
                        x1: ctx.x1.toInt32(),
                        x2: ctx.x2.toInt32(),
                        x3: ctx.x3.toInt32()
                    };

                    console.log("[T" + callIndex + "][" + label + "] " +
                        "x0=0x" + snapshot.x0.toString(16) + " " +
                        "x1=0x" + snapshot.x1.toString(16) + " " +
                        "x2=0x" + snapshot.x2.toString(16) + " " +
                        "x3=0x" + snapshot.x3.toString(16));

                    // 如果指定了内存读取点
                    if (point.readPtr) {
                        try {
                            var data = ctx[point.readPtr.reg];
                            var len = point.readPtr.len || 16;
                            console.log("  内存[" + point.readPtr.reg + "]:");
                            console.log(hexdump(data, { length: len }));
                        } catch (e) {}
                    }
                }
            });
            console.log("[+] 追踪点: " + label + " @ 0x" +
                        point.offset.toString(16));
        } catch (e) {
            console.log("[-] 无法 Hook: " + label);
        }
    });
}

// 使用示例：在加密算法的关键运算点设置追踪
traceIntermediateValues("libcrypto.so", [
    { offset: 0x4A30, label: "SubBytes 入口" },
    { offset: 0x4A60, label: "ShiftRows 入口" },
    { offset: 0x4A90, label: "MixColumns 入口",
      readPtr: { reg: "x0", len: 16 } },
    { offset: 0x4AC0, label: "AddRoundKey 入口" },
    { offset: 0x4B00, label: "最终输出" }
]);

Taint Analysis 思想在 Frida 中的应用

Taint Analysis（污点分析）是一种跟踪数据流传播的技术。在 Frida 中，我们可以手动实现类似的效果——标记输入数据的来源，然后追踪这些数据在算法中的传播路径。

简易污点追踪

// Frida 中的简易污点分析
function taintTrack(moduleName, funcOffset, inputSize) {
    var mod = Process.findModuleByName(moduleName);
    var funcAddr = mod.base.add(funcOffset);
    var taintedBytes = {};

    Interceptor.attach(funcAddr, {
        onEnter: function (args) {
            // 标记输入数据为"已污染"
            var inputPtr = args[0];
            var taintId = "INPUT_" + Date.now();

            console.log("[污点分析] 标记输入 " + inputSize + " 字节");

            // 在多个关键点检查是否有"污染数据"参与运算
            var checkPoints = [0x4A30, 0x4A50, 0x4A80, 0x4AB0, 0x4AE0];
            checkPoints.forEach(function (cpOff) {
                try {
                    Interceptor.attach(mod.base.add(cpOff), {
                        onEnter: function (args) {
                            // 比较当前寄存器值与原始输入
                            var ctx = this.context;
                            var regs = ['x0', 'x1', 'x2', 'x3'];
                            regs.forEach(function (reg) {
                                var val = ctx[reg];
                                // 检查该值是否指向输入数据区域
                                var offset = val.sub(inputPtr);
                                if (offset.compare(ptr(0)) >= 0 &&
                                    offset.compare(ptr(inputSize)) < 0) {
                                    console.log("[污点传播] " +
                                        reg + " 指向输入偏移 " +
                                        offset.toInt32() + " @ 0x" +
                                        cpOff.toString(16));
                                }
                            });
                        }
                    });
                } catch (e) {}
            });
        }
    });
}

非标准算法的还原策略

还原方法论

还原非标准算法通常遵循以下策略：

1. 黑盒测试
   → 使用不同输入多次调用，观察输入输出关系
   → 判断是加密/哈希/编码

2. 特征识别
   → 分析 S-Box、迭代次数、常量
   → 判断是否基于某个标准算法魔改

3. 动态追踪
   → 使用 Frida 记录每一步运算
   → 构建运算序列

4. 分步还原
   → 将算法拆分为独立的步骤
   → 逐个步骤还原并验证

5. 完整实现
   → 用 Python/C 重写还原的算法
   → 对比验证

黑盒测试脚本

// 算法黑盒测试
function blackBoxTest(moduleName, funcOffset) {
    var mod = Process.findModuleByName(moduleName);
    var funcAddr = mod.base.add(funcOffset);

    // 准备测试用例
    var testCases = [
        { input: [0x41, 0x41, 0x41, 0x41], desc: "AAAA" },
        { input: [0x00, 0x00, 0x00, 0x00], desc: "NULL" },
        { input: [0xFF, 0xFF, 0xFF, 0xFF], desc: "0xFF" },
        { input: [0x01, 0x02, 0x03, 0x04], desc: "递增" },
        { input: [0x48, 0x65, 0x6C, 0x6C, 0x6F], desc: "Hello" }
    ];

    var results = [];
    var testIndex = 0;

    // 分配输入缓冲区
    var inputBuf = Memory.alloc(1024);
    var outputBuf = Memory.alloc(1024);

    testCases.forEach(function (tc) {
        // 写入测试输入
        for (var i = 0; i < tc.input.length; i++) {
            inputBuf.add(i).writeU8(tc.input[i]);
        }

        Interceptor.attach(funcAddr, {
            onEnter: function (args) {
                // 替换输入为我们的测试数据
                args[0] = inputBuf;
                args[2] = ptr(tc.input.length);
                this._testCase = tc;
            },
            onLeave: function (retval) {
                // 读取输出
                var output = [];
                for (var i = 0; i < 32; i++) {
                    try {
                        output.push(("0" +
                            outputBuf.add(i).readU8().toString(16))
                            .slice(-2));
                    } catch (e) {
                        break;
                    }
                }

                console.log("\n[测试] " + tc.desc +
                            " (len=" + tc.input.length + ")");
                console.log("  输入: " + tc.input.map(function (b) {
                    return ("0" + b.toString(16)).slice(-2);
                }).join(" "));
                console.log("  输出: " + output.join(" "));
            }
        });
    });
}

实际案例：某 APP 的自定义加密还原

以某 APP 的自定义加密函数为例，展示完整的还原过程。

分析发现：

  1. 函数接收 16 字节输入，输出 16 字节
  2. 内部有一个 256 字节的查找表（自定义 S-Box）
  3. 共执行 4 轮变换，每轮包含：查表替换 → 行移位 → 列混合
  4. 列混合使用的不是 AES 标准的 GF(2^8) 乘法，而是自定义的运算

还原步骤：

// Step 1: 提取自定义 S-Box
function extractCustomSBox(moduleName, sboxOffset) {
    var mod = Process.findModuleByName(moduleName);
    var sboxAddr = mod.base.add(sboxOffset);
    var sbox = [];

    console.log("[S-Box 提取]");
    for (var i = 0; i < 256; i++) {
        sbox.push(sboxAddr.add(i).readU8());
    }

    // 输出为 C 数组格式
    var lines = [];
    for (var row = 0; row < 16; row++) {
        var hexValues = [];
        for (var col = 0; col < 16; col++) {
            hexValues.push("0x" +
                ("0" + sbox[row * 16 + col].toString(16)).slice(-2));
        }
        lines.push("    " + hexValues.join(", "));
    }
    console.log("uint8_t sbox[256] = {\n" +
                lines.join(",\n") + "\n};");

    return sbox;
}

// Step 2: 验证每轮变换的输入输出
function verifyRoundTransform(moduleName, roundOffsets) {
    var mod = Process.findModuleByName(moduleName);

    roundOffsets.forEach(function (off, round) {
        var addr = mod.base.add(off);
        Interceptor.attach(addr, {
            onEnter: function (args) {
                console.log("\n[第 " + (round + 1) + " 轮变换]");
                var state = [];
                for (var i = 0; i < 16; i++) {
                    state.push(("0" +
                        args[0].add(i).readU8().toString(16)).slice(-2));
                }
                console.log("  输入状态: " + state.join(" "));
            },
            onLeave: function (retval) {
                // 某些变换可能就地修改，需要重新读取
            }
        });
    });
}

// Step 3: 对比还原算法与原始函数
// 在 Python 端实现还原的算法，然后通过 Frida 对比验证

总结

非标准算法是 Android 逆向中的核心难题。本文介绍了非标准算法的识别特征、使用 Frida 追踪算法执行过程的方法、Taint Analysis 思想的应用，以及从黑盒测试到分步还原的完整策略。关键要点是：先通过黑盒测试理解算法的输入输出特性，再通过动态追踪理解内部运算过程，最后逐步还原并用对比验证确保正确性。

许可协议

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

分享文章
快来参与讨论吧