前言:
当前兄弟们对“数据结构与算法源码下载软件”可能比较关怀,小伙伴们都需要剖析一些“数据结构与算法源码下载软件”的相关文章。那么小编在网摘上汇集了一些关于“数据结构与算法源码下载软件””的相关内容,希望看官们能喜欢,朋友们快快来学习一下吧!引言
本文主要记录了逆向分析国外某地图APP的坐标系加解密算法的还原过程,从抓包特征开始, 一步一步定位到关键加解密函数。
在加解密函数分析过程中遭遇ARM NEON向量指令集, 不得不使用动态调试定位该指令集处, 但又遭遇反调试,导致加载目标进程直接退出, 之后开始分析反调试过程, 针对性的进行打补丁。
通过动态调试终于拿到ARM NEON向量指令集四轮密钥变换之后保存在内存中的关键密钥,并使用函数参数HOOK方式拿到加密字符串和解密字符串, 这样我在本地将算法还原后可以验证还原的算法是否准确。
在拿到密钥之后我在本地使用C语言进行了算法代码还原, 最后经过验证在本地成功解密出明文坐标信息。
逆向分析思路
我的逆向分析思路概括起来主要包括以下几个过程:
全方位使用软件功能,同时打开Wireshark进行抓包, 等所有功能差不多全部点击完成时, 保存好抓包文件通过分析抓包文件, 整理出一些比较明显未加密的特征,例如: 本文中代表经纬度的关键参数:&longitude=&latitude=利用静态分析工具IDA加载可执行程序, 使用快捷键shift+F12调出字符串查找窗口,搜索上面的关键参数利用IDA的交叉引用功能尽量找到关键参数对应的调用函数位置, 如果无法定位到有效的函数,可以尝试其它参数搜索利用关键参数找到的所有可疑函数记录下来, 第一轮先静态分析, 利用IDA的F5功能快速将汇编代码进行高级语言伪代码转换,提高分析效率。第二轮将筛选出来的高可疑函数使用函数参数HOOK, 通过打印出来的参数内容验证自己的想法。在静态分析中遇到无法从IDA中直接扣代码或晦涩的汇编指令, 使用动态调试进行断点跟踪验证。在本地使用高级语言将分析出来的函数逻辑进行代码组织, 验证流程。前期分析
在经过一段时间的前期反复使用和抓包分析, 最终定位到以下参数很可能是加密后的坐标系信息上传数据包:
通过其它功能接口的使用, 整理出一组关键的频率比较高的特征:&longitude=、&latitude=
在前期尽量能多收集一些关键特征, 经过分析整理后进行优先级排序, 方便为后面的静态分析做准备。
静态分析
使用静态反汇编工具IDA加载软件的二进制程序, 由于程序比较大, 在经过比较长时间的加载分析之后, 使用快捷键shift+F12调出IDA的字符串查找窗口, 输入上面的关键字符串进行搜索查找,最终在庞大的软件中找到该处:
直接双击该字符串,利用IDA的交叉引用功能,可以发现以下函数进行了调用:
函数对应的类名为:NMXXTEAEncrypt,函数名为:testXXTEA
立即到IDA的Functions window窗口进行搜索,发现有以下函数:
看来字符串很可能是通过xxTEA算法进行加解密的, 先了解下XXTEA算法是什么。
XXTEA算法特征如下:
速度快。XXTEA算法经过优化,执行速度很快,可以在现代计算机上每秒进行几十亿次加密。这使其可以应用在对性能要求较高的场景体积小。XXTEA算法只需要包括两个尺寸小的表(每个4K),因此代码实现也非常小巧和紧凑。这使其可以应用在代码空间有限的场景安全性高。尽管简单,但XXTEA具有非常高的安全强度。它采用128位密钥,能够抵御所有已知的密码分析攻击易于实现。XXTEA算法设计简单,易于理解和实现。这使其可以很容易地应用到各种硬件和软件平台开源免费。XXTEA算法是开源的,任何人都可以自由使用,不需要支付授权费用广泛支持。现在大多数平台和编程语言都有XXTEA的实现,使其很容易集成使用加密安全性高。XXTEA采用加密模式可以确保数据的保密性。不同于只提供校验的哈希算法
这里直接双击XXTEA的解密算法xxTeaDecryptString函数, 并利用IDA的F5功能进行高级语言伪代码生成,代码如下:
在上图中, 发现有一个关键的函数调用方法, 名为:sub_4C2408, 双击进入该函数内部, 如图所示:
种种迹象表明, 该函数看起来像是在做算法运算, 而其中包含两个关键子函数:sub_4C2498和sub_4C20E0, 先看第一个,双击进入函数sub_4C2498内部, 如图:
看关键操作,像是Base64的特征,不过里面没有其它函数调用, 像这个纯算法到时候可以直接拿出来使用。
接着进入第二个函数sub_4C20E0内部,如图:
这里看到了一些让人懵圈的东西, 像这种奇怪的指令是没办法直接扣出来使用的, 回到IDA View窗口看看都是些什么指令,如图:
根据查询, 这些指令是ARM NEON向量指令集, 看下ARM NEON向量指令集介绍:
ARM NEON 是 ARM 架构中的一个 SIMD (单指令多数据) 向量处理指令集。它具有以下特点和作用:
提供了128比特的向量寄存器,可以加速多媒体和信号处理运算。支持整数和单精度浮点向量运算,如加、减、乘、除、饱和、打包、解包等。包含矩阵变换和乘法指令,可以加速图像处理。支持多种数据类型:8位整数、16位整数、32位整数、32位浮点数。可以并行进行同一指令操作的向量计算,提升计算性能。编译器优化时可以自动利用NEON指令提升性能,无需人工优化。保持了与ARM标量指令的兼容性,同时使用标量和向量指令。应用场景包括图像处理、音频编解码、3D图形、信号处理、科学计算等。被广泛应用于移动设备、嵌入式系统等对计算性能要求高的场景。
这样的指令集不知道里面在做些什么操作, 只能使用动态调试的方法去看内存了。
处理反调试
在经过一顿操作猛如虎的环境搭建和配置后, 兴奋的附加到目标进程, 但却屡屡收到噩耗,如图所示:
看样子是不想让我附加进程, 回到IDA, 在程序入口处发现以下代码,如图所示:
Ptrace()系统调用被用来实现反调试保护,原理如下:
在目标程序启动初期,调用 ptrace(PT_DENY_ATTACH, 0, 0, 0) 禁止其他进程附加随后再调用 ptrace(PT_TRACE_ME, 0, 0, 0) 对自身进程跟踪如果该调用失败,说明当前进程已经被调试器附加,出现反调试情况如果成功,则一直循环调用 wait() 等待被其他进程跟踪如果 wait() 返回,则同样表示有反调试行为程序可以通过检查 ptrace() 调用的返回值来判断是否出现了反调试情况,并作出相应反应
针对该原理, 我使用了以下代码进行了绕过:
int fake_ptrace(int request,pid_t pid,caddr_t addr,int data){ return 0;}void*(*old_dlsym)(void* handle,const char* symbol);void* my_dlsym(void* handle,const char* symbol){ if(strcmp(symbol,"ptrace") == 0) { return (void*)fake_ptrace; } return old_dlsym(handle,symbol);}%ctor{ @autoreleasepool { MSHookFunction((void*)dlsym,(void*)my_dlsym,(void**)&old_dlsym); }}
大致意思就是利用Hook框架对原ptrace()函数进行挂钩, 然后对该函数进行处理, 让他调用我的假ptrace()函数。
下面终于可以愉快的动态调试了。
动态调试
动态调试的过程跟普通调试方法差不多, 熟练使用单步指令、下断点就行, 以下是从ARM NEON指令集中动态解出密钥:
为了能得到加密函数和解密函数的传参内容, 我使用了类似以下的代码进行了函数参数Hook:
%hook NMXXTEAEncrypt+ (id)xxTeaEncryptString:(id)arg1{id r = %orig();id r1 = arg1;NSLog(@"=========================================================");NSLog(@"NMXXTEAEncrypt::xxTeaEncryptString");NSLog(@"=========================================================");NSLog(@"Encrypt return value = %@", r);NSLog(@"data value = %@", r1);return r;}%end
Hook后的效果非常不错, 软件自动把加密后的字符串和解密后的字符串自动打印出来了,如图:
算法还原
首先还原上面的子函数:sub_4C2408, 还原的代码如下:
void* decrypt_func(const void* data, unsigned int data_length, int key){ int v1; unsigned int v6; void* v7; BYTE* v8; void* v9; signed int v10; int v17; signed int v18; size_t v19; v1 = (int)data; v6 = data_length; v7 = 0; if(v1 && data_length >= 5) { v8 = base64_decode(v1,data_length); v9 = malloc(0x10u); v10 = 3 * (v6 >> 2); if(xxtea_decrypt((unsigned int*)v8, v10/-4, (int)key) == 1) { while(v10 >= 2) { v17 = v10 - 1; v18 = v8[v10-- - 1]; if ( v18 >= 1 ) { v19 = v17 - v18 + 1; v7 = malloc(v19); //*v4 = v19; memcpy(v7, v8, v19); goto LABEL_8; } } v7 = 0; }LABEL_8: free(v8); free(v9); } return v7;}
其次还原子函数sub_4C2498,源码如下:
BYTE* base64_decode(int data, unsigned int data_size){ unsigned int v2; // r6@1 int v3; // r0@1 signed int v4; // r2@1 signed int v5; // r4@1 int v6; // r10@5 size_t v7; // r5@5 BYTE *v8; // r0@11 BYTE *v9; // r8@11 unsigned int v10; // r0@13 unsigned int v11; // r2@13 unsigned int v12; // r10@17 int v13; // r5@17 BYTE *v14; // r8@17 int v15; // r4@17 int v16; // r1@19 int v17; // r11@21 int v18; // t1@22 int v19; // r9@26 signed int v20; // r2@26 signed int v21; // r0@26 BYTE *v22; // r3@26 signed int v23; // r5@27 int v25; // [sp+0h] [bp-34h]@15 int v26; // [sp+4h] [bp-30h]@15 int v27; // [sp+8h] [bp-2Ch]@13 BYTE *v28; // [sp+Ch] [bp-28h]@11 int v29; // [sp+10h] [bp-24h]@1 BYTE *v30; // [sp+14h] [bp-20h]@12 int v31; // [sp+18h] [bp-1Ch]@1 int v32; // [sp+18h] [bp-1Ch]@21 char number_array[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/="; v2 = data_size; v29 = data; v3 = data + data_size; v4 = 1; v5 = 0; v31 = *(BYTE *)(v3 - 3); if ( *(BYTE *)(v3 - 1) == 61 ) { v4 = 2; v5 = 1; } if ( *(BYTE *)(v3 - 2) == 61 ) v5 = v4; v6 = v5; v7 = 3 * (data_size >> 2); if ( *(BYTE *)(v3 - 3) == 61 ) v6 = v5 + 1; switch ( v6 ) { case 0: case 1: v7 += 4; break; case 2: v7 += 3; break; case 3: v7 += 2; break; default: break; } v8 = malloc(v7); v9 = v8; v28 = v8; if ( !v8 ) { puts("No enough memory."); exit(0); } memset(v8, 0, v7); v30 = v9; if ( v6 != v2 ) { v10 = v2 - v6; v27 = v2 - v6; v11 = 0; if ( v31 == 61 ) ++v5; v26 = v5 - v2; v25 = v6 - v2; v30 = v9; do { if ( v11 < v10 ) { v12 = -4; v13 = 0; v14 = (BYTE *)(v29 + v11); v15 = v25 + v11; if ( v25 + v11 > 0xFFFFFFFC ) v12 = v25 + v11; v16 = v26 + v11; if ( v26 + v11 <= 0xFFFFFFFC ) v16 = -4; v17 = -v16; v32 = v11 - v12; do { v18 = *v14++; --v17; v13 = (char)&strrchr(number_array, v18)[-(unsigned int)number_array] | (v13 << 6); } while ( v17 ); v9 = v28; if ( v12 ) { if ( v12 <= 0xFFFFFFFD ) v15 = -3; v19 = -v15; v20 = 16; v21 = v13 << (6 * v12 + 24); v22 = v30; do { v23 = v21 >> v20; v20 -= 8; *v22++ = v23; ++v15; } while ( v15 ); v30 += v19; } v10 = v27; v11 = v32; } } while ( v11 < v10 ); } *v30 = 0; return v9;}
继续还原第二个子函数sub_4C20E0:
signed int xxtea_decrypt(unsigned int *data, signed int data_size, int decrypt_key){ signed int v3; unsigned int v10; int v14; unsigned int v27; signed int v28; unsigned int *v29; int v30; int v31; unsigned int v32; int v33; int v34; unsigned int v35; int v36; unsigned int *v37; v3 = data_size; v10 = *data; v37 = data; v14 = decrypt_key; if(v3 < 2) { if(v3 >= -1) { return 0; } v36 = -v3; v27 = 2654435769 * (52 / -v3) + 3041712726; if ( v27 != 0 ) { v28 = v3; v29 = v37; v30 = ~v28; v31 = v14; do { v32 = v29[v30]; v33 = (v27 >> 2) & 3; v34 = v36; do { v35 = v37[v34 - 2]; v10 = v32 - (((16 * v35 ^ (v10 >> 3)) + ((v35 >> 5) ^ 4 * v10)) ^ ((*(unsigned long*)(v31 + 4 * ((v34 - 1) & 3 ^ v33)) ^ v35) + (v10 ^ v27))); v37[v34-- - 1] = v10; v32 = v35; } while (v34 >= 2); v29 = v37; v30 = ~v28; v10 = *v37 - ((((v37[~v28] >> 5) ^ 4 * v10) + (16 * v37[~v28] ^ (v10 >> 3))) ^ ((*(unsigned long*)(v31 + 4 * v33) ^ v37[~v28]) + (v10 ^ v27))); v27 += 1640531527; *v37 = v10; } while ( v27 ); } } return 1;}
到此,关键解密函数全部还原出来了, 加密算法与此类似,不再赘述, 最后的代码结构如下:
在main函数中,我需要将动态解出来的密钥还有参数传给函数进行加解密,如图:
结果验证
将上面的C代码编译后执行, 加密字符串成功被解密了,如图:
标签: #数据结构与算法源码下载软件