逆向分析sign算法

admin

101095
文章

87
评论

2022年9月19日22:26:30评论35 views字数 8320阅读27分44秒阅读模式

逆向分析sign算法

本文为看雪论坛优秀文章

看雪论坛作者ID：飞翔的猫咪

题目: 分析出KanxueSign函数的算法(题目出自看雪高研班2021年11月份作业)

还原的代码在附件中，编译:g++ main.cpp base64.c

1.分析:

纯c算法的逆向，有很多的ollvm,所以这道题完成以后可以更加熟悉处理ollvm的程序。

2.答案:

经过初步分析算法的输入为MainActivity类的firstInstallTime,packageCodePath,randomLong,startTime四个成员变量，与MainActivity.randomLong无关。

固定住输入好分析:

老方法,使用frida固定住这四个变量的输入方便记录分析，我这里四个变量的取值为:

cls.startTime.value = 0x17d472e9806;cls.firstInstallTime.value = 0x17d41d64983;cls.randomLong.value = 0x49536c10125ac000;cls.packageCodePath.value = "/data/app/com.kanxue.ollvm_ndk_11-7sJSh-MLUIRVBOWzGqFjjw==/base.apk";

经过算法的输出为36b0d7a02b934a38fffd51f0be37c661fdf6896e81d82c4dde65fb194268e9cd00c301110281011c028100c302810071007100c300bd0190023e014a01a30281022a00a8020400be014a01900156015602e2023e010b022a011101a3010b02c702c7012c012d01c10208019c0147012c0294023a01d100a900a70249008601ca007202b60135009e02d601e001e002a2028b028b00c3012b028101c100be014a0281007101a3ahryb3qMnhySa3mLbQeOakeQb3ySaK==

三段结果:

结果分为三段，三段由不同的算法处理，由sprintf组装，具体的逻辑在sub_12AE4中

1、第一段结果为:36b0d7a02b934a38fffd51f0be37c661fdf6896e81d82c4dde65fb194268e9cd,64个字节。

2、第二段结果为00c301110281011c028100c302810071007100c300bd0190023e014a01a30281022a00a8020400be014a01900156015602e2023e010b022a011101a3010b02c702c7012c012d01c10208019c0147012c0294023a01d100a900a70249008601ca007202b60135009e02d601e001e002a2028b028b00c3012b028101c100be014a0281007101a3

3、第三段结果为ahryb3qMnhySa3mLbQeOakeQb3ySaK==，可以看出这是一段疑似base64结果

第一段算法:

再分析过程中发现sha256的常数:0x6a09e667,0xbb67ae85,实现函数为sub_1B1E8,但这个实现是个sha256的变种，输入的字符串有时为64个字节未做padding的字符串，通过nop掉ollvm的控制块，修复真实块的关系，以及还原ollvm指令替换，得到的sub_1B1E8函数的代码片段为:

v231 = *v594;    v232 = *v588;    v233 = *v590;    v234 = (unsigned int)*v591;    v235 = *v592;    v587 = a2_arg + 1;    v654 = a2_arg + 1;    v236 = a2_arg[1] << 24;    v237 = (*v654 ^ 0xFF00FFFF) & *v654;    v238 = ((*v654 << 8) ^ 0xFF00FF00) & (*v654 << 8);    v657 = HIBYTE(a2_arg[1]);    v658 = v237;    v659 = v657 | (v658 >> 8);    v660 = v238;    v239 = v659 | v236;    v656 = v239 | v660;    v655 = v656;    v581 = v656;    sub_26300(v231, v661, v232, v589, v233, v234, v235, v593, v656 + 1899447441); //2     v240 = *v593;    v241 = *v594;    v242 = *v589;    v243 = *v590;    v244 = (unsigned int)*v591;    v654 = a2_arg + 2;    v245 = a2_arg[2] << 24;    v246 = a2_arg[2] & 0xFF0000;    v247 = (a2_arg[2] << 8) & 0xFF0000;    v657 = HIBYTE(a2_arg[2]);    v658 = v246;    v659 = v657 | (v658 >> 8);    v660 = v247;    v656 = v659 | v245 | v660;    v655 = v656;    v582 = v656;    sub_26300(v240, v241, v661, v588, v242, v243, v244, v592, v656 - 1245643825); //3     v248 = *v592;    v249 = *v593;    v250 = *v594;    v251 = *v588;    v252 = *v589;    v253 = *v590;    v587 = a2_arg + 3;    v654 = a2_arg + 3;    v254 = a2_arg[3] << 24;    v255 = a2_arg[3] & 0xFF0000;    v256 = (a2_arg[3] << 8) & 0xFF0000;    v657 = HIBYTE(a2_arg[3]);    v658 = v255;    v659 = v657 | (v658 >> 8);    v660 = v256;    v257 = v659 | v254;    v656 = v257 | v660;    v655 = v656;    v578 = v656;    sub_26300(v248, v249, v250, &v661, v251, v252, v253, v591, v656 - 373957723); //4

