演算法逆向1——簡單演算法逆向

01-24

本文原創作者：icq5f7a075d
本文屬i春秋原創獎勵計劃，未經許可禁止轉載！
如文中出現錯誤，歡迎指出，感激不盡！
文中的所有程序請在虛擬機中運行。

Music起~

「啊門啊前一棵葡萄樹，啊嫩啊嫩綠地剛發芽，蝸牛背著那重重地殼呀，一步一步地往上爬~」

上周分析勒索病毒(GlobeImposter)，筆者感覺自己演算法的逆向能力很弱，於是找了些題目練手。本文逆向程序主要來源於《加密與解密實戰攻略》，演算法將用Python/C++實現。

既然有了演算法逆向1，自然會有2、3、4......葉問說「我要打十個！」，筆者說「我要寫十篇！」，甭管行不行，先立Flag！

1. 簡單的演算法逆向

預計時間：2h

1.1. 定位關鍵位置

先隨便輸入，彈出了錯誤提示：

搜索字元串：Invalid！此時已經找到了關鍵位置。

上下翻找一番，0x00404167就是關鍵跳轉，如果是crackme，那麼直接把這裡修改為jmp就可以了。而我們要進行演算法逆向，就要追蹤分析ebx和esi這兩個值怎麼來的。

1.2. 演算法逆向

往上回溯，ebx的值來自於下圖，過程還是比較簡單，對輸入name字元串進行計算，得到一個值，以這個值為編號，在表0x4050B8中取值：

往上回溯，esi的值來自於此，也比較簡單對輸入密碼字元串進行計算：

演算法逆向源碼（python）：

calc_table=[0x19791126,0x19791007,0x11261979,0x10071979, 0x12345678,0x9abcdef0,0x12123434,0x78787878, 0xccc6ccc6,0xcc00cc00,0xffefefff,0xddcc5555, 0x67678787,0xcececbcc,0x778899ab,0x44337766]def calc_name(name): sum_name=0 for i in range(0,len(name)): sum_name=sum_name+i*ord(name) #print hex(sum_name) calc_name1=(sum_name&0xFFFF)+((((2*len(name)+0x63)&0xFFFF)<<0x10)) #print hex(calc_name1) calc_name2=calc_name1&0xF return calc_name2def calc_pass(password): str_pass="0"+password edx=0 for i in range(0,len(str_pass)): edx=edx*2 edx=edx+edx*4 edx=edx+ord(str_pass)-0x30 return edxname_in = raw_input("Input your name:")pass_in=raw_input("Input your pass:")print hex(calc_table[calc_name(name_in)])print hex(calc_pass(pass_in))

2. 解方程演算法逆向

預計時間：4h

本程序雖然叫解方程演算法，但是解方程演算法只是本程序演算法中的一小部分。

2.1. 定位關鍵演算法

運行程序，隨便輸入name和serial，點擊check沒有任何反應。直接拖入IDA，程序的函數很少，一眼就可以看到，我們要逆向的演算法在DialogFunc和sub_401141中：

DialogFunc中流程很簡單，檢測到Check按鈕點擊事件就會進入如下的處理過程：

第一次調用GetDlgItemTextA獲取輸入的Serial，第二次調用GetDlgItemTextA獲取輸入的Name，對Name的長度進行判斷，當Name長度大於5並小於32，則調用sub_401141進行計算，計算結果正確則彈出正確對話框，否則，重新等待用戶輸入。

要分析的演算法處於sub_401141，第一次參數是Name的長度，第二次參數是Serial的長度，0x403084存放輸入的Serial，0x403044存放輸入的Name。

2.2. 演算法分析

（本小節中的代碼盡量遵循彙編語句，所以比較凌亂，下小節有整合後的源碼）

首先是一個先循環，倒序取Name中的字元進行計算，結果存放在dword_4030C4中：

這段代碼有循環移位操作，需要使用自定義函數實現，在下文中會對移位指令進行介紹，

本部分源碼(C++)：

unsigned ebx=0x1; unsigned d_4030c4=0x0; char cl; for(int i=len_name;i>0;){ i--; unsigned edx=name; edx=edx ^ ebx; edx=edx * ebx; ebx+=0x5; d_4030c4=d_4030c4 ^ edx; d_4030c4=leftrot(d_4030c4,5); } d_4030c4=0-d_4030c4-1;//這裡必須要減去1 d_4030c4=right_rot(d_4030c4,len_name); char b_4030c8="";

對Name的計算完畢之後，對Serial進行計算，但是計算Serial計算是將其分為三部分:"-"字元、"-"字元前的字元，"-"字元後的字元，下圖是計算是否存在"-"字元，並取"-"字元前的字元：

這部分源碼（C++）：

for(int eax=0;eax!=len_serial;){ char edx_c=serial[eax]; eax++; if(edx_c=="-"){//Serial中必須有"-"字元 char al=(char)eax; b_4030c8=--al; eax=len_serial;} } if(b_4030c8!=0){ cl=""; cl= b_4030c8; } else{ return -1; }

"-"字元前的字元的字元ASCII區間(0x3F,0x5B)

這部分源碼（C++）：

int cl_i=(int)cl; for(;cl_i!=0;) { cl_i=cl_i-1; char edx_c=serial[cl_i]; if(edx_c<=0x3F || edx_c>=0x5B) { return -1;} }

計算』-』前的字元，判斷得到的值和最初計算Name得到的值是否相同，且Serial中』-』後的字元個數是3

這部分源碼（C++）：

cl=b_4030c8; cl_i=(int)cl; int ebx_2=0; for(;cl_i!=0;) { cl_i=cl_i-1; char edx_c=serial[cl_i]; ebx_2*=0x1A; edx_c=serial[cl_i]; edx_c=edx_c-"x41"; ebx_2=ebx_2+int(edx_c); } if(ebx_2!=d_4030c4) {return -1;} int eax=len_serial; eax=(eax/0x100)*0x100+(eax%0x100-(int)b_4030c8)%0x100; if(eax!=4){ return -1; }

計算』-』後的3個字元

這部分源碼（C++）：

int j=(int)b_4030c8; char b_4030c9=serial[j+1]; char b_4030ca=serial[j+2]; char b_4030cb=serial[j+3]; eax=(int)b_4030c9; eax*=3; unsigned d_4030cc=eax; eax=0; ebx=(int)b_4030c9; ebx*=7; unsigned d_4030d0=eax-ebx; unsigned d_4030d4=(int)b_4030c9; d_4030cc=d_4030cc-(int)b_4030ca; d_4030d0=(int)b_4030ca*2+d_4030d0; d_4030d4=d_4030d4+(int)b_4030ca; d_4030cc=d_4030cc+(int)b_4030cb*5; d_4030d0=d_4030d0+(int)b_4030cb*7; d_4030d4=d_4030d4-(int)b_4030cb*2; if(d_4030cc==0x204 && d_4030d0==0x19 &&d_4030d4==0x0D) { printf("OK! "); return 0; }

2.3. 源碼整合 源碼（C++）

#include <iostream>#include <string.h>using namespace std;//elfbin:0x8501675cchar* str_n="elfbin";//test unsigned len_n=strlen(str_n);char* str_s="YWSCVFH-RAC";//testunsigned len_s=strlen(str_s);unsigned leftrot(unsigned a,int n) //RCL{ unsigned b; b=(a >> (32 - n)) | (a << n); return b;}unsigned rightrot(unsigned a,int n){ unsigned b; b=(a << (32 - n)) | (a >> n); return b;}int main(){ //計算name，得到32位數值； unsigned f_n=0x0; char cl; int i=len_n; int j=1; for(;i>0;){ i--; f_n^=(str_n^j)*j; j+=5; f_n=leftrot(f_n,5); } f_n=0-f_n-1;//這裡必須要減去1 ,取反 f_n=rightrot(f_n,len_n); //Serial中必須有"-"字元，第一個字元不能是"-"字元，"-"字元前的字元應該是大寫或@ char l_s=""; for(i=0;i!=len_s;i){ if(str_s=="-"){ l_s=(char)i; i=len_s; } else i++; } if(l_s==0){ return -1; } for(i=(int)l_s;i!=0;) { i--; if(str_s<=0x3F || str_s>=0x5B) {return -1;} } //計算Serial, 倒序取"-"字元前的字元，其在倒序字元串中的索引*在字母表中的位置求和 int f_s=0; for(i=(int)l_s;i!=0;) { i--; f_s*=0x1A;//=26 f_s=f_s+int(str_s)-"x41";//int(serial)-"x41",在字母表中的位置 } if(f_s!=f_n) // 計算Serial得到的值等於計算Name得到的值 {;return -1;} //serial "-"字元後面還有3個字元 if((len_s-(int)l_s)!=4){ return -1; } //計算Serial後三位 unsigned A,B,C; char a=str_s[(int)l_s+1]; char b=str_s[(int)l_s+2]; char c=str_s[(int)l_s+3]; A=(int)a*3; B=-(int)a*7; C=(int)a; A=A-(int)b; B=(int)b*2+B; C=C+(int)b; A=A+(int)c*5; B=B+(int)c*7; C=C-(int)c*2; //0x204=a*3-b+c*5 //0x19=a*7+b*2+c*7 //0x0D=a+b-c*2 if(A==0x204 && B==0x19 &&C==0x0D) { printf("OK! "); return 0; } printf("%x,%x,%x ",A,B,C); return -1;}

2.4. 註冊機

本程序雖然叫解方程演算法，實際上一共有三部分演算法：計算Name，計算Serial中前部分，計算Serial最後三位元組：

計算Name和計算Serial的演算法如下：

計算Serial最後三位元組才是真正的解方程演算法，方程組如下：

3a-b+5c=0x204

7a+2b+7c=0x19

a+b-2c=0x0D

註冊機源碼（C++)

#include <iostream>#include <string.h>using namespace std;unsigned leftrot(unsigned a,int n) { unsigned b; b=(a >> (32 - n)) | (a << n); return b;}unsigned rightrot(unsigned a,int n){ unsigned b; b=(a << (32 - n)) | (a >> n); return b;}int main(){ char str_n[30];//test char str_s[30]; unsigned len_n; cout<<"Name:"; cin>>str_n; len_n=strlen(str_n); //計算name，得到32位數值； unsigned f_n=0x0; char cl; int i=len_n; int j=1; for(;i>0;){ i--; f_n^=(str_n^j)*j; j+=5; f_n=leftrot(f_n,5); } f_n=0-f_n-1; f_n=rightrot(f_n,len_n); //計算str_s for(i=0;f_n>0x1a;i++){ str_s=(char)(f_n%0x1a+0x41); f_n/=0x1a; } str_s=(char)(f_n+0x41); str_s[i+1]="-"; str_s[i+2]="R"; str_s[i+3]="A"; str_s[i+4]="C"; cout<<"Serial:"<<str_s<<endl; return 0;}

2.5. 移位運算

算是本節的彩蛋吧，在本演算法逆向過程中，移位指令花費了筆者大量時間，於是就總結出了下面這些東西：

夜深人靜，未完待續.....續篇：演算法逆向2--CRC32