标题: 逆向工程中面对并理解编译器对除法的优化(2)

创建: 2020-07-07 12:58 更新: 2024-11-06 14:30 链接: 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 ) >> 32 ) / 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 ) >> 32 >> 5 ) hex( ( 0xdd67c8a7 * xxx ) >> 0x25 )

进一步等价于:

hex( xxx // 0x25 )

注意，">> 0x25"与"// 0x25"中都出现了0x25，这只是巧合，不要瞎联想。

这两个Python3表达式为什么会等价？

参看:

http://www.masmforum.com/archive2012/6717_MagicNumber64.zip

将32位有符号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

有本书可以看看:

《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 ) >> 32 ) / 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是除数，有如下关系:

a // b = ( 0xdd67c8a7 * a ) >> 32 >> 5 => ( 0xdd67c8a7 * a ) = pow(2,32+5) * a // b => b = pow(2,32+5) // 0xdd67c8a7 + 1

在Python3中执行:

pow(2,32+5) // 0xdd67c8a7 + 1 = 37 pow(2,32+19) // 0x8a86bc61 + 1 = 968897 pow(2,32+29) // 0x4a925fdf + 1 = 1843042529

用此办法可静态获取除法优化前的除数，比F5结果好。

2024-11-05

假设在IDA中肉眼怀疑有除法优化，不是所有神密常量都能放狗命中，想纯静态还原出除数，从而得到人类可读的最简除法表达式。此需求在逆向工程中时有碰到，以前写过两篇技术文章，当时IDA F5尚不能还原除数，最近发现IDA F5已能从除法优化中还原除数，伪代码或许有瑕疵，但除数还原正确。若发现IDA F5未能还原除数，可尝试手工还原之，本文从实用角度举例演示。

除法优化汇编模板1/2

/ * 有符号除法 / mov ?,magic_0 imul sar ?,magic_1 / * 此处随位数而变化，依次对应16/32/64位除法 / shr ?,15/31/63 add

/ * 无符号除法 / mov ?,magic_0 mul shr ?,magic_1

一般情况

16位除数 pow(2,16+magic_1) // magic_0 + 1 32位除数 pow(2,32+magic_1) // magic_0 + 1 64位除数 pow(2,64+magic_1) // magic_0 + 1

有符号

pow(2,16+1) // 0x4925 + 1 = 7 pow(2,32+2) // 0x92492493 + 1 = 7 pow(2,64+1) // 0x4924924924924925 + 1 = 7

pow(2,16+7) // 0x8081 + 1 = 255 pow(2,32+7) // 0x80808081 + 1 = 255 pow(2,64+7) // 0x8080808080808081 + 1 = 255

无符号

pow(2,32+7) // 0x80808081 + 1 = 255 pow(2,64+7) // 0x8080808080808081 + 1 = 255

除法优化汇编模板3

/ * 无符号除法 / mov ?,magic_0 .if !carry mul .endif shr ?,magic_1

一般情况

16位除数 pow(2,16+magic_1) // magic_0 32位除数 pow(2,32+magic_1) // magic_0 64位除数 pow(2,64+magic_1) // magic_0

无符号

pow(2,16+2) // 0x9249 = 7 pow(2,32+2) // 0x92492492 = 7 pow(2,64+2) // 0x9249249249249249 = 7

无符号

pow(2,16+7) // 0x8081 + 1 = 255

除数为16位无符号255时，出现汇编模板3，但从两个magic反推除数时，需要加1，出现例外。

除数最后是否加1，不太固定，未进行严格数学推导，上面只是部分经验结论。肯定有算法从两个magic反推除数，是否加1应该有确定性结论，只不过我数学渣，未深究而已。一般逆向工程中，根据模板套经验结论足矣，能动态调试时还可以验证。

某次逆向工程看到:

mov r8, 8080808080808081h mul r8 shr rdx, 7

与除法优化汇编模板2接近，疑似64位无符号除法优化，尝试还原64位无符号除数:

pow(2,64+magic_1) // magic_0 + 1 pow(2,64+7) // 0x8080808080808081 + 1 = 255

即，上述汇编代码实际执行:

X // 255

可用如下Python脚本快速反推除数:

python3 get_divisor.py 16 0x4925 1

python3 get_divisor.py 32 0x92492493 2

python3 get_divisor.py 64 0x4924924924924925 1

7 python3 get_divisor.py 16 0x8081 7

python3 get_divisor.py 32 0x80808081 7

python3 get_divisor.py 64 0x8080808080808081 7

255 python3 get_divisor.py 16 0x9249 2

python3 get_divisor.py 32 0x92492492 2

python3 get_divisor.py 64 0x9249249249249249 2

7

import sys

def main ( argv ) :

while True :
    if len( argv ) < 4 :
        print( "Usage: %s <N> <magic_0> <magic_1>" % argv[0] )
        break
    N   = int( argv[1], 0 )
    m   = int( argv[2], 0 )
    l   = int( argv[3], 0 )
    d   = pow( 2, N+l ) // m + 1
    n   = pow( 2, N ) - 1
    if ( m * n // pow( 2, N+l ) ) != ( n // d ) :
        d  -= 1
        assert ( m * n // pow( 2, N+l ) ) == ( n // d )
    print( "%u" % d )
    break

if "main" == name : main( sys.argv )

2024-11-05

《逆向工程中面对并理解编译器对除法的优化》 https://scz.617.cn/misc/201603311247.txt

《逆向工程中面对并理解编译器对除法的优化(2)》 https://scz.617.cn/misc/202007071258.txt