抖音签名算法的逆向杂谈
前言：
我已经来到看雪两年多了，只发过一篇贴子，还不是技术贴。
两年来，我虽然很少在线，但偶尔逛逛也能发现一些有用的文章，解决了我许多疑惑。我今天就把这一周以来研究抖音签名算法的主要心得分享给大家。
初探：
抖音的签名算法在libcms.so中，在JNI_Onload中动态注册jni函数。
算法用ollvm混淆了，主要是流程平坦化，流程混淆和运算替换
as,cp算法：
这部分我参考了https://bbs.pediy.com/thread-226931.htm，通过调试对比，很快的就把最新版的as,cp算法弄出来了。所以这部分没什么心得。
mas算法
这部分我没有找到任何参考文章，是我一步一步调试分析出来得。
先上代码：
#include
#include
#include
unsigned char ARRAY[0x100];
unsigned int KEY[0x20];
unsigned int init = 0;
void dump_mem(const char *mem, int len)
{
for (int i = 0; i < len; ++i)
{
unsigned char c = *(unsigned char *)(mem + i);
const char *fmt = c < 0x10 ? "0x0%X" : "0x%X";
printf(fmt, c);
if ((i + 1) % 16 == 0 && (i + 1) < len)
{
printf("\n");
}
else
{
printf(" ");
}
}
printf("\n");
}
void dump_memToStr(char *str, const char *mem, int len)
{
for (int i = 0; i < len; ++i)
{
unsigned char c = *(unsigned char *)(mem + i);
const char *fmt = c < 0x10 ? "0%x" : "%x";
sprintf(str + i * 2, fmt, c);
}
}
int LoadData(const char *fn, void *mem)
{
FILE *fp = fopen(fn, "rb");
int len = 0;
fseek(fp, 0, SEEK_END);
len = ftell(fp);
rewind(fp);
int rSzie = fread(mem, len, 1, fp);
fclose(fp);
return rSzie;
}
/*
* -----------------------------------------------------------------------------------------------------------------------
* 单个整数处理
*-------------------------------------------------------------------------------------------------------------------------
*/
unsigned int encrypt_dword_0(unsigned int d)
{
unsigned char b[4] = {0};
for (int i = 0; i < 4; ++i)
{
b[i] = *(unsigned char *)((unsigned char *)&d + i);
}
unsigned int ret = b[0];
for (int i = 0; i < 3; ++i)
{
ret = (ret << 4) + b[i + 1];
}
return ret;
}
unsigned int encrypt_dword_1(unsigned int d)
{
unsigned int pre = 0;
unsigned char b[4] = {0};
for (int i = 0; i < 4; ++i)
{
b[i] = *(unsigned char *)((unsigned char *)&d + i);
}
unsigned int v0, v1, v2, v3, v4;
for (int index = 0; index < 4; ++index)
{
switch (index & 0x1)
{
case 0:
v0 = pre << 7;
v1 = b[index] ^ v0;
v2 = pre >> 3;
v3 = v1 ^ v2;
pre = pre ^ v3;
break;
case 1:
v0 = pre << 0xB;
v1 = b[index] ^ v0;
v2 = pre >> 5;
v3 = v1 ^ v2;
v4 = v3 ^ 0xFFFFFFFF;
pre = pre ^ v4;
break;
}
}
unsigned ret = pre & 0x7FFFFFFF;
return ret;
}
unsigned int encrypt_dword_2(unsigned int d)
{
unsigned int pre = 0x4E67C6A7;
unsigned char b[4] = {0};
for (int i = 0; i < 4; ++i)
{
b[i] = *(unsigned char *)((unsigned char *)&d + i);
}
//printf("b0 = %#x, b1 = %#x, b2 = %#x, b3 =%#x\n",b[0],b[1],b[2],b[3]);
for (int index = 0; index < 4; ++index)
{
unsigned int v0 = pre << 5;
unsigned int v1 = v0 + b[index];
unsigned int v2 = pre >> 2;
unsigned int v3 = v1 + v2;
//printf("v0 = %#x, v1 = %#x, v2 = %#x, v3 = %#x",v0,v1,v2,v3);
pre = pre ^ v3;
// printf("pre = %#X\n\n\n",pre);
}
unsigned int ret = pre;
return ret;
}
unsigned int encrypt_dword_3(unsigned int d)
{
unsigned int v1;
int v2;
unsigned int v3;
unsigned int v4;
v1 = *((unsigned char *)ARRAY + (d >> 24));
v2 = *((unsigned char *)ARRAY + (unsigned char)d);
v3 = (*((unsigned char *)ARRAY + ((d >> 16) & 0xFF)) << 16) | (v1 << 24);
v4 = v3 | (*((unsigned char *)ARRAY + ((unsigned short)d >> 8)) << 8);
return (((v4 | v2) << 10) | (v3 >> 22)) ^ ((v4 >> 8) | (v2 << 24)) ^ (v4 | v2) ^ (4 * (v4 | v2) | (v1 >> 6)) ^ (((v4 | v2) << 18) | (v4 >> 14));
}
/*
* -----------------------------------------------------------------------------------------------------------------------
* 处理索引1-16的数据
*-------------------------------------------------------------------------------------------------------------------------
*/
unsigned int rEndian(unsigned int d)
{
unsigned char b[4] = {0};
for (int i = 0; i < 4; ++i)
{
b[i] = *(unsigned char *)((unsigned char *)&d + i);
}
return (b[0] << 24) | (b[1] << 16) | (b[2] << 8) | b[3];
}
unsigned char rBit(unsigned char c)
{
unsigned char tmp = 0;
unsigned char bit[8] = {0};
for (int i = 0; i < 8; ++i)
{
bit[i] = (c >> i) & 0x1;
}
//dump_mem((const char*)&bit, 8);
for (int i = 0; i < 8; ++i)
{
tmp |= (bit[i] << (7 - i)) & 0xFF;
}
return tmp;
}
unsigned int rBit_eachByte(unsigned int d)
{
unsigned char *C = (unsigned char *)&d;
unsigned int ret = 0;
for (int index = 0; index < 4; ++index)
{
ret |= rBit(C[index]) << (8 * index);
}
return ret;
}
void encrypt_dwordArr_0(unsigned int *D)
{
unsigned int tD[4] = {0};
for (int i = 0; i < 4; ++i)
{
tD[i] = rEndian(D[i]);
}
for (int i = 0; i < 32; ++i)
{
tD[i % 4] = encrypt_dword_3(tD[(i + 1) % 4] ^ tD[(i + 2) % 4] ^ tD[(i + 3) % 4] ^ KEY[i]) ^ tD[i % 4];
}
for (int i = 0; i < 4; ++i)
{
D[i] = rEndian(tD[3 - i]);
}
}
void encrypt_dwordArr_1(unsigned int *D)
{
for (int i = 0; i < 4; ++i)
{
D[i] = rBit_eachByte(D[i]) ^ rBit_eachByte(encrypt_dword_0(D[(i + 1) % 4])) ^ rBit_eachByte(encrypt_dword_1(D[(i + 2) %4])) ^ rBit_eachByte(encrypt_dword_2(D[(i + 3) % 4]));
}
}
void encrypt_subBytes(unsigned char *data)
{
encrypt_dwordArr_0((unsigned int *)data);
//dump_mem((const char*)data, 16);
encrypt_dwordArr_1((unsigned int *)data);
//dump_mem((const char*)data, 16);
}
/*
* -----------------------------------------------------------------------------------------------------------------------
* 根据as计算mas
*-------------------------------------------------------------------------------------------------------------------------
*/
unsigned char rFourBit(unsigned char c)
{
return ((c & 0xF) << 4) | ((c >> 4) & 0xF);
}
const char *cal_mas_0(const char *as)
{
unsigned char *mas = (unsigned char *)malloc(27);
memset(mas, 0, 27);
mas[0] = 1;
*(unsigned short *)(mas + 1) = 0x8760; // =(unsigned short)mas
*(unsigned short *)(mas + 3) = 0x0220; // ???,和getuid有关
memcpy(mas + 5, as, 22);
for (int i = 1; i < 27; ++i)
{
mas[i] = rBit(mas[i]);
}
unsigned char *mas_copy = (unsigned char *)malloc(27);
memcpy(mas_copy, mas, 27);
for (int i = 1; i < 17; ++i)
{
mas[i] = mas_copy[1 + 16 - i];
}
encrypt_subBytes(mas + 1);
for (int i = 17; i < 27; ++i)
{
mas[i] = mas_copy[17 + 26 - i];
}
free(mas_copy);
return mas;
}
const char *cal_mas_1(const char *mas)
{
unsigned char *mas_str = (unsigned char *)malloc(27 * 2 + 1);
memset(mas_str, 0, 27 * 2 + 1);
dump_memToStr(mas_str, (const char *)mas, 27);
//printf("%s\n",mas_str);
return mas_str;
}
const char *cal_mas(const char *as)
{
if (!init)
{
LoadData("ARRAY.dat", ARRAY);
LoadData("KEY.dat", KEY);
init = 1;
}
return cal_mas_1(cal_mas_0(as));
}
ollvm对这些算法的保护是很有用的，比如像encrypt_dword_0,encrypt_dword_1,encrypt_dword_2这些算法，如果不加ollvm的情况下，估计一天就能全搞定了，但是加上后，可能就要3天了。
刚开始接触ollvm，看到一大堆分支，有点不知所措。不过经过多次调试后，便发现其实ollvm其实是纸老虎。以encrypt_dword_1为例：
分支，单元块虽多，但是有用的也只有5块（其实就只有黄色的三块是重要的）。
那要怎么才能定位到这几块主要的地方呢？
动态调试？这是不可能的，十分耗时间。
正确方法是视觉排除法加直觉。
放大关键部分
结合两张图，可以看出主要块上面的都是一些凭感觉就可以排除，因为他们太小，基本没什么有用运算。通过视觉就可以排除掉60%以上的块了，然后再辅助直觉就可以排除80%的块，然后就可以把剩下的块标注出来，最后剩下的块中基本都至少包含一种有效运算如异或，移位，求和之类的。
再通过下断点调试，这里不是单步调试，而是直接f9。然后观察这些关键运算的操作数。粗略f9跑几遍，有些出现特别多，而操作数又无明显意义（比如运算都是是一个地址加一个常数）的运算，基本可以确定不是关键的。
在剩下的块中，我们要保证输入数据的每一步变化都在这些运算之中，要保证数据变化在掌控之中。最好截图保存运算前后的数据。
如果数据变化在掌控之中，根据截图就可以总结出算法。如：
如果数据变化不在掌控之中，我们可以先大胆猜测一些中间运算，然后验证下，如果能解决最好，不能解决，那就需要在其它可疑块上下断点。
总之，就是要保证数据的来源和去处在掌控之中。
总结：
逆向ollvm的最好方法是视觉和直觉排除法。
写到后面发现全文没什么有用的东西，就当作闲聊吧。
最后放上一张验证算法正确的图：
原文作者：青史无疆（看雪ID）
原文链接：https://bbs.pediy.com/thread-246360.htm
转载请注明转自看雪论坛。
