写在前面的感言
作为一个大一新生来说考线性代数真是太好了!
陷入深坑发现奥秘
首先打开程序运行(Win7SP1 64位下),回答是一个弹窗,于是马上去IDA的Exports里搜MessageBox,然后用xref向上翻几层(其实这几层是MFC的封装,IDA里按Shift+F5,添加新SignatureVC32MFC和VC32RTF,就可以解析出来),就到了输出结果的关键点。
通过修改跳转,我们知道了三个case分别是什么含义:
int __usercall sub_4071FD@<eax>(CWnd *this@<ecx>, int a2@<ebx>, int a3@<edi>)
{
CWnd *v3; // esi
int result; // eax
v3 = this;
CWnd::UpdateData(this, 1);
result = check(a2, a3, (int)v3);
switch ( result )
{
case 1:
return CWnd::MessageBoxW((void *)v3, (LPCWSTR)&unk_44BE10, &Caption, 0);// Right
case 0:
return CWnd::MessageBoxW((void *)v3, (LPCWSTR)&unk_44BE18, &Caption, 0);// Wrong
case 2:
result = CWnd::MessageBoxW((void *)v3, aWA, &Caption, 0);// Near to right
break;
}
return result;
}
所以可以估计判断是在check里发生的了,结合OllyDbg分析,我们可以很快还原check的大部分含义,中间有个int 0x2d,我当时以为是判断型的反调试,直接NOP掉了。
signed int __usercall check@<eax>(int a1@<ebx>, int a2@<edi>, int a3@<esi>)
{
int v3; // ecx
int v4; // ebx
_WORD *key; // eax
int keylen; // esi
int i; // ecx
unsigned int v8; // kr00_4
signed int result; // eax
signed int j; // [esp+14h] [ebp-D9F8h]
char v11; // [esp+18h] [ebp-D9F4h]
char v12[20]; // [esp+D998h] [ebp-74h]
char v13; // [esp+D9C0h] [ebp-4Ch]
__int16 v14; // [esp+D9D2h] [ebp-3Ah]
char v15[20]; // [esp+D9D4h] [ebp-38h]
int v16; // [esp+D9E8h] [ebp-24h]
int v17; // [esp+D9ECh] [ebp-20h]
int v18; // [esp+D9F0h] [ebp-1Ch]
CPPEH_RECORD ms_exc; // [esp+D9F4h] [ebp-18h]
int savedregs; // [esp+DA0Ch] [ebp+0h]
__alloca_probe();
ms_exc.registration.ScopeTable = (PSCOPETABLE_ENTRY)((_DWORD)ms_exc.registration.ScopeTable ^ __security_cookie);
v18 = a1;
v17 = a3;
v16 = a2;
*(_DWORD *)&v15[16] = (unsigned int)&savedregs ^ __security_cookie;
v4 = v3;
table_init(&v11);
strcpy(&v13, "KanXueCrackMe2017");
v14 = 0;
dealKey((int)&v11, &v13);
key = *(_WORD **)(v4 + 152);
keylen = *((_DWORD *)key - 3);
for ( i = 0; i < keylen; ++key )
{
if ( i < 0 || i > keylen )
ATL::AtlThrowImpl(-2147024809);
v15[i++] = *key;
}
v15[i] = 0;
__asm { int 2Dh; Windows NT - debugging services: eax = type }
ms_exc.registration.TryLevel = 0;
*(_DWORD *)&v15[12] = 4223103;
v8 = strlen(v15);
for ( j = 0; j < 1000; ++j )
{
base64((int)v12, (int)v15, v8);
memcpy_0(v15, v12, v8);
}
if ( strcmp("Vm0wd2QyUXlVWGw==", v12) )
return 0;
result = 1;
ms_exc.registration.TryLevel = -2;
return result;
}
然后可以看到只要你输入的key1000次base64和截断前strlen(key)位后等于Vm0wd2QyUXlVWGw==即可^^
然而不会,于是算去base64_decode("Vm0wd2QyUXlVWGw=="),恰好是这一函数的前11位,得到了key,不,这里多了一个等号。
继续分析,尝试随便一个输入,于是发现了一个很有趣的现象,任何一个key多次base64_encode后都会变成
Vm0wd2QyUX...开头的字符串,而substr(base64_encode(x),0,strlen(x))==x恰好是数列a(n+1)=
substr(base64_encode(a(n)),0,strlen(a(n)))极限的情况,真是有趣。
学习SEH回归正途
有趣归有趣,但在多次尝试之后都没有得到可使base64多一个等号的情况下我把注意力放在了int 0x2d上,网上去搜,发现它会触发一个异常,也就是说正常程序执行到这里会跳转到exception handler,而不是继续执行后面的代码 ,我们可以在程序运行到int 0x2d时把该句汇编改成mov eax,fs:[0],dword ptr ss:[eax+0x4]就是将要跳转到的正确地址了,在该处打上断点重来。
跳转到的地方是VC库中SEH处理函数,通过单步调试,我们可以发现真正要执行的代码在该处理函数下调用_EH4_TransferToHandler调用的v2中.
这里被IDA看做是check的一部分,我们这前面按E,然后在这里按P即可识别为一个新函数。
通过调试,我们可以得出以下内容,可以看到这才是正确的逻辑:
void __usercall hiddenFunc(int a1@<ebp>)
{
int v1; // eax
dealKey(a1 - 0xD9F4, (const char *)(a1 - 0x38));// a1-0x38 is the key!
v1 = 0;
while ( *(_DWORD *)(a1 + 4 * v1 - 0xD9F4) == *(_DWORD *)(a1 + 4 * v1 - 0xD934) )
{
if ( ++v1 >= 48 )
{
if ( ecc_check((const char *)(a1 - 0x38)) == 1 && strlen((const char *)(a1 - 0x38)) == 12 )
JUMPOUT(&loc_407114); // Bingo
*(_DWORD *)(a1 - 4) = -2;
JUMPOUT(loc_4071E3); // Near to right
}
}
JUMPOUT(&loc_407114); // Failed
}
分析高精度感叹人生
可见关键在dealKey中,再看
void __stdcall dealKey(int a1, const char *a2)
{
signed int v2; // ebx
int v3; // edi
char v4; // al
char *v5; // [esp+0h] [ebp-4h]
signed int key; // [esp+10h] [ebp+Ch]
v5 = (char *)malloc(3 * strlen(a2));
calc(a2, (int)v5);
key = strlen(v5);
v2 = 0;
if ( key > 0 )
{
v3 = key;
do
{
v4 = v5[v2];
if ( v4 < '0' || v4 > 57 )
{
if ( v4 >= 65 && v4 <= 'H' )
v3 = v4 - 55;
}
else
{
v3 = v4 - 48;
}
doABit(v3 / 3, v3 % 3 + 1, a1);
++v2;
}
while ( v2 < key );
}
free(v5);
}
我们首先分析calc中的代码,可以看到里面多次调用sub_403641,结合其内容和在dealKey和ecc_check中对它的调用,怀疑是高精度变量的初始化。
int __stdcall calc(const char *key, int blank)
{
char v3; // al
int v4; // ebx
bigNumber *v5; // eax
int v6; // ebx
char v7; // al
int result; // eax
signed int keylen; // [esp+10h] [ebp-208h]
signed int i; // [esp+14h] [ebp-204h] MAPDST
bigNumber ansAndRet; // [esp+18h] [ebp-200h]
bigNumber Val; // [esp+60h] [ebp-1B8h]
bigNumber vala; // [esp+A8h] [ebp-170h]
bigNumber valc; // [esp+F0h] [ebp-128h]
bigNumber valb; // [esp+138h] [ebp-E0h]
bigNumber valx; // [esp+180h] [ebp-98h]
bigNumber a2; // [esp+1C8h] [ebp-50h]
Val.len = -1;
LOBYTE(Val.sig) = 0;
memset(&Val, 0, 0x40u);
initBigNumber(1, 0, &vala);
initBigNumber(62, 0, &valb);
initBigNumber(18, 0, &valc);
keylen = strlen(key);
i = 0;
for ( i = 0; i < keylen; ++i )
{
v3 = key[i];
if ( v3 < '0' || v3 > '9' )
{
if ( v3 < 'A' || v3 > 'Z' )
{
if ( v3 < 'a' || v3 > 'z' )
v4 = -1;
else
v4 = v3 - '=';
}
else
{
v4 = v3 - '7';
}
}
else
{
v4 = v3 - '0';
}
if ( v4 != -1 )
{
initBigNumber(v4, 0, &valx);
v5 = sub_4038E1(&vala, &a2, &valx);
sub_40447F((int)&Val, &ansAndRet, (int)v5);
sub_404669(&vala, &valb, &ansAndRet);
}
}
v6 = 0;
if ( Val.len >= 0 )
{
while ( 1 )
{
qmemcpy(&vala, mod(&Val, &ansAndRet, &valc), sizeof(vala));
qmemcpy(&Val, div(Val.num, &ansAndRet, &valc), sizeof(Val));
if ( vala.num[0] <= 9u && !vala.len )
break;
if ( (unsigned int)(vala.num[0] - 10) <= 7 && !vala.len )
{
v7 = LOBYTE(vala.num[0]) + '7';
goto LABEL_22;
}
if ( vala.len != -1 || vala.num[0] )
{
printf("error %d %d \n", vala.num[0], vala.len);
goto LABEL_28;
}
*(_BYTE *)(blank + v6) = '0';
LABEL_26:
++v6;
LABEL_28:
if ( Val.len < 0 )
goto LABEL_29;
}
v7 = LOBYTE(vala.num[0]) + '0';
LABEL_22:
*(_BYTE *)(blank + v6) = v7;
goto LABEL_26;
}
LABEL_29:
result = blank;
*(_BYTE *)(blank + v6) = 0;
return result;
}
然后我们继续看到sub_403F83中公然写着sub_406256("模错误。。。");(可能需要IDA7.0并配置ida.cfg查看中文),可以判断八成是高精度库,并且该函数在取模。(我当时还是没敢断定,这么多年高精度算是白写了啊)
然后我们继续分析这个函数,虽然我没有分析全,但通过已经分析的内容可以基本断定是在做进制转换(从62进制(0-9A-Za-z)转为18进制(0-9A-H))。
我们可以用Java来做反向计算的工作(由于BigNumber似乎不支持超过36进制的直接输出,我们可以手写代码来做这个工作),我的代码如下(初学BigNumber库请谅解,注意x和cm中实际输出相反 ):
import java.math.*;
class KXCTF2017Fall5{
static String x="EAFC52E741H1C9F64";
static String y="62";
public static void main(String args[]) {
BigInteger a=new BigInteger(x,18);
System.out.println(a.toString(10));
BigInteger b=new BigInteger(y,10);
int z=0;
String ans="";
while(a.compareTo(BigInteger.ZERO)>0){
int y=a.mod(b).intValue();
if(y<=9)ans+=(char)('0'+y);
else if(y<=9+26)ans+=(char)('A'+(y-10));
else ans+=(char)('a'+(y-10-26));
a=a.divide(b);
}
System.out.println(ans);
}
}
分析矩阵乘法巩固线代
接下来就看doABit的内容了,里面都调用了同一个函数matrix_mul,只是由于参数不同,调用的参数和次数不同罢了。
char *__usercall doABit@<eax>(int a1@<eax>, int a2@<ecx>, int a3@<esi>)
{
int v3; // eax
int v4; // eax
int v5; // eax
int v6; // eax
char *result; // eax
int v8; // ecx
if ( a1 )
{
v3 = a1 - 1;
if ( v3 )
{
v4 = v3 - 1;
if ( v4 )
{
v5 = v4 - 1;
if ( v5 )
{
v6 = v5 - 1;
if ( v6 )
{
result = (char *)(v6 - 1);
if ( result )
return result;
if ( a2 != 1 )
{
if ( a2 != 2 )
{
result = (char *)(a2 - 3);
if ( a2 != 3 )
return result;
matrix_mul((_DWORD *)(a3 + 192), (char *)(a3 + 192), a3 + 46464);
}
matrix_mul((_DWORD *)(a3 + 192), (char *)(a3 + 192), a3 + 46464);
}
v8 = a3 + 0xB580;
}
else
{
if ( a2 != 1 )
{
if ( a2 != 2 )
{
result = (char *)(a2 - 3);
if ( a2 != 3 )
return result;
matrix_mul((_DWORD *)(a3 + 192), (char *)(a3 + 192), a3 + 37248);
}
matrix_mul((_DWORD *)(a3 + 192), (char *)(a3 + 192), a3 + 37248);
}
v8 = a3 + 37248;
}
}
else
{
if ( a2 != 1 )
{
if ( a2 != 2 )
{
result = (char *)(a2 - 3);
if ( a2 != 3 )
return result;
matrix_mul((_DWORD *)(a3 + 192), (char *)(a3 + 192), a3 + 28032);
}
matrix_mul((_DWORD *)(a3 + 192), (char *)(a3 + 192), a3 + 0x6D80);
}
v8 = a3 + 28032;
}
}
else
{
if ( a2 != 1 )
{
if ( a2 != 2 )
{
result = (char *)(a2 - 3);
if ( a2 != 3 )
return result;
matrix_mul((_DWORD *)(a3 + 192), (char *)(a3 + 192), a3 + 18816);
}
matrix_mul((_DWORD *)(a3 + 192), (char *)(a3 + 192), a3 + 0x4980);
}
v8 = a3 + 18816;
}
}
else
{
if ( a2 != 1 )
{
if ( a2 != 2 )
{
result = (char *)(a2 - 3);
if ( a2 != 3 )
return result;
matrix_mul((_DWORD *)(a3 + 192), (char *)(a3 + 192), a3 + 9600);
}
matrix_mul((_DWORD *)(a3 + 192), (char *)(a3 + 192), a3 + 0x2580);
}
v8 = a3 + 9600;
}
}
else
{
if ( a2 != 1 )
{
if ( a2 != 2 )
{
result = (char *)(a2 - 3);
if ( a2 != 3 )
return result;
matrix_mul((_DWORD *)(a3 + 192), (char *)(a3 + 192), a3 + 0x180);
}
matrix_mul((_DWORD *)(a3 + 192), (char *)(a3 + 192), a3 + 384);
}
v8 = a3 + 384;
}
return matrix_mul((_DWORD *)(a3 + 192), (char *)(a3 + 192), v8);
}
于是分析其中的matrix_mul,一开始我还以为两重循环的是典型的“纸与笔”高精度乘法(一般矩阵乘法三重循环),但是并不是,它是一个(1*n)*(n*n)的矩阵乘法。
char *__usercall matrix_mul@<eax>(_DWORD *a1, char *a2, int x@<ecx>)
{
int v3; // ebx
char *result; // eax
_DWORD *v5; // edx
int v6; // ecx
_DWORD *v7; // esi
signed int v8; // [esp+10h] [ebp-CCh]
signed int v9; // [esp+14h] [ebp-C8h]
char v10; // [esp+18h] [ebp-C4h]
v3 = x;
result = &v10;
v9 = 48;
do
{
v5 = a1;
v6 = 0;
v7 = (_DWORD *)v3;
v8 = 48;
do
{
v6 += *v7 * *v5;
++v5;
v7 += 48;
--v8;
}
while ( v8 );
*(_DWORD *)result = v6;
v3 += 4;
result += 4;
--v9;
}
while ( v9 );
qmemcpy(a2, &v10, 0xC0u);
return result;
}
进一步分析可知,题中将一个1*n矩阵乘多个n*n矩阵,最后要求1*n矩阵恢复原状,这是一种典型的快速判断那些n*n矩阵乘积是否为单位矩阵的算法(高概率正确)。
继续看,发现这些n*n矩阵按我们输入的字符串指示来乘,之前得出的18进制下的每一位数p都会被执行doABit,调用matrix_mul的参数为p/3为乘的n*n矩阵的编号,p%3+1位乘的次数。
这些n*n矩阵可以用OllyDbg直接从内存中dump出来(免去分析生成过程),可以发现它们全都是置换矩阵,因此其实计算它们只需要Θ(n)的时间复杂度,我们用C++载入它们并分析,可以发现1*n矩阵乘这些矩阵的四次方的结果恰好是那个1*n矩阵(*) 。分析的代码如下:
#include <cstdio>
#include <cstring>
using namespace std;
unsigned int buf[6][50][48];
int bd[6][50];
int e[50],f[50];
int main(){
freopen("a.txt","rb",stdin);
//freopen("d.txt","w",stdout);
fread(buf,0x180,1,stdin);
for(int j=0;j<48;j++)printf("%3d",j);
puts("");
for(int l=0;l<6;l++){
fread(buf[l],0x2400,1,stdin);
for(int i=0;i<48;i++){
for(int j=0;j<48;j++)if(buf[l][j][i]==1)bd[l][i]=j,printf("%3d",j);
}
puts("");
}
for(int h=0;h<6;h++){
for(int j=0;j<48;j++)e[j]=j;
for(int i=1;i<=4;i++){
for(int j=0;j<48;j++)f[j]=e[bd[2][j]];
memcpy(e,f,sizeof f);
}
for(int j=0;j<48;j++)printf("%3d",f[j]);
puts("");
}
return 0;
}
这样的答案似乎有很多种,继续调试发现,原来那个1*n矩阵在按我们密钥的指示乘数之前就已经被按其他字符串的指示乘过,这段代码就在一开始的check函数中
strcpy(&v13, "KanXueCrackMe2017");
v14 = 0;
dealKey((int)&v11, &v13);
我们直接通过调试获取KanXueCrackMe2017转为18进制的值,为EDAHE450C741GH441E11BH84,既然它已经乘了这写,我们理所当然可以反过来按反序乘他们各自的逆矩阵(也就是该矩阵的三次方,
更进一步地,我们对于某矩阵的k次方,可以乘4-k次方
),从而得到原矩阵,公式见下:
我们把这个过程同样用程序来实现,代码如下(
由于之前Java程序中x和cm中实际输出相反,所以这边不需要反向,只要顺序输出就行了 ):
#include <cstdio>
#include <cstring>
using namespace std;
unsigned int buf[6][50][48];
int bd[6][50];
int main(){
freopen("a.txt","rb",stdin);
//freopen("d.txt","w",stdout);
fread(buf,0x180,1,stdin);
for(int j=0;j<48;j++)printf("%3d",j);
puts("");
for(int l=0;l<6;l++){
fread(buf[l],0x2400,1,stdin);
for(int i=0;i<48;i++){
for(int j=0;j<48;j++)if(buf[l][j][i]==1)bd[l][i]=j,printf("%3d",j);
}
puts("");
}
//delim
puts("========================");
char x[]="EDAHE450C741GH441E11BH84";
int cnt=-1;
char u[100];
memset(u,0,sizeof u);
for(int i=0,_=strlen(x);i<_;i++){
int p=0;
if(x[i]>='A'){
p=x[i]-'A'+10;
}else p=x[i]-'0';
u[++cnt]=(p/3)*3+(4-(p%3+1)-1);
}
for(int i=0;i<=cnt;i++){
char p=u[i];
printf("%c",p<10?'0'+p:p-10+'A');
}
return 0;
}
我们把得到的结果放到前面的Java程序中的x变量中,得到一个key(ieunV2phk6yPywNtJ),输入窗口,返回还差一小步:
稍加修改最后收工
我们可以看到之前代码中要返回正确还要满足一下条件:
ecc_check((const char *)(a1 - 0x38)) == 1 && strlen((const char *)(a1 - 0x38)) == 12
ecc_check中通过将几个initBigNumber的返回值相加定义了一些大常数,并且里面字符串中ecc等字样,而我们知道
普通Cracker在非对称加密算法面前是渺小的 ,所以不去分析,看到另一个限制是key长度为12,而我们之前的key比这个长,我们很容易想到一个压缩方法:
如果key中指示了连续四次乘某矩阵,就把这一部分划掉 (比如12指示的是乘1号矩阵2+3次,相当于乘(2+3)%4=1次,我们将12改成0),从而减小key长度。
这个工作可以通过稍微修改一下我们的程序实现,如下:
#include <cstdio>
#include <cstring>
using namespace std;
unsigned int buf[6][50][48];
int bd[6][50];
int main(){
freopen("a.txt","rb",stdin);
//freopen("d.txt","w",stdout);
fread(buf,0x180,1,stdin);
for(int j=0;j<48;j++)printf("%3d",j);
puts("");
for(int l=0;l<6;l++){
fread(buf[l],0x2400,1,stdin);
for(int i=0;i<48;i++){
for(int j=0;j<48;j++)if(buf[l][j][i]==1)bd[l][i]=j,printf("%3d",j);
}
puts("");
}
//delim
puts("========================");
char x[]="EDAHE450C741GH441E11BH84";
int pre=-1,p2,cnt=-1;//Changed
char u[100];
memset(u,0,sizeof u);
for(int i=0,_=strlen(x);i<_;i++){
int p=0;
if(x[i]>='A'){
p=x[i]-'A'+10;
}else p=x[i]-'0';
if(pre==(p/3)){//Changed range start
u[cnt]=(p/3)*3+(4-((p%3+1)+p2)%4-1);
if(((p%3+1)+p2)%4==0)cnt--;
}else{
u[++cnt]=(p/3)*3+(4-(p%3+1)-1);
p2=p%3+1;
pre=p/3;
}//Changed range end
}
for(int i=0;i<=cnt;i++){
char p=u[i];
printf("%c",p<10?'0'+p:p-10+'A');
}
return 0;
}
我们再把得到的结果放到前面的Java程序中的x变量中,得到又一个key(CcLaoE37J45Y),成功了!!!
另外,我们进一步可猜想ecc_check仅仅是在保证解的唯一性。
[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!
最后于 2018-7-14 00:15
被qwertyaa编辑
,原因: