一道算法题

资讯作者：看雪学院 2021-04-17 18:42:27 阅读：590

本文为看雪论坛文章

看雪论坛作者ID：GitRoy

本题为看雪3w班级作业题，大家感兴趣可以玩一下。

0x1 通过JEB分析APK

0x2 查看so

发现所有函数都被ollvm了，所以按照之前学到的常规分析方法，开始分析。整理好思路如下：

0x3 构建自己的思路

1. 先静态分析，通过交叉引用或者自己的猜测大概知道哪些函数可能会参与到返回值的生成中。

2. 基于frida，构造主动调用，并对可能的函数进行hook，验证自己的猜想，并且找出核心参与返回值计算的函数。

3. 挂上ida trace，将核心函数的结果保存到本地。

4. 仔细分析本地的结果，并还原加密算法。

5. IDA F5不可信，随便看一下就好了。

0x4 执行自己的思路

构造主动调用：

function call_fun() {Java.perform(function () {var main = Java.use('com.kanxue.ollvm_ndk.MainActivity')// main.UUIDCheckSum.implementation = function(arg1){//     console.log('java input is',arg1);//     return main.UUIDCheckSum(arg1);// }var res = main.UUIDCheckSum('vm8MRDk58srS2jDoRAIswzJU0ALS0z2P50lK');console.log('java res is: ', res);})}

针对交叉引用进行hook：

下面是我通过分析后，猜测可能会参数过程的函数，我把他们都hook了。

function hook_native() {var libBase = Module.getBaseAddress('libnative-lib.so');var inputStr;Interceptor.attach(libBase.add(0xFCB4), {onEnter: function (args) {// console.log('0xFCB4 Enter');// console.log(hexdump(args[0]));// inputStr = args[0];// console.log(args[1]);  }, onLeave: function () {// console.log('0xFCB4 onleave');// console.log(hexdump(inputStr));}  })var inputStr2c;var intpuStrIn;Interceptor.attach(libBase.add(0x1029C), {onEnter: function (args) {inputStr2c = args[0]// console.log(Memory.readUtf8String(args[1]));}, onLeave: function (retval) {// console.log(hexdump(inputStr2c);// console.log(hexdump(intpuStrIn));}  })  //nl9LSEj4-rsR3-4nS@-rv{K1-@MR1{3Q412bInterceptor.attach(libBase.add(0xF9B8), {onEnter: function (args) {//    console.log(hexdump(args[]));// console.log(args[2]);}, onLeave: function (retval) {// console.log(retval);}  })  Interceptor.attach(libBase.add(0xF04C), {onEnter: function (args) {// console.log(hexdump(args[0]));//    console.log(hexdump(args[]));// console.log(args[1]);}, onLeave: function (retval) {// console.log(hexdump(retval));}  })    Interceptor.attach(libBase.add(0xF270), {onEnter: function (args) {// console.log(hexdump(args[0]));//    console.log(hexdump(args[]));// console.log(args[1]);}, onLeave: function (retval) {// console.log(hexdump(retval));console.log(Memory.readUtf8String(retval.add(1)));}  })  }

通过一系列hook后的分析，发现sub_FCB4会对输入做第一层加密，然后sub_F270与返回值息息相关。

sub_F270返回结果，地址+1就和真正的返回值对的上。

综上所述，我想着重trace两个函数：

(1) sub_FCB4

(2) sub_F404C

0x5 第一个算法Trace FCB4

Trace 结果:

配合F5 伪代码继续分析:

通过一段时间的分析，与Trace结果比对，还原第一个加密算法。

int main() {    using namespace std;    //vm8MRDk58srS2jDoRAIswzJU0ALS0z2P50lK    std::cout << "Hello, World!" << std::endl;    char *input = "vm8MRDk58srS2jDoRAIswzJU0ALS0z2P50lK";    char encode_input[strlen(input)];    int v14 = 0xFF;    int v16 = 0;    int key[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};    for (int i = 0; i < strlen(input) - 2; ++i) {        char s = input[i] ^1;        bool v10 = i == 8 || i == 13;        bool v11 = i == 14;        bool v12 = i == 18;        bool v13 = i == 24;        if (v10 || i == 14 || i == 18 || i == 24) {            if (v10 || v12 || v13) {                s = '-';                encode_input[i] = s;                continue;            }        }        if (v11) {            s = 0x34;            encode_input[i] = s;            continue;        }          if (i == 23) {            s = input[i + 1] ^ 1;        }        //这里等于24的时候有特殊处理，v14和v16不做重新赋值,保留当前状态        if (i != 24) {            if (i != 23) {                v14 = v14 ^ input[i];                v16 = v16 + input[i];            } else {                v14 = v14 ^ input[i + 1];                v16 = v16 + input[i + 1];            }        }        encode_input[i] = s;    }    encode_input[34] = key[v16 - (v16 & 0xFFFFFFF0)];    encode_input[35] = key[v14 & 0xf];    std::cout << encode_input << std::endl;      return 0;}

验证结果：

input:wl9LSEj4-rsR3-4nS@-rv{K1-@MR1{3Q4192

resul:wl9LSEj4-rsR3-4nS@-rv{K1-@MR1{3Q4192

0x6 第二个算法 F404C

核心代码，仔细看了一下，混淆的不厉害，不太需要Trace，直接动态调试。最终调试出下面关键伪代码：

所以还原整个算法代码如下：

#include <iostream>  using namespace std;    void result(char **m_result, char word) {      **m_result = word;//    printf("%x\n", *m_result);//    printf("%s\n", **m_result);    *m_result = *m_result + 1;}  int main() {    //vm8MRDk58srS2jDoRAIswzJU0ALS0z2P50lK    std::cout << "Hello, World!" << std::endl;    //第一个算法    char *input = "vm8MRDk58srS2jDoRAIswzJU0ALS0z2P50lK";    char encode_input[strlen(input)];    int v14 = 0xFF;    int v16 = 0;    int key[] = {0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x2D, 0x5F, 0x61, 0x62, 0x63, 0x64, 0x65,                 0x66, 0x67, 0x68, 0x69, 0x6A, 0x6B, 0x6C,                 0x6D, 0x6E, 0x6F, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78,                 0x79, 0x7A, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4A,                 0x4B, 0x4C, 0x4D, 0x4E, 0x4F, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56,                 0x57, 0x58, 0x59, 0x5A};    for (int i = 0; i < strlen(input) - 2; ++i) {        char s = input[i] ^1;        bool v10 = i == 8 || i == 13;        bool v11 = i == 14;        bool v12 = i == 18;        bool v13 = i == 24;        if (v10 || i == 14 || i == 18 || i == 24) {            if (v10 || v12 || v13) {                s = '-';                encode_input[i] = s;                continue;            }        }        if (v11) {            s = 0x34;            encode_input[i] = s;            continue;        }          if (i == 23) {            s = input[i + 1] ^ 1;        }        if (i != 24) {            if (i != 23) {                v14 = v14 ^ input[i];                v16 = v16 + input[i];            } else {                v14 = v14 ^ input[i + 1];                v16 = v16 + input[i + 1];            }        }        encode_input[i] = s;    }    encode_input[34] = key[v16 - (v16 & 0xFFFFFFF0)];    encode_input[35] = key[v14 & 0xf];    std::cout << encode_input << std::endl;    //第二个算法    //最终的    char *c = (char *) malloc(100);    char *f_result = c;    int m_index = 0;    int m_index_ = 1;    int v10 = 0;    int v11 = 0;    int v12 = 0;    for (; m_index < strlen(encode_input); m_index++) {        result(&f_result, key[*(encode_input + m_index) >> 2]);        v10 = 0x10LL * (*(encode_input + m_index) & 3);        if (m_index_ >= strlen(encode_input)) {            result(&f_result, key[v10]);            result(&f_result, 0x3Du);            result(&f_result, 0x3Du);        } else {            result(&f_result, key[v10 | (*(encode_input + m_index_) >> 4)]);            v11 = m_index_ + 1;            v12 = 4LL * (*(encode_input + m_index_) & 0xF);            if (v11 >= strlen(encode_input)) {                result(&f_result, key[v12]);                result(&f_result, 0x3Du);            } else {                result(&f_result, key[v12 | (*(encode_input + v11) >> 6)]);                result(&f_result, key[*(encode_input + v11) & 0x3F]);            }        }        m_index = m_index_ + 2;        m_index_ += 3;    }    std::cout << c << std::endl;    return 0;}