首页
论坛
课程
招聘
一道算法题
2021-1-11 23:51 4388

一道算法题

2021-1-11 23:51
4388

0x0 写在前面

本题为看雪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{3Q412b
    Interceptor.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两个函数

    • sub_FCB4

    • 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;
    }

    结果验证



    [2022夏季班]《安卓高级研修班(网课)》月薪三万班招生中~

    最后于 2021-1-11 23:55 被GitRoy编辑 ,原因:
    上传的附件:
    收藏
    点赞1
    打赏
    分享
    最新回复 (1)
    雪    币: 1061
    活跃值: 活跃值 (1035)
    能力值: ( LV2,RANK:10 )
    在线值:
    发帖
    回帖
    粉丝
    ADR66 活跃值 2021-4-28 06:38
    2
    0
    为啥这里sub_F270要加1呢?这是根据什么原理。
    游客
    登录 | 注册 方可回帖
    返回