标题: 逆向工程中面对并理解编译器对除法的优化(2) 创建: 2020-07-07 12:58 更新: 链接: https://scz.617.cn/misc/202007071258.txt 逆向工程中遭遇如下代码，输入short型变量xxx，经某种数学变换得到变量yyy: -------------------------------------------------------------------------- 00007FFFF3A7DE35 0F B7 B4 24 98 00 00 00 movzx esi, [rsp+xxx] ; Move with Zero-Extend 00007FFFF3A7DE3D B8 A7 C8 67 DD mov eax, 0DD67C8A7h 00007FFFF3A7DE42 F7 EE imul esi ; Signed Multiply 00007FFFF3A7DE44 89 F1 mov ecx, esi 00007FFFF3A7DE46 C1 F9 1F sar ecx, 1Fh ; Shift Arithmetic Right 00007FFFF3A7DE49 01 F2 add edx, esi ; Add 00007FFFF3A7DE4B C1 FA 05 sar edx, 5 ; Shift Arithmetic Right 00007FFFF3A7DE4E 29 CA sub edx, ecx ; Integer Subtraction 00007FFFF3A7DE50 6B DA 25 imul ebx, edx, 25h ; Signed Multiply 00007FFFF3A7DE53 F7 DB neg ebx ; Two's Complement Negation 00007FFFF3A7DE55 01 F3 add ebx, esi ; Add 00007FFFF3A7DE57 48 63 CB movsxd rcx, ebx ; Move with Sign-Extend Doubleword 00007FFFF3A7DE5A 48 89 4C 24 48 mov [rsp+yyy], rcx -------------------------------------------------------------------------- 这段代码的F5结果并不会提供更有价值的信息，比如我的Hex-Rays显示: yyy = xxx - 0x25 * (((signed int)(xxx + (0xFFFFFFFFDD67C8A7LL * xxx >> 32)) >> 5) - ((signed int)xxx >> 31)); 这个神鬼莫测的F5结果，还不如直接看汇编代码。 你猜，yyy的最简表达式是什么？是这个: yyy = xxx % 0x25 即xxx模37。这事慢慢说，先提个小问题。如下"8字节宽"代码: mov esi, 0xffff mov eax, 0xdd67c8a7 imul esi imul之后edx等于多少？不许在调试器中实际执行。当时截图在微博上提这个问，渣 浪进行图片OCR后不知识别出什么敏感词，然后限流了。要说是位数，可我写的不是 "sixty four"啊，活久见。 很久没有折腾ASM编程，逆水行舟不进则退，最初误以为答案是0xdd66，因为: 0xdd67c8a7 * 0xffff = 0xdd66eb3f3759 但实际结果是: (gdb) i r edx eax edx 0xffffdd67 -8857 eax 0xeb3f3759 -348178599 后来bluerust、hume分别指出问题所在，imul是有符号相乘，此时0xdd67c8a7实际是 个负数。在Python3中执行: hex( 0x10000000000000000 - ( 0x100000000 - 0xdd67c8a7 ) * 0xffff ) 得到: 0xffffdd67eb3f3759 这个64位数与edx:eax相符。再挖个imul的小坑，如下代码: mov esi, 0xffffffff mov eax, 0xdd67c8a7 imul esi imul之后edx等于多少？ (gdb) i r edx eax edx 0x0 0 eax 0x22983759 580400985 在Python3中执行: hex( ( 0x100000000 - 0xdd67c8a7 ) * ( 0x100000000 - 0xffffffff ) ) 得到: 0x22983759 -------------------------------------------------------------------------- 00007FFFF3A7DE35 0F B7 B4 24 98 00 00 00 movzx esi, [rsp+xxx] ; Move with Zero-Extend 00007FFFF3A7DE3D B8 A7 C8 67 DD mov eax, 0DD67C8A7h 00007FFFF3A7DE42 F7 EE imul esi ; Signed Multiply 00007FFFF3A7DE44 89 F1 mov ecx, esi /* * 这是算术右移，不是逻辑右移。 * * ecx由于源自short型变量，其结果恒为0。 */ 00007FFFF3A7DE46 C1 F9 1F sar ecx, 1Fh ; Shift Arithmetic Right /* * edx = hex( ( 0xdd67c8a7 * xxx ) >> 0x20 ) */ 00007FFFF3A7DE49 01 F2 add edx, esi ; Add /* * 这是算术右移，不是逻辑右移。 */ 00007FFFF3A7DE4B C1 FA 05 sar edx, 5 ; Shift Arithmetic Right /* * edx减0 */ 00007FFFF3A7DE4E 29 CA sub edx, ecx ; Integer Subtraction -------------------------------------------------------------------------- 相当于在Python3中执行: hex( ( 0xdd67c8a7 * xxx ) >> 0x25 ) 进一步等价于: hex( xxx // 0x25 ) 注意，">> 0x25"与"// 0x25"中都出现了0x25，这只是巧合，不要瞎联想。 这两个Python3表达式为什么会等价？ 将X除以37优化成乘法运算，其中一种方案如下: -------------------------------------------------------------------------- mov ecx,X mov eax,0DD67C8A7h imul ecx add edx,ecx sar edx,05h shr ecx,31 add edx,ecx ; quotient now in edx -------------------------------------------------------------------------- 之前写过一篇: 《逆向工程中面对并理解编译器对除法的优化》 https://scz.617.cn/misc/201603311247.txt 推荐过一本书: 《Hacker's Delight 2nd Edition》 有兴趣深究者可以看看，此处不展开。 -------------------------------------------------------------------------- 00007FFFF3A7DE35 0F B7 B4 24 98 00 00 00 movzx esi, [rsp+xxx] ; Move with Zero-Extend 00007FFFF3A7DE3D B8 A7 C8 67 DD mov eax, 0DD67C8A7h 00007FFFF3A7DE42 F7 EE imul esi ; Signed Multiply 00007FFFF3A7DE44 89 F1 mov ecx, esi /* * 这是算术右移，不是逻辑右移。 * * ecx由于源自short型变量，其结果恒为0。 */ 00007FFFF3A7DE46 C1 F9 1F sar ecx, 1Fh ; Shift Arithmetic Right /* * edx = hex( ( 0xdd67c8a7 * xxx ) >> 0x20 ) */ 00007FFFF3A7DE49 01 F2 add edx, esi ; Add /* * 这是算术右移，不是逻辑右移。 */ 00007FFFF3A7DE4B C1 FA 05 sar edx, 5 ; Shift Arithmetic Right /* * edx减0 */ 00007FFFF3A7DE4E 29 CA sub edx, ecx ; Integer Subtraction /* * 有符号相乘 */ 00007FFFF3A7DE50 6B DA 25 imul ebx, edx, 25h ; Signed Multiply /* * 求负 */ 00007FFFF3A7DE53 F7 DB neg ebx ; Two's Complement Negation 00007FFFF3A7DE55 01 F3 add ebx, esi ; Add 00007FFFF3A7DE57 48 63 CB movsxd rcx, ebx ; Move with Sign-Extend Doubleword 00007FFFF3A7DE5A 48 89 4C 24 48 mov [rsp+yyy], rcx -------------------------------------------------------------------------- 相当于在Python3中执行: hex( xxx - ( ( 0xdd67c8a7 * xxx ) >> 0x25 ) * 0x25 ) 进一步等价于: hex( xxx - ( xxx // 0x25 ) * 0x25 ) hex( xxx % 0x25 ) 参看: https://github.com/benaadams/Primes https://github.com/benaadams/Primes/blob/master/Program.cs Program.cs中列举了一批用于除法优化的神密常量，比如: new PrimeInfo(37, 0xdd67c8a7, 5) new PrimeInfo(968897, 0x8a86bc61, 19) new PrimeInfo(1843042529, 0x4a925fdf, 29) 将X除以968897优化成乘法运算，其中一种方案如下: -------------------------------------------------------------------------- mov ecx,X mov eax,08A86BC61h imul ecx add edx,ecx sar edx,013h shr ecx,31 add edx,ecx ; quotient now in edx -------------------------------------------------------------------------- 提一个通用问题，假设在IDA中肉眼怀疑有对除法的优化，不考虑Google搜索神密常 量，不考虑动态调试获取商后反向求出除数，有无办法从神密常量(0xdd67c8a7,5)着 手进行数学推导得到除数37，从而得到人性化的最简表达式。 假设a是被除数、b是除数，有如下关系: ( 0xdd67c8a7 * a ) >> 0x20 >> 5 = a // b => ( 0xdd67c8a7 * a ) = pow(2,0x20+5) * a // b => b = pow(2,0x20+5) // 0xdd67c8a7 + 1 在Python3中执行: pow(2,0x20+5) // 0xdd67c8a7 + 1 = 37 pow(2,0x20+19) // 0x8a86bc61 + 1 = 968897 pow(2,0x20+29) // 0x4a925fdf + 1 = 1843042529 用此办法可以静态获取除法优化前的除数，绝对比F5结果好。