魔数除法算法逆向
寻找指定代码
本文任务为对样本dll库指定文件偏移处代码进行逆向分析。
首先从任务要求中可知，指定算法在文件偏移0x5FACE处
由于在windows环境下，我们使用Stud_PE程序辅助分析PE头所附带的各种信息：image_base为0x10700000 ;text段的文件偏移与RVA的差值为 0x52009-0x51009=0x1000
又从区段图中可知，文件偏移0x5FACE处仍在text段中，因此其偏移量不变，则逆向代码对应 VA=image_base+file_offset-offset=0x10700000+0x5FACE-0x1000=0x1075EACE
得出代码VA以后，我们可以继续使用Stud_PE查看一下对应文件偏移处的机器码，方便后续验证VA有效性
接下来使用IDA打开样本dll文件，并找到对应的VA处代码，将其与上图进行对照，发现机器码无误，VA计算正确
逆向分析算法
找到对应函数位置以后，我们正式开始进行代码逆向分析
windows下_fastcall调用约定中，前两个参数分别对应寄存器ecx、edx，因此我们设此处参数为arg(第一处cmp后将原始参数存入了栈中)，此处比较后返回的代码串为
if(arg>=3&&arg<0xd){
return &table1[arg*2]
}虽然汇编代码中的查表处为*8，但是推测此处表类型为int（4字节），有（ecx*8）/bit=(arg*2)/int
解决完函数开头的条件分支以后，我们继续对右侧代码进行分析：整理出第一个汇编序列如下
mov eax,ecx ;eax=arg
cdq ;edx为arg符号位
mov edi,eax ;edi=arg
xor edi,edx ;根据arg正负判断是否取反
sub edi,edx ;根据arg正负判断是否+1概括为 int a=abs(arg),此处我们为了简便，将每次的长串计算结果存储到一个变量中
继续向下查看整理出第二个汇编序列
mov esi,ecx ;esi=arg
shr esi,1Fh ;esi=(arg)>>31
sub esi,80000000h ;esi=(arg)>>31-0x80000000
mov eax,esi
xor edx,edx
div edi ;esi / a且edx为余数
sub esi,edx ;等价于esi-esi%a
dec esi ; 再-1
mov [esp+18h+var_8],1Fh;直接给局部变量赋值 概括为 int b=(arg>>31)-0x80000000-((arg>>31)-0x80000000))-1；int c=31;
继续向下查看整理出第三个汇编序列
mov eax,80000000h
div esi
mov ebp,eax ;ebp =0x80000000/b = d
mov ebx,80000000h
imul eax,esi ;d*b
sub ebx,eax ; 0x80000000-(0x80000000/b)*b=0x80000000%b
mov eax,80000000h
div edi
mov ecx.eax ; ecx=0x80000000/a=f
mov edx,80000000h
imul eax,edi
sub edx,eax;同理,此处也是模运算概括为 int d=0x80000000/b;int e=0x80000000%b;int f=0x80000000/a;int g=0x80000000%a;
变量初值部分逆向完毕，继续向下分析循环体部分，观察跳转部分可以得知，先进行内部操作，再判断循环条件，这应该是do_while循环
我们提炼出循环终止的条件，可以看到几个寄存器代表的值没有改变，因此有循环体如下
do{
}while((d<a-g) || (d==a-g)&&!e)//注意这里是先jnb跳转后，再用jz+test来判断跳转的，不可以直接写成>=解决大循环体后，我们针对循环体内部操作进行逆向，此处的汇编代码较为简单，我们可以直接概括为C语言
e*=2;d*=2;++c;
if(e>=b){++d;e-=b;}
g*=2;f*=2;
if(g>=a){++f;g-=a;}
解决完循环体以后，我们来逆向该算法的最后一部分
首先可以看到向全局变量dword_1079F090处存入了f+1;然后将原始参数放入ecx中，测试其是否为负数；
若为负，执行取反操作；否则顺序执行最后一段汇编，全局变量dword_1079F090地址作为返回值，并将c-32的值存入另一个全局变量中
概括如下,最终返回值符合定义offset
g1 = arg+1;
if(arg<0)g1=-g1;
int *result=&g1;
g2=c-32;
return result;
最终我们完整分析出来的C代码为
int *magic_number(int arg)
{
if ( arg >= 3 && arg < 0xD )
return &table1[2 * a1];
int a = abs32(arg);
int c = 31;
int b = (arg >> 31) - 0x80000000 - ((arg >> 31) - 0x80000000) % a - 1;
int d = 0x80000000 / b;
int e = 0x80000000 % b;
int f = 0x80000000 / a;
int g = 0x80000000 % a;
do
{
e *= 2;
d *= 2;
++c;
if ( e >= b )
{
++d;
e -= b;
}
g *= 2;
f *= 2;
if ( g >= a )
{
++f;
g -= a;
}
}
while ( d < a - g || d == a - g && !e );
g1 = f + 1;
if (arg<0)
g1 = -g1;
result = &g1;
g2 = c - 32;
return result;
}数学模型构建
本节我们进行刚才逆向出来的算法的数学模型构建；重定义变量含义如下：
| arg (ecx) | 真实除数 | divisor (d) |
|---|---|---|
| a (edi) | 除数的绝对值 | abs_d |
| b(esi) | 辅助除数 | aux_divisor |
| c(esp+8+c) | 移位计数器，初始 31 | shift_counter |
| d(ebp) | 2^31 / aux_divisor 的商 |
aux_quot |
| e(ebx) | 2^31 / aux_divisor 的余数 |
aux_rem |
| f (ecx) | 2^31 / abs_d 的商（魔数种子） |
magic_quot |
| g(edx) | 2^31 / abs_d 的余数 |
magic_rem |
| g1 | 最终魔数 | magic_number (M) |
| g2 | 最终移位量 | shift_amount (s) |
函数初始的直接返回应该对应着快速查表，获取小除数的magic_number并直接返回。除此以外才是magic_number的真正生成过程，我们据此进行构建
首先明确目标，我们希望找到一个整数 M 和一个整数 s，使得对于任意整数 x，以下等式成立：（其中d为除数，M为魔数，s为移位量）
如果我们把 1/d 表示成一个定长的小数，比如 1/d ≈ Q / 2^N，其中 Q 是整数，那么 x/d ≈ (x * Q) >> N
那么寻找魔数与移位量的问题就被转换为求Q和N的问题
该算法的思路是：从 N = 31 开始，计算 Q = floor(2^31 / d)。但由于这是下取整，2^31 / d 总是略大于 Q。Q乘以 x 后，误差会被放大，导致结果偶尔比真实商小 1。为了消除这个误差，我们需要提高 N（增加精度），让 Q 更精确地逼近 2^N / d。
因此我们在循环中维护计数器 cc（初始 31），并引入辅助除数 b：
所以初始商和余数分别为：
其中 d,e 对应辅助除数 b；f,g 对应绝对值 a。
汇编代码里的 do ... while 循环，就是在逐位地执行 二进制长除法 ：
在循环体执行 之前 ，始终满足：
循环体每次执行的操作将其视为长除法的左移过程：
由 (1)，2^c=d⋅b+e
下一步 c′=c+1，则需表示 2^(c+1)=2d⋅b+2e
若 2e≥b**，说明 2e 中可再分出一个 b，因此商多 1，余数减去 b。这正好给出：
同理，f′,g′ 更新后也满足
循环每迭代一次，c 递增 1，商和余数始终对应 2^c/b 和 2^c/a。
循环结束以后，由于我们最终的除法估算通过下界得到，所以不可避免的出现商小1的情况，因此我们在魔数上+1，向上进行舍入的修正
