记一次Instagram算法提取

无名侠

这次分析的APP为instagram，我发布了几篇算法分析文章，每一篇文章的侧重点不同，本篇文章主要采用“提取”方法。

其它算法文章:
IDA F5 利用法:http://www.52pojie.cn/thread-576532-1-1.html
本地调用法:http://www.52pojie.cn/thread-537460-1-1.html
等效算法替代法:http://www.52pojie.cn/thread-491745-1-1.html
ARM汇编模拟/替代法:http://www.52pojie.cn/thread-507815-1-1.html
静态分析法:http://www.52pojie.cn/thread-490628-1-1.html



Instagram 的数据包首部都会附加一串校验码:
"signed_body=586752602ab1663ecea796f4637ce5e7acadc32194d8d47d2a8eabbd5e76c6bf.{"_csrftoken":"nduLj1VObNrpyQ5u4RZ4BqS8Mj2oT6dH","source_type":"3","_uid":"4342149846","_uuid":"c3e595be-3663-4786-a63e-7a84fdf3300d","caption":"why+not+show?","upload_id":"1483625101909","device":{"manufacturer":"samsung","model":"GT-P5210","android_version":17,"android_release":"4.2.2"},"edits":{"crop_original_size":[640.0,480.0],"crop_center":[0.0,-0.0],"crop_zoom":1.3333334},"extra":{"source_width":640,"source_height":480}}&ig_sig_key_version=4"
我通过对APK进行反向分析，最终把算法代码定位在:libstrings.so->Java_com_instagram_strings_StringBridge_getSignatureString

通过观察可知，主要加密流程在sub_9BC、sub_A7C、sub_A88这个三个函数。Scrambler::getString是另外一个SO中的导出函数，但是参数固定，可知结果固定，动态调试的时候可直接获取。
三个主要函数可以判断是OpenSSL中的函数，OpenSSL有很多种密码算法，小弟才疏学浅，无法通过常量值或流程特征来判断算法，只有通过逆向手段了。

这三个函数都是极大极大的函数，抛开sub_9BC为初始化函数不管，另外两个函数的代码量也相当惊人，如果采用常规手段可能会相当费力。


既然没有现成可用的代码，那就想办法吧。


办法有很多：
1、qemu-arm 模拟器 模拟执行算法
2、Android设备上运行 TCP调用
3、提取算法

方案1，我了解qemu，学习嵌入qemu可能会花费我很多时间。
方案2，简单、效率低、不适合服务器。
方案3，效率高，方便。

因此，我选择方案3。何谓提取？ 提取在我看来是指从ELF从提取代码到内存并进行相关修复后调用目标函数。 方案3有一个致命弱点，ELF中代码的指令集必须要为X86，然而幸运的是，该APP官网有X86专版。

实际上Android X86版本都是可以模拟执行ARM指令的，为什么还有一个专版？这只是该APP为提升用户体验而采取的一种手段，通过反汇编libstrings.so可知，大部分算法都用到了SSE和MMX指令集。

如何把代码数据装载到内存中？
暴力膜蛤法！有知识的朋友第一个想法便是解析ELF，然后就心生畏惧了。 我采用了一个比较简单的方案，我将整个ELF读入到内存中，不做任何解析工作。定义相关函数指针并以硬编码形式指向函数在内存中的位置。

char * elf = loadFile("libstrings.so");
..........
init1 _init1 = (init1)&elf[0xB50];
updata _updata = (updata)&elf[0x1320];
finalEn _final = (finalEn)&elf[0x1360];
........

定位后，这些函数都可以直接调用了，用IDA分析一下参数即可。

细节上的一些坑:
1.SSE指令集的指令所访问的内存地址必须以16字节对齐
2.__stack_chk_guard是一个外部符号，需要为其分配内存
3.中文数据编码问题

每一个坑都有很多东西要讲的，我只是抛砖引玉的提一下。

坑1：
我以前没有使用过SSE指令集，在我们要分析的SO中，数学运算都是用该指令集实现的。上午调试的时候就不停的报异常，异常是因为访问的内存地址不是16字节对齐的，也就是说 Addr mod 16 != 0 就会报异常。
SO中的代码是一个整体，ESP都是相对的。 那么我们只需要在调用该SO前修正ESP即可。
修正方法:
设 a = 异常代码处ESP mod 16
调用某函数前执行:sub esp,a
调用后平衡堆栈:add esp,a
前提条件: 调用某函数前的esp是16字节对齐的。
为了避免麻烦，我们重新申请一个堆栈供算法使用。

[C++] 纯文本查看 复制代码

newesp = (char *)_aligned_malloc(4096 * 10, 16);;//分配栈，按照16字节对齐。
// 切换栈
_asm
{
		mov old_esp,esp //备份esp
		mov esp,newesp
}

切换堆栈后，就可以对堆栈进行第二次修正，也就是前面提到的修正方法。

完整过程调用：

[C++] 纯文本查看 复制代码

	newesp = (char *)_aligned_malloc(4096 * 10, 16);;//分配栈，按照16字节对齐。
	// 切换栈
	_asm
	{
		mov old_esp,esp
		mov esp,newesp
	}
	_asm sub esp, 4;
	_init1((char *)ctx, key, strlen(key));
	_asm add esp, 4;

	_updata(ctx, data1, strlen(data1));

	elf[0x6040] = 0x80;

	_asm sub esp, 0x8;
	_final(ctx, result1);
	_asm add esp, 0x8;

	_asm mov esp, old_esp;

elf[0x6040] = 0x80; 是一段全局变量赋值代码，我不清楚该全局变量为何被清0了，实际上应该是有值的，所以我重新赋值。

坑2：
stack check 栈检查机制，GCC在编译的时候可以选择添加或者关闭。该机制是检查堆栈是否被破坏的一种机制。__stack_chk_guard是一个外部符号，也就是外部模块中的内存地址，我们需要重申请一个即可，是什么值并不重要！
int  * __stack_chk_guard_ptr = (int *)&elf[0x5FC4];
*__stack_chk_guard_ptr = (int)new int;
偏移都是通过IDA静态分析得出。

坑3:中文编码
转UTF8再调用加密函数即可。


为防止恶意利用，我不提供相关算法的代码。核心代码已经透露在文章中了。

dying

[Python] 纯文本查看 复制代码

  def generateSignature(self, data):
        try:
            parsedData = urllib.parse.quote(data)
        except AttributeError:
            parsedData = urllib.quote(data)
        return 'ig_sig_key_version=' + self.SIG_KEY_VERSION + '&signed_body=' + hmac.new(self.IG_SIG_KEY.encode('utf-8'), data.encode('utf-8'), hashlib.sha256).hexdigest() + '.' + parsedData

xiaosuobjsd

膜拜大神

琅琊孔明

我是不是发现了了不得的东西

常飞

太感谢楼主了，吾爱已经很久没有这么好的教程了。

n0elle

很棒 nice

KelvinLaw

无名大神又出新的教程，赶紧来学习一下

cr4ck

Mark学习,此文深不可测,感谢无名侠的分享

qwe191903

我可不可以转载？让更多人看见

Shadow_hy

好东西 看看