像这样的代码有64处，和sha256的处理吻合。

sub_26300我这里用了trace的方式还原，代码片段如下:

...w15 = 0x324F4353;w16 = 0xA7EA7AC2;w13 = w4 >> 0xB;w14 = w4 << 0x15;w19 = w15 & (~w13);w21 = w13 & (~w15);w22 = w15 & (~w14);w14 = w14 & (~w15);w19 = w19 | w21;w15 = w16 & (~w6);w21 = w22 | w14;w22 = w16 & (~w5);w5 = w5 & (~w16);w14 = w6 & (~w16);w23 = w15 | w14;w5 = w22 | w5;w17 = w4 >> 0x19 | w4 << (32 - 0x19);w19 = w19 ^ w21;w5 = w23 ^ (~w5);w20 = *w7_ptr;w21 = w19 & (~w17);w19 = w17 & (~w19);...

其实里边的指令是指令替换，一大堆的操作最后可能就是做了一个异或，只不过当时没看注意。

第一段算法的运算流程如下:

1、startTime和firstInstallTime组合成字符串"17d472e980617d41d64983",经过运算填充成64个字节的值为:

逆向分析sign算法

2、将这个值送入sub_1B1E8中运算并保存下来，然后这个填充成64字节的数组每个元素再^0x6a,再送入sub_1B1E8中运算。

3、接下来用sha256的padding来处理packageCodePath,不过和标准的sha256的padding区别在于最后的长度会多0x200,在维基百科中查到的padding算法:
逆向分析sign算法
padding算法还原如下:

void padding(){  size_t str_len = APK_PATH.length();  size = this->RoundUp64(str_len + 1 + 8);  data = new unsigned char[size];  memcpy(data, APK_PATH.c_str(), str_len);  order_of_0x80 = str_len + 1;  data[str_len] = 0x80;  size_t padding_len = str_len * 8 + 0x200;  data[size - 1] = padding_len;  data[size - 2] = padding_len >> 8;  data[size - 3] = padding_len >> 16;  data[size - 4] = padding_len >> 24;  data[size - 5] = padding_len >> 32;  data[size - 6] = padding_len >> 40;  data[size - 7] = padding_len >> 48;  data[size - 8] = padding_len >> 56;}

4、padding完了以后的字符串会送入sub_1B1E8运算。

5、上一步的结果再填充为sha256的64个字节，送入sub_1B1E8运算得到最终结果。

第二段算法的运算流程如下:

第二段算法的还原代码为:

void second_part(){    for (int i = 0; i < APK_PATH.length(); i++)    {        unsigned int index = (unsigned int)(random_long % 5) + (APK_PATH.c_str()[i]);        unsigned int v = dword_5C008[index];        printf("%.4x", v);    }}

其中dword_5C008为642个int长度的数组，元素列表为:

