該題目是一道算法題，算法涉及二次HASH加密及驗證。本人通過分析，認為只有用暴力枚舉的方法才能得到認證碼。經過長時間跟蹤，通過研究加密算法，分析出了通過枚舉的方式猜解得到認證碼的方法。本文將先對該題進行二進制逆向分析，然后進行算法破解分析。
直接將exe拖入IDA中，然后查找字符串Your code 和Wrong code
找到的每處所在的函數都按F2設置一個斷點：
選擇local win32 debugger，然后點擊開始按鈕進行調試：
這時候程序中斷在我們設置的斷點處：
上圖中，如果界面顯示的是匯編代碼，直接按一下F5就切換到了偽C代碼里了。
上面的代碼具體是干什么的，我們暫時不去關心，這時按F9讓程序繼續執行，然后輸入認證碼，隨便輸入一串字符就好，輸長一點，回車之后到達了我們之前下斷的wrong code這里，IDA反編譯的偽C代碼如下：
#!c
int __cdecl sub_431970(int a1, int a2)
{
memset(&v4, 0xCCu, 0x108u); //這里memset是我肉眼識別出函數功能后，做的標記，
v6 = strlen(secret[0]);// secret[0] 一個內存中固定的字符串
v5 = a2;
for ( i = 0; i < 0x10; i += 4 )
{
v7 = 0;
for ( j = i; j < i + 4; ++j )
{
for ( k = 0; ; ++k )
{
v2 = strlen(secret[0]);
if ( k >= v2 )
break;
if ( secret[0][k] == *(_BYTE *)(j + a1) ) //a1 由b@@[email protected]@[email protected]@@X轉換得到
{
v7 <<= 6;
v7 += k;
break;
}
}
}
*(_BYTE *)v5 = v7 >> 16;
*(_BYTE *)(v5 + 1) = BYTE1(v7);
*(_BYTE *)(v5 + 2) = v7;
v5 += 3;
}
return sub_42FDC0();
}
通過閱讀上面的代碼，以及跟蹤分析，首先發現字符串a1是把我們輸入的認證碼依次替換掉b@@[email protected]@[email protected]@@X中的@得到的。另外字符串secret[0]是固定的值為：R9Ly6NoJvsIPnWhETYtHe4Sdl+MbGujaZpk102wKCr7/ODg5zXAFqQfxBicV3m8U
通過查看內存值，便一目了然：
通過分析算法發現他的HASH加密算法如下：
把a1字符串每4個一組，如果字符a1[i]是字符串secret[0]里的字符，那么
#!c
V7=0
Hash= v7<<6+k //k是a1[i]在字符串secret[0]里的下標。
如果a1[i+1]依然滿足條件
那么hash= hash<<6+k；依次進行，經過4個字符后 V7從0開始 再hash后面四個字符。
把最終得到的4組hash值以16進制形式存入內存中，每組HASH得到一個3字節的數據，4組完成后共得到12字節數據。
這里隨便輸入的認證碼，本次HASH運算完，得到的12字節數據如下：
然后第一次HASH結束。
在函數尾部下斷點，F9 一次，再F8后來到了 程序最開始的函數中，也就是第一次我們斷下的函數里：
繼續按F8，進入了下面的函數：
#!c
int __cdecl sub_431E10(int a1)
{
memset(&v2, 0xCCu, 0x114u);
v9 = a1;
v8 = strlen(a1);
strlen(secret[0]) = strlen(secret[0]);
if ( v8 != 12 ) 這里檢查我們上面得到的HASH后的內容是否是12字節
{
sub_43019E("Wrong code!\n");
sub_4302C0(1u);
}
for ( i = 0; i < v8; ++i )
{
v5 = 0;
for ( j = 0; j < strlen(secret[0]); ++j )
{
if ( secret[0][j] == *(_BYTE *)(i + v9) ) //這里檢查上面HASH后的每一個字節對應的字符是否在
//字符串secret[0]里
{
v5 = 1;
break;
}
}
if ( !v5 )
{
sub_43019E("Wrong code!\n"); //如果不是 就掛了。
sub_4302C0(1u);
}
}
v3 = malloc(16);
memset(v3, 0, 16);
sub_430045(v9, v3);
sub_42F3F2(v3);
return sub_42FDC0();
}
如果上面認證全部通過，按F9后，會進入HASH加密的函數：
這個時候需要進行加密的就是上面得到的第一次HASH加密后的12字節數據。
對這12字節加密，每4個一組，共3組，每組得到3字節數據，這樣第二次HASH后就得到了9字節的數據。按F9后到達這里：
#!c
int __cdecl sub_431CA0(int a1)
{
memset(&v2, 0xCCu, 0xF0u);
v6 = a1;
v5 = strlen(a1);
if ( v5 != 9 ) //首先判斷第二次HASH后的字節長度是否為9，不是就錯了。
{
sub_43019E("Wrong code!\n");
sub_4302C0(1u);
}
for ( i = 0; i < v5; ++i )
{
if ( (signed int)*(_BYTE *)(i + v6) < 48 || (signed int)*(_BYTE *)(i + v6) > 57 ) //檢查第二次HASH后的//每個字節是否都為數字 //字符
{
sub_43019E("Wrong code!\n");
sub_4302C0(1u);
}
}
for ( i = 0; i < v5; ++i )
{
for ( j = i + 1; j < v5; ++j )
{
if ( *(_BYTE *)(i + v6) == *(_BYTE *)(j + v6) ) //檢查第二次HASH后的每個字節是否彼此重復。
{
sub_43019E("Wrong code!\n");
sub_4302C0(1u);
}
}
}
sub_42F1D1(v6); //如果上面都通過了 ，就到達了勝利的彼岸了！
return sub_42FDC0();
}
以上就是整個二進制算法的逆向過程，這里我們搞清楚了他的加密算法，下面就是嘗試破解認證碼了。
針對第一部分HASH算法，我計劃是從R9Ly6NoJvsIPnWhETYtHe4Sdl+MbGujaZpk102wKCr7/ODg5zXAFqQfxBicV3m8U里任意選取兩個（根據需要也可能是1個）字符分別填充到b@@t [email protected] @[email protected] n@@X，并分組進行HASH加密，再驗證HASH結果是否滿足條件，如果滿足條件，那么就保存一下選取的字符以及HASH后的密文。
具體算法如下：
#!c
char m2[17]="b@@[email protected]@[email protected]@@X",*p,*q;
int in1=0,in2=0,in3=0,in4=0;
q=m2;
get(q,0,1,2); //分組取hash 參數分別為字符串 序號 m2里需要填充的字符坐標
q+=4;
get(q,1,1,0);
q+=4;
get(q,2,0,2);
q+=4;
get(q,3,1,2); //共4組，到這里infos就得到了所有滿足第一次HASH結果的可能的值
針對第二次HASH加密，我們把get()函數獲得的所有滿足條件的密文字符串進行組合，然后對每組字符串再次嘗試hash加密，把得到的結果進行檢查是否每個字符都是0-9內并且互不重復，把滿足條件的結果記錄下來。
最后完整破解認證碼的代碼如下：
#!c
#include <stdio.h>
#include <string.h>
#include <windows.h>
char m1[70]="R9Ly6NoJvsIPnWhETYtHe4Sdl+MbGujaZpk102wKCr7/ODg5zXAFqQfxBicV3m8U";
char sz[11]="0123456789";
struct info
{
char *hash; //存放第一次hash后的值
char *mw; //存放hash前明文
};
info infos[4][1000];
long hash(char *s)
{
int j=0,v7=0,k=0;
v7 = 0;
for ( j = 0; j < 4; ++j )
{
for ( k = 0; ; ++k )
{
if ( k >= strlen(m1))
break;
if ( m1[k] == s[j] )
{
v7 <<= 6;
v7 += k;
break;
}
}
}
return v7;
}
int check(char a,char *s) //檢查字符a是否在字符串s里
{
int i=0;
for (i=0;i<strlen(s);i++)
{
if (s[i]==a)
{
return 1;
}
}
return 0;
}
int check2(char *s) //第二次hash 每次hash后檢查一下 是否在0-9間，同時檢查一下是否有重復數字
{
int v7=hash(s);
char *v5;
v5=(char *)malloc(4);
v5[0] = char(v7 >> 16);
v5[1] = char(v7 >> 8);
v5[2] = char(v7);
v5[3]='\0';
if ( !check(v5[0],sz) || !check(v5[1],sz) || !check(v5[2],sz) )
{
return 0;
}
else if(v5[0]==v5[1]||v5[0]==v5[2]||v5[1]==v5[2])
{
return 0;
}
else
return 1;
}
void get(char *s,int index,int in1,int in2) //暴力枚舉 獲得滿足第一次hash結果的 hash密文 和明文
{
char *p,*q,char ms[3];
char *v5;
int i0=0,i=0,j=0,v7=0,k=0,num=0;
p=q=s;
for (i0=0;i0<64;i0++)
{
p[in1]=m1[i0];
for ( i = 0; i < 64; i ++ )
{
if (in2!=0)
{
p[in2]=m1[i];
}
else
i=65;
v7=hash(p);
v5=(char *)malloc(4);
v5[0] = char(v7 >> 16);
v5[1] = char(v7 >> 8);
v5[2] = char(v7);
v5[3]='\0';
if ( check(v5[0],m1) && check(v5[1],m1) && check(v5[2],m1) )
{
infos[index][num].hash=(char *)malloc(4);
strcpy(infos[index][num].hash,v5);
ms[0]=p[in1];
if (in2==0)
{
ms[1]='\0';
}
else
{
ms[1]=p[in2];
ms[2]='\0';
}
infos[index][num].mw=(char *)malloc(3);
strcpy(infos[index][num].mw,ms);
num++;
delete v5;
}
}
if (i<64)
{
break;
}
}
}
void main()
{
char m2[17]="b@@[email protected]@[email protected]@@X",*p,*q;
int in1=0,in2=0,in3=0,in4=0;
q=m2;
get(q,0,1,2); //分段hash 參數分別為字符串 序號 m2里需要填充的字符坐標
q+=4;
get(q,1,1,0);
q+=4;
get(q,2,0,2);
q+=4;
get(q,3,1,2); //到這里infos就得到了所有滿足第一次HASH結果的可能的值
char temp1[15],temp2[15],temp3[15],temp4[15];
for(in1=0;;in1++) //暴力枚舉 所有組合，查找滿足第二次條件的值
{
if (!infos[0][in1].hash)
{
break;
}
strcpy(temp1,infos[0][in1].hash);
for (in2=0;;in2++)
{
strcpy(temp2,temp1);
if (!infos[1][in2].hash)
{
break;
}
strcat(temp2,infos[1][in2].hash);
p=temp2;
if (!check2(p))
{
continue;
}
for (in3=0;;in3++)
{
strcpy(temp3,temp2);
if (!infos[2][in3].hash)
{
break;
}
strcat(temp3,infos[2][in3].hash);
p=temp3+4;
if (!check2(p))
{
continue;
}
for (in4=0;;in4++)
{
strcpy(temp4,temp3);
if (!infos[3][in4].hash)
{
break;
}
strcat(temp4,infos[3][in4].hash);
p=temp4+8;
if (!p||!check2(p))
{
continue;
}
else
{
p=temp4;
char result[10];
result[0]='\0';
for (int i=0;i<3;i++)
{
int v7=hash(p);
char *v5=(char *)malloc(4);
v5[0] = char(v7 >> 16);
v5[1] = char(v7 >> 8);
v5[2] = char(v7);
v5[3]='\0';
strcat(result,v5);
p+=4;
}
for (i=0;i<strlen(result);i++)
{
char tt=result[i];
result[i]='a';
if (check(tt,result))
{
break;
}
result[i]=tt;
}
if (i==strlen(result))
{
puts("got it!!!");
printf("%s%s%s%s\n",infos[0][in1].mw,infos[1][in2].mw,infos[2][in3].mw,infos[3][in4].mw);
}
}
}
}
}
}
}
破解代碼運行后結果如下：
得到了兩個結果：
分別輸入兩個結果，顯示如下：
第一個結果，輸入后沒任何反應，也不提示錯誤。第二個輸入后成功得到flag。
分析認為這個加密算法有2個解，但是最終能解密FLAG的只有第二個才可以。
本題主要是通過兩次HASH運算 并分別進行驗證的方式加密；兩次都可以根據已知限制條件，分別采用暴力枚舉的方式進行暴力破解。雖然破解代碼量有點大，但是破解速度并沒有收到影響，執行破解代碼后能馬上得到結果！
文中有分析不當或不周全的地方，希望大家批評指正！