about 9 years ago
Reversing 250, 原題目 https://github.com/csie217/ctf/raw/master/codegate2014pre/clone_technique.exe
PE 檔，執行的話會一直分出新的 process 執行自己。分析後發現
- 執行時需要 3 個參數 a1, a2, counter，如果沒有的話有預設值 (a1=0xA8276BFA,a2=0x92F837ED,counter=1)
- 參數 a1, a2 傳入一個 decrypt 函式，會試著解密一個固定的字串 (0x00407030)
- a1 符合某個條件時，不會 fork 而是直接回傳一個值；否則依底下的方式 fork，結束後回傳 0。
- 接下來會 fork 出新的 process 執行自己，會等 child 結束再開下一個，最多 400-counter 次 (如果 child 回傳 0 就提前結束) 。傳入 child 的參數是 a1, a2 和上一個 child 的回傳值運算過的結果、還有 counter-1
因為只要有任何一個 child 回傳 0，就會全部結束掉了；但如果 child 的回傳值不是 0，意思是這個 child 沒有再往下分枝。另外每往下一層 counter 都會減 1。所以最差情況是: 前 399-counter 次的 child 回傳值非 0，最後一次是 0。這樣每層最多 401 個 process，乘上總層數就大約只有 160000 次。
但 process 數可能因為太多開不起來，而且太慢。因此我們重新寫了一遍，所做的事情完全一樣只是不 fork 而只是遞迴函式。另外原本的程式中有個計算 a^n 的函式 pow(a,n) 是直接用迴圈乘 n 次所以太慢了，我們把它換成了快速幂。還有重新寫成 C 時要注意，原本的 imul, div 這些都會直接 overflow，要注意變數是 signed 還是 unsigned。
重新寫成 C code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const char *str="\x0F\x8E\x9E\x39\x3D\x5E\x3F\xA8"\
"\x7A\x68\x0C\x3D\x8B\xAD\xC5\xD0"\
"\x7B\x09\x34\xB6\xA3\xA0\x3E\x67\x5D\xD6";
inline int ROL(int a,int b){
return (a<<b)|((unsigned)a>>(32-b));
}
char* decode(const char *a1,int a2,int a3){
int i;
int size;
char *v8;
size = strlen(a1);
v8 = (char*)malloc(size+1);
memset(v8,0,size);
for(i = 0;i < (size - 1);i += 2){
v8[i] = a2 ^ a1[i];
a2 = ROL(a2,5)^0x2f;
if(!a1[i + 1]){
break;
}
v8[i + 1] = a3 ^ a1[i + 1];
a3 = ((unsigned char)a2)^ROL(a3,11);
}
return v8;
}
inline int pow(int a,unsigned int b){
if(b==0) return 1;
int d = pow(a,b/2);
if(b%2){
return d*d*a;
}else{
return d*d;
}
}
int calc(int a1,int a2,int ct){
printf("%s\n",decode(str,a1,a2));
a1^=0xB72AF098u;
a2 = (a1*a2)^a2;
int v1 = 29*a1+7*pow(a1,2);
int v6 = pow(v1^a2,((unsigned)v1%2)+5);
if((unsigned int)a1<=0xD0000000u){
int ret;
do{
if(ct>400) return 0;
ct++;
ret = calc(v1,v6,ct);
v1 = ret;
v6 = pow(ret^v6,ret%30);
}while(ret);
return 0;
}else{
return (13*((unsigned)v1/27))^0x1f2a990d;
}
}
int main(){
calc(0xA8276BFA,0x92F837ED,1);
return 0;
}
執行後解出 key
$ ./clone | strings -n 10
And Now His Watch is Ended