unsigned int dword_5C008[] = {    0x16a, 0x151, 0xd7, 0x134, 0x196, 0x229, 0x67, 0xfa,    0x269, 0x272, 0x226, 0x122, 0xec, 0x2b5, 0x216, 0x214,    0x179, 0x9f, 0x277, 0x194, 0xf4, 0x2ad, 0xa0, 0x210,    0x26d, 0x1b9, 0x257, 0x2c9, 0xe9, 0xa1, 0x16c, 0x15f,    0x99, 0x2e1, 0xbf, 0x1c6, 0xb4, 0x21d, 0xde, 0x16d,    0xc4, 0x8b, 0x25d, 0x108, 0x11b, 0x12c, 0x14a, 0xc3,    0x195, 0x2c7, 0xca, 0x207, 0x206, 0x1b8, 0x1a0, 0x12d,    0xce, 0x93, 0x2df, 0x205, 0xaa, 0x28b, 0x9b, 0x1df,    0x288, 0x200, 0x86, 0x169, 0x211, 0x297, 0x2d6, 0x135,    0x223, 0xa9, 0x208, 0x1a2, 0x23a, 0x294, 0x1ad, 0x1ca,    0x1e2, 0x102, 0xa7, 0x19c, 0x2b1, 0x1d1, 0x249, 0x72,    0xd4, 0x1dd, 0x173, 0xb5, 0x17a, 0xe1, 0xa5, 0x10b,    0x2d9, 0x281, 0x12b, 0xbd, 0x111, 0xbe, 0x1a9, 0x105,    0x147, 0x82, 0x1e0, 0x1a3, 0x156, 0x23e, 0x22a, 0x190,    0x71, 0x9e, 0x16b, 0x1c1, 0x11c, 0x204, 0x2e2, 0x2a2,    0xa8, 0x14b, 0x2b6, 0xc9, 0x239, 0x116, 0x2a7, 0xd1,    0x273, 0x6c, 0x21c, 0xe2, 0xeb, 0x2d0, 0x1db, 0x6b,    0x232, 0xef, 0x85, 0x13f, 0xf5, 0x9d, 0xf8, 0x267,    0x1f2, 0x75, 0x246, 0x1d8, 0x13b, 0x2d7, 0x2ac, 0xd5,    0x187, 0x29c, 0x176, 0x131, 0x28d, 0x91, 0xb6, 0x114,    0x2d8, 0x275, 0x11a, 0x26c, 0x110, 0x2aa, 0x1c3, 0x19f,    0x1a8, 0x279, 0x2de, 0x15d, 0x2db, 0x6a, 0x230, 0x68,    0x178, 0x2bd, 0x217, 0x146, 0x186, 0x1e6, 0x1b1, 0x143,    0x2e3, 0x2af, 0x8e, 0x1d0, 0xac, 0x1de, 0x260, 0x81,    0x193, 0x266, 0x231, 0x1d2, 0xba, 0x240, 0x18e, 0x7e,    0xc1, 0x1f1, 0x1fe, 0x2a3, 0x250, 0x13a, 0x24a, 0x64,    0x29a, 0x24b, 0x2ca, 0x188, 0xfd, 0x103, 0x100, 0x1d9,    0x9a, 0x1f3, 0x182, 0x7d, 0xda, 0xdf, 0x11f, 0x27e,    0x1b4, 0x215, 0x8f, 0x263, 0x192, 0x150, 0x17d, 0x2a4,    0x154, 0x23b, 0x14f, 0x12f, 0x29f, 0x2ba, 0x237, 0x2bc,    0x126, 0x1fd, 0x168, 0x2c5, 0x254, 0x2e0, 0x1c9, 0x201,    0x172, 0x140, 0x138, 0xe0, 0xb1, 0xbb, 0x2dd, 0x19e,    0x1e7, 0x160, 0x13e, 0x7a, 0x1cb, 0x28c, 0x7f, 0xf9,    0x14e, 0x2b8, 0x101, 0x1ea, 0x1d7, 0x1f7, 0x276, 0x1c2,    0x8a, 0x2cf, 0x238, 0xdc, 0x2ae, 0x94, 0x157, 0x175,    0x21f, 0x2c2, 0xab, 0x130, 0x104, 0xfb, 0x24d, 0x222,    0x221, 0x18c, 0x1fa, 0x1fc, 0x1b5, 0x87, 0x2be, 0x1af,    0x1b7, 0xc2, 0x22b, 0x10a, 0x19b, 0x121, 0x198, 0x148,    0x1f6, 0x280, 0x132, 0x17b, 0x1bb, 0xcd, 0x20e, 0x2bb,    0xb7, 0x1cc, 0x244, 0x2a6, 0x264, 0x1ef, 0x251, 0x76,    0x171, 0x2dc, 0x236, 0x25f, 0x159, 0x1a4, 0x1f4, 0x118,    0x17e, 0x106, 0x115, 0x262, 0x1a6, 0x185, 0x1f5, 0x29b,    0x29e, 0x13d, 0x9c, 0x224, 0xc5, 0x219, 0x25c, 0x149,    0x88, 0x137, 0x2a9, 0xb2, 0x139, 0x24e, 0x183, 0x235,    0x1fb, 0x15b, 0xc7, 0x1c5, 0xd9, 0x26b, 0x7b, 0x1e4,    0xf7, 0x2c6, 0x22f, 0x16f, 0x2d2, 0xfc, 0x177, 0x1cd,    0x241, 0x2ce, 0x1be, 0x1bc, 0x7c, 0x1e3, 0x258, 0x2b0,    0xae, 0x125, 0xa6, 0x2d1, 0x1b6, 0xcf, 0x278, 0x18d,    0x155, 0x1ab, 0x1f8, 0x270, 0x1d5, 0x2c1, 0x1b0, 0x27f,    0x74, 0x1ae, 0xe7, 0x2a5, 0xd0, 0x98, 0x141, 0x289,    0x1f0, 0x1aa, 0x1bf, 0x2cd, 0x1c8, 0x2b7, 0x296, 0x299,    0x6f, 0x17c, 0xd8, 0x77, 0x124, 0xe8, 0x18f, 0x26e,    0x2bf, 0x1dc, 0x21a, 0x209, 0x20a, 0x18a, 0x274, 0x1ac,    0x28a, 0x109, 0x1ee, 0x73, 0x2b3, 0x136, 0x234, 0x1da,    0x10d, 0x27a, 0x2d4, 0x22e, 0x2c4, 0x83, 0x261, 0x18b,    0x20f, 0x167, 0x1e5, 0x1f9, 0x252, 0x1e8, 0x89, 0x25e,    0x23c, 0x129, 0xb3, 0xbc, 0x284, 0x112, 0x11d, 0x22d,    0x2d3, 0x15c, 0x10f, 0xd2, 0xf2, 0x15e, 0x298, 0x28e,    0x2cc, 0xea, 0x120, 0x145, 0xf3, 0x202, 0x197, 0x181,    0x2c3, 0x170, 0x1a7, 0x78, 0xe6, 0xc0, 0xf1, 0x1ff,    0x295, 0x213, 0xc8, 0x164, 0x22c, 0x10c, 0x1d4, 0xcb,    0x165, 0x1ec, 0xcc, 0x282, 0x1bd, 0xb0, 0x24f, 0x80,    0xa2, 0x29d, 0x2d5, 0x14d, 0xe4, 0x16e, 0x158, 0x152,    0xc6, 0x6d, 0xd3, 0x212, 0x184, 0x153, 0x180, 0x66,    0x228, 0x220, 0x259, 0x2ab, 0x70, 0x27d, 0x2b9, 0x291,    0xed, 0xaf, 0x127, 0x255, 0x123, 0x90, 0x293, 0xf0,    0x271, 0x247, 0x162, 0x27c, 0x203, 0x119, 0x218, 0xfe,    0x1c0, 0x1c4, 0x163, 0x243, 0x14c, 0x1d6, 0x1e1, 0x65,    0x12a, 0x2da, 0x292, 0xf6, 0x11e, 0x20d, 0x25b, 0x144,    0xe5, 0xa3, 0x8c, 0x283, 0x1cf, 0x96, 0x191, 0x2a0,    0x225, 0x199, 0x242, 0x92, 0x107, 0x21e, 0x166, 0x8d,    0x290, 0x24c, 0x285, 0x287, 0x113, 0x133, 0x13c, 0x10e,    0x17f, 0x1eb, 0xe3, 0x233, 0x26f, 0x265, 0x26a, 0xd6,    0x19d, 0x15a, 0xad, 0x256, 0x1a1, 0x23f, 0x6e, 0x1a5,    0x245, 0x2c8, 0x1ed, 0x20c, 0xdd, 0x2b4, 0x21b, 0x1c7,    0xa4, 0x97, 0x1b3, 0x2cb, 0x174, 0x1b2, 0x27b, 0x189,    0x20b, 0x23d, 0x142, 0x28f, 0xdb, 0x69, 0x79, 0x2b2,    0x1ce, 0x12e, 0x2a8, 0x268, 0x95, 0x25a, 0x227, 0xb8,    0x253, 0xee, 0xb9, 0x19a, 0x1ba, 0x161, 0x1d3, 0x2c0,    0x128, 0x2a1, 0xff, 0x117, 0x1e9, 0x84, 0x286, 0x248,    0x0, 0x0};

当时看到这么大的数组，就怀疑是不是哪个算法的常量，我没看出来，但可以确定的是确实是个常量数组。

第三段算法:

是一个改了字典表的base64,字典表如下:
逆向分析sign算法
也就是"0123456789-_abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ="

还原代码如下:

void third_part(){    BYTE buf[1024] = {0};    base64_encode((const BYTE *)startTime_firstInstallTime.c_str(), buf, startTime_firstInstallTime.length(), 1);    printf("%s",buf);}