-
-
[原创]2019 Q2 第十题 开启时间之轮 分析
-
2019-6-23 20:02 6551
-
0x1 程序分析
win32对话框程序,按钮事件处理函数为0x403db
int __cdecl ctf_Dlg_check(HWND hDlg) { signed int kenlen; // eax signed int bad_code; // esi unsigned int randstr_len_1; // ebp unsigned int randstr_len; // kr04_4 char *v5; // eax char **v6; // edx signed int i; // ecx char *pdata; // esi int idx; // eax signed int v11; // [esp+Ch] [ebp-8B0h] int xxxxxxx; // [esp+10h] [ebp-8ACh] int suffix_str_or_numbase[3]; // [esp+14h] [ebp-8A8h] int suffix_max_len[3]; // [esp+20h] [ebp-89Ch] int suffix_addnum[3]; // [esp+2Ch] [ebp-890h] int val[3]; // [esp+38h] [ebp-884h] OBJ3 pobj; // [esp+44h] [ebp-878h] int a3; // [esp+74h] [ebp-848h] char v19; // [esp+78h] [ebp-844h] CHAR final_text[256]; // [esp+B0h] [ebp-80Ch] char rand_string[256]; // [esp+1B0h] [ebp-70Ch] CHAR key[256]; // [esp+2B0h] [ebp-60Ch] CHAR prepared_rand_string[256]; // [esp+3B0h] [ebp-50Ch] CHAR Text; // [esp+4B0h] [ebp-40Ch] char v25; // [esp+4B1h] [ebp-40Bh] __int16 v26; // [esp+8ADh] [ebp-Fh] char v27; // [esp+8AFh] [ebp-Dh] int ignore; // [esp+8B8h] [ebp-4h] rand_string[0] = 0; memset(&rand_string[1], 0, 0xFCu); *(_WORD *)&rand_string[253] = 0; rand_string[255] = 0; prepared_rand_string[0] = 0; memset(&prepared_rand_string[1], 0, 0xFCu); *(_WORD *)&prepared_rand_string[253] = 0; prepared_rand_string[255] = 0; key[0] = 0; memset(&key[1], 0, 0xFCu); *(_WORD *)&key[253] = 0; key[255] = 0; final_text[0] = 0; memset(&final_text[1], 0, 0xFCu); *(_WORD *)&final_text[253] = 0; final_text[255] = 0; Text = 0; memset(&v25, 0, 0x3FCu); v26 = 0; v27 = 0; suffix_str_or_numbase[1] = 10; suffix_str_or_numbase[2] = 10; suffix_addnum[0] = 10; suffix_max_len[0] = 10; suffix_max_len[1] = 100; suffix_max_len[2] = 100; val[0] = 2; val[1] = 0xFF; val[2] = 0xFFFFFFED; suffix_str_or_numbase[0] = 0x100; suffix_addnum[1] = 0; suffix_addnum[2] = 0; xxxxxxx = 0; GetDlgItemTextA(hDlg, 1000, prepared_rand_string, 255); kenlen = GetDlgItemTextA(hDlg, 1001, key, 255); if ( kenlen < 6 || kenlen > 145 ) { v11 = 1; bad_code = 1; } else { bad_code = 0; v11 = 0; } sscanf(prepared_rand_string, aDS, &xxxxxxx, rand_string); `eh vector constructor iterator'(&pobj, 0x10u, 3, (void (__thiscall *)(void *))obj_construct, (void (__thiscall *)(void *))obj_destructor); randstr_len = strlen(rand_string) + 1; randstr_len_1 = randstr_len - 1; ignore = 0; if ( ctf_obj_malloc_len(&pobj.o3, randstr_len - 1, 1) ) { qmemcpy(pobj.o3.pdata, rand_string, randstr_len_1); bad_code = v11; pobj.o3.data_len = randstr_len - 1; pobj.o3.pdata[randstr_len_1] = 0; } if ( bad_code || !ctf_check_format(key, &pobj.o1, &pobj.o2) ) { sprintf(final_text, aBadCodeD, bad_code + 1); } else { v5 = &v19; v6 = &pobj.o1.pdata; i = 0; do { pdata = *v6; if ( !*v6 ) pdata = (char *)&unk_4100FC; *((_DWORD *)v5 - 1) = pdata; *(_DWORD *)v5 = v6[1]; *((_DWORD *)v5 + 1) = suffix_str_or_numbase[i]; *((_DWORD *)v5 + 2) = suffix_addnum[i]; *((_DWORD *)v5 + 3) = suffix_max_len[i]; ++i; v6 += 4; v5 += 20; } while ( i < 3 ); idx = ctf_final_check((int)hDlg, (NNN *)&a3, val, xxxxxxx); b64decode_idx(idx, final_text); } sprintf(&Text, final_text); MessageBoxA(hDlg, &Text, final_text, 0); ignore = -1; `eh vector destructor iterator'(&pobj, 0x10u, 3, (void (__thiscall *)(void *))obj_destructor); return 0; }
从4个大数字符串里随机选取一个:
BOOL __cdecl ctf_set_rand_text(HWND hDlg) { char n; // al LPCSTR pText[4]; // [esp+0h] [ebp-10h] pText[0] = a10092301978589; pText[1] = a10150414221767; pText[2] = a10238377684164; pText[3] = a10313436195533; n = rand(); return SetDlgItemTextA(hDlg, 1000, pText[n & 3]); }
input长度在[6,145]中:
if ( kenlen < 6 || kenlen > 145 ) { v11 = 1; bad_code = 1; }
进入check_format做格式验证:
1.input分为两部分,由"XXXX"分隔。
2.后半部分必须为数字,且第一个数字不能为0。(应该是防止多解用的)
char __cdecl ctf_check_format(const char *key, STR_OBJ *obj1, STR_OBJ *obj2) { char *pdata; // eax unsigned __int64 data_len; // ST04_8 int len; // eax int ret_1; // esi STR_OBJ *v7; // eax STR_OBJ *v8; // eax unsigned int v9; // ecx char *v10; // eax int v11; // edi char *v12; // eax char v13; // al char v14; // al char v15; // al char result; // al char v17; // al STR_OBJ obj_t2; // [esp+Ch] [ebp-3Ch] STR_OBJ obj_key; // [esp+1Ch] [ebp-2Ch] STR_OBJ obj_t3; // [esp+2Ch] [ebp-1Ch] int ignore; // [esp+44h] [ebp-4h] obj_key.byte_field = (char)key; obj_setup(&obj_key, 0); obj_set_data(&obj_key, key, strlen(key)); obj_t2.byte_field = (char)key; ignore = 0; obj_setup(&obj_t2, 0); obj_memset(&obj_t2, 4u, 'X'); pdata = obj_t2.pdata; LOBYTE(ignore) = 1; if ( !obj_t2.pdata ) pdata = (char *)&unk_4100FC; HIDWORD(data_len) = obj_t2.data_len; LODWORD(data_len) = 0; len = obj_mem_find(&obj_key, pdata, data_len); ret_1 = len; if ( len == -1 ) goto gg; v7 = sub_404B60(&obj_key, &obj_t3, 0, len); LOBYTE(ignore) = 2; sub_404CF0(v7, 0, -1); LOBYTE(ignore) = 1; obj_setup(&obj_t3, 1); v8 = sub_404B60(&obj_key, &obj_t3, ret_1 + obj_t2.data_len, 0xFFFFFFFF); LOBYTE(ignore) = 3; sub_404CF0(v8, 0, -1); LOBYTE(ignore) = 1; obj_setup(&obj_t3, 1); if ( !obj1->data_len ) goto gg; v9 = obj2->data_len; if ( !v9 ) goto gg; v10 = obj2->pdata; if ( !v10 ) v10 = (char *)&unk_4100FC; if ( *v10 == '0' ) { gg: LOBYTE(ignore) = 0; obj_setup(&obj_t2, 1); ignore = -1; obj_setup(&obj_key, 1); return 0; } v11 = 0; if ( v9 > 0 ) { while ( 1 ) { v12 = obj2->pdata; if ( !v12 ) v12 = (char *)&unk_4100FC; if ( !isdigit(v12[v11]) ) break; if ( (unsigned int)++v11 >= obj2->data_len ) goto LABEL_14; } if ( obj_t2.pdata ) { v14 = *(obj_t2.pdata - 1); if ( v14 && v14 != -1 ) *(obj_t2.pdata - 1) = v14 - 1; else ctf_free(obj_t2.pdata - 1); } obj_t2.pdata = 0; obj_t2.data_len = 0; obj_t2.availabe_buf_size = 0; if ( obj_key.pdata ) { v15 = *(obj_key.pdata - 1); if ( v15 && v15 != -1 ) { *(obj_key.pdata - 1) = v15 - 1; result = 0; } else { ctf_free(obj_key.pdata - 1); result = 0; } return result; } return 0; } LABEL_14: if ( obj_t2.pdata ) { v13 = *(obj_t2.pdata - 1); if ( v13 && v13 != -1 ) *(obj_t2.pdata - 1) = v13 - 1; else ctf_free(obj_t2.pdata - 1); } obj_t2.pdata = 0; obj_t2.data_len = 0; obj_t2.availabe_buf_size = 0; if ( obj_key.pdata ) { v17 = *(obj_key.pdata - 1); if ( v17 && v17 != -1 ) { *(obj_key.pdata - 1) = v17 - 1; return 1; } ctf_free(obj_key.pdata - 1); } return 1; }
将输入的第一部分,第二部分和随机选取的大数存在自定义的字符串结构中:
00000000 STR_OBJ struc ; (sizeof=0x10, mappedto_34) 00000000 ; XREF: ctf_check_format/r 00000000 ; ctf_check_format/r ... 00000000 byte_field db ? ; XREF: ctf_check_format+26/w 00000000 ; ctf_check_format+4E/w 00000001 useless db 3 dup(?) ; string(C) 00000004 pdata dd ? ; XREF: ctf_check_format+6D/r 00000004 ; ctf_check_format:loc_403C6F/r ... ; offset 00000008 data_len dd ? ; XREF: ctf_check_format:loc_403B7F/r 00000008 ; ctf_check_format+DC/r ... 0000000C availabe_buf_size dd ? ; XREF: ctf_check_format+1CA/w 0000000C ; ctf_check_format+22E/w
STR_OBJ3 pstr_obj; 00000000 STR_OBJ3 struc ; (sizeof=0x30, mappedto_35) 00000000 ; XREF: ctf_Dlg_check/r 00000000 o1 STR_OBJ ? ; XREF: ctf_Dlg_check+201/o 00000010 o2 STR_OBJ ? ; XREF: ctf_Dlg_check+1DF/o 00000020 o3 STR_OBJ ? ; XREF: ctf_Dlg_check+198/o 00000020 ; ctf_Dlg_check+1AC/r ... 00000030 STR_OBJ3 ends
由3个字符串和其他一些数据组成了新的结构,传入最后的校验函数ctf_final_check
00000000 NNN struc ; (sizeof=0x14, mappedto_37) 00000000 pdata dd ? ; offset 00000004 data_len dd ? 00000008 str_or_numbase dd ? 0000000C add_num dd ? 00000010 maxcount dd ? 00000014 NNN ends
ctf_final_check的返回值传入一个变形的b64函数里,生成最后的提示信息字符串:(提示成功的字符串对应着final_check的返回值为0)
int __cdecl b64decode_idx(int idx, char *outbuf) { int cnt; // eax char *s; // esi unsigned int len; // eax char *pstr[5]; // [esp+Ch] [ebp-280h] char *pstrNull[27]; // [esp+20h] [ebp-26Ch] char buf2[256]; // [esp+8Ch] [ebp-200h] char buf[256]; // [esp+18Ch] [ebp-100h] buf[0] = 0; pstr[0] = s_Yes_correct; pstr[1] = s_No_wrongSN; pstr[2] = s_SN_doesnt_work; pstr[3] = s_findsth_err; pstr[4] = s_wrong_addoil; memset(pstrNull, 0, sizeof(pstrNull)); memset(&buf[1], 0, 0xFCu); *(_WORD *)&buf[253] = 0; buf[255] = 0; buf2[0] = 0; memset(&buf2[1], 0, 0xFCu); *(_WORD *)&buf2[253] = 0; buf2[255] = 0; cnt = cnt_of_one(idx); s = pstr[cnt]; if ( !s ) s = pstr[cnt_of_one(cnt) | 1]; sub_403870(0x40, buf2, 0x40u); sub_403630(buf2); len = sub_403660(s, buf); qmemcpy(outbuf, buf, len); outbuf[len] = 0; return 0; }
ctf_final_check:
int __cdecl ctf_final_check(int a2, NNN *nnn, _DWORD *val, int ct) { void *v4; // esp signed int i_1; // esi unsigned int val2_1; // esi int val3_1; // edi signed int i; // esi NNN *pNNN; // edi int base; // eax signed int sign; // eax int i_2; // esi int const_6_1; // ebx unsigned __int8 const_25; // al unsigned int const_25_1; // ebx unsigned int i_3; // esi int data_len; // ecx char *v18; // eax char *v19; // edi unsigned __int8 val_1; // al int val_2; // edi int val_result; // esi int i_4; // esi int j; // edi signed int i_5; // eax int ret_1; // ecx int v30; // [esp-Ch] [ebp-40724h] int ignore_1; // [esp+0h] [ebp-40718h] unsigned int ignore_2; // [esp+4h] [ebp-40714h] char *p_1; // [esp+8h] [ebp-40710h] unsigned int maxcount; // [esp+Ch] [ebp-4070Ch] char buf[256]; // [esp+10h] [ebp-40708h] char *buf_2; // [esp+110h] [ebp-40608h] int val_3; // [esp+114h] [ebp-40604h] int idx; // [esp+118h] [ebp-40600h] int bfail_1; // [esp+11Ch] [ebp-405FCh] BN bn_XXX1; // [esp+120h] [ebp-405F8h] BN bn_XXX2; // [esp+12Ch] [ebp-405ECh] BN bn_XXX3; // [esp+138h] [ebp-405E0h] BN bn14; // [esp+144h] [ebp-405D4h] int const_6; // [esp+150h] [ebp-405C8h] BN bn2; // [esp+154h] [ebp-405C4h] int n_multiply[6]; // [esp+160h] [ebp-405B8h] BN bn11; // [esp+178h] [ebp-405A0h] int rand_int; // [esp+184h] [ebp-40594h] int val2; // [esp+188h] [ebp-40590h] BN p; // [esp+18Ch] [ebp-4058Ch] BN bn_cipher; // [esp+198h] [ebp-40580h] int ignore; // [esp+1A4h] [ebp-40574h] BN bn_e; // [esp+1A8h] [ebp-40570h] int val_ret_check1; // [esp+1B4h] [ebp-40564h] int val_ret_check2; // [esp+1B8h] [ebp-40560h] int val_ret_check3; // [esp+1BCh] [ebp-4055Ch] BN bn_X3; // [esp+1C0h] [ebp-40558h] BN bn; // [esp+1CCh] [ebp-4054Ch] BN bn8; // [esp+1D8h] [ebp-40540h] BN bn_result; // [esp+1E4h] [ebp-40534h] int e[6]; // [esp+1F0h] [ebp-40528h] BN bn_phi; // [esp+208h] [ebp-40510h] BN bn_d; // [esp+214h] [ebp-40504h] BN bn_expect0; // [esp+220h] [ebp-404F8h] BN bn7; // [esp+22Ch] [ebp-404ECh] BN bn_expmod1[6]; // [esp+238h] [ebp-404E0h] BN bn_dif; // [esp+280h] [ebp-40498h] BN bn_X2; // [esp+28Ch] [ebp-4048Ch] int val3; // [esp+298h] [ebp-40480h] int prime_list[65536]; // [esp+29Ch] [ebp-4047Ch] BN bn_X1; // [esp+402C0h] [ebp-458h] BN bn9; // [esp+402CCh] [ebp-44Ch] int ret; // [esp+402D8h] [ebp-440h] int val1; // [esp+402DCh] [ebp-43Ch] BN bn_modN; // [esp+406E0h] [ebp-38h] BN bn_m; // [esp+406ECh] [ebp-2Ch] int bfail; // [esp+406F8h] [ebp-20h] int remainder; // [esp+406FCh] [ebp-1Ch] CPPEH_RECORD ms_exc; // [esp+40700h] [ebp-18h] v4 = alloca(263936); ms_exc.old_esp = (DWORD)&v30; const_6 = 6; n_multiply[0] = 3; i_1 = 0; n_multiply[1] = 0; n_multiply[2] = 1; n_multiply[3] = 0; n_multiply[4] = 64; n_multiply[5] = 0; e[0] = 0; e[1] = 1; e[2] = 2; e[3] = 3; e[4] = 4; e[5] = 5; ret = 0; val_ret_check1 = 32; val_ret_check2 = 64; val_ret_check3 = 128; bfail = 0; remainder = 0; rand_int = rand(); prime_list[0] = 0; memset(&prime_list[1], 0, 0x40020u); ms_exc.registration.TryLevel = 0; BN_setup(&bn_XXX1); BN_setup(&bn_dif); BN_setup(&bn_phi); while ( 1 ) { ignore = i_1; if ( i_1 >= 6 ) break; BN_setup(&bn_expmod1[i_1++]); } val1 = *val & 0xFFF; // 2 val2 = val[1] & 0xFF; // 0xff val2_1 = val2; val3 = val[2]; val3_1 = val3; // 0xFFFFFFED BN_set_num(&bn_modN, val1); // bn1=2 BN_quick_exp(&bn2, &bn_modN, val2_1); // bn2=2**0xff BN_add_imm(&bn_modN, &bn2, val3_1); // bn1 = 2**0xff-19 BN_sub_imm(&bn_phi, &bn_modN, 1); // bn3 = 2**0xff-20 BN_set_num(&bn_cipher, ct); for ( i = 0; ; ++i ) { ignore = i; if ( i >= 3 ) break; pNNN = &nnn[i]; base = pNNN->str_or_numbase; if ( base == 256 ) BN_str_reverse(&bn_XXX1 + i, pNNN->pdata, pNNN->data_len);// reverse(part1)+10 else ret = BN_set_from_base(&bn_XXX1 + i, base, pNNN->pdata);// int(part2,10) BN_add_imm(&bn_XXX1 + i, &bn_XXX1 + i, pNNN->add_num); } if ( ret ) { bfail = 1; } else { BN_copy(&bn_X1, &bn_XXX1); BN_copy(&bn_X2, &bn_XXX2); BN_copy(&bn_X3, &bn_XXX3); BN_add_bn(&bn7, &bn_X2, &bn_X2); BN_add_bn(&bn8, &bn7, &bn7); sign = BN_cmp_bn(&bn8, &bn_modN); val_ret_check1 = sign >= 0; if ( sign < 0 ) { BN_set_num(&bn9, sign >= 0); i_2 = 0; ignore = 0; const_6_1 = const_6; while ( i_2 < const_6_1 ) // 6 { BN_sub_bn(&bn_dif, &bn_X2, &bn_X1); BN_quick_expmod(&bn_expmod1[i_2], &bn_dif, e[i_2], &bn_modN);// e=[0,1,2,3,4,5] BN_multi_add_mod(&bn11, n_multiply[i_2], &bn_expmod1[i_2], &bn9, &bn_modN);// a = [3,0,1,0,64,0] BN_copy(&bn9, &bn11); ignore = ++i_2; } BN_sub_bn(&bn_expect0, &bn_X1, &bn9); val_ret_check2 = BN_get_num(&bn_expect0); if ( !val_ret_check2 ) { BN_set_num(&bn_e, 0); const_25 = bytearray_get_by_idx('X'); const_25_1 = const_25; ignore_1 = const_25; i_3 = 0; ignore_2 = 0; maxcount = nnn->maxcount; buf[0] = 0; memset(&buf[1], 0, 0xFCu); *(_WORD *)&buf[253] = 0; buf[255] = 0; data_len = nnn->data_len; v18 = &nnn->pdata[data_len - 1]; p_1 = &nnn->pdata[data_len - 1]; v19 = buf; buf_2 = buf; while ( v18 >= nnn->pdata ) { *v19++ = *v18; buf_2 = v19; p_1 = --v18; } buf[0] += LOBYTE(nnn->add_num); while ( i_3 < strlen(buf) ) { idx = buf[i_3++]; ignore_2 = i_3; val_1 = bytearray_get_by_idx(idx); val_2 = val_1; val_3 = val_1; if ( val_1 >= const_25_1 ) { bfail_1 = 1; break; } BN_multiply(&bn_e, &bn_e, const_25_1); BN_add_imm(&bn_e, &bn_e, val_2); } if ( i_3 <= maxcount && !bfail_1 ) { rand_int = gen_prime(rand_int, prime_list); ignore = 0; if ( rand_int > 0 && prime_list[0] ) { BN_DIV(&remainder, &bn_e, prime_list[0]); if ( remainder ) JUMPOUT(unk_4047EE); } else { BN_gcd(&bn11, &bn_phi, &bn_e); if ( j_BN_count_bits(&bn11) <= 1 ) { BN_modinv(&bn_d, &bn_e, &bn_phi); BN_exp_mod(&bn_m, &bn_cipher, &bn_d, &bn_modN, &bn14); BN_sub_bn(&bn_result, &bn_X3, &bn_m); val_result = BN_get_num(&bn_result); val_ret_check3 = val_result; BN_exp_mod(&p, &bn_X3, &bn_e, &bn_modN, &bn14); BN_sub_bn(&bn, &p, &bn_cipher); if ( val_result ) val_ret_check3 = BN_get_num(&bn); } } } } } } ms_exc.registration.TryLevel = -1; BN_free(&bn_XXX1); BN_free(&bn_dif); BN_free(&bn_phi); i_4 = 0; for ( j = const_6; i_4 < j; ++i_4 ) BN_free(&bn_expmod1[i_4]); i_5 = 0; ret_1 = bfail; do ret_1 |= *(&val_ret_check1 + i_5++); while ( i_5 < 3 ); return ret_1; }
使用到的大数结构:
00000000 BN struc ; (sizeof=0xC, mappedto_36) 00000000 ; XREF: BN_set_from_base/r 00000000 ; BN_cmp_imm/r ... 00000000 sign dd ? ; XREF: BN_cmp_imm+3A/w 00000000 ; BN_add_imm+3E/w ... 00000004 size_in_dword dd ? ; XREF: BN_cmp_imm+29/w 00000004 ; BN_add_imm+31/w ... 00000008 pdata dd ? ; XREF: BN_cmp_imm+31/w 00000008 ; BN_add_imm+29/w ... ; offset 0000000C BN ends
把3个字符串转换为数字,进行几个个关键校验:(省略了一些简单的变换步骤)
1、4*y < 2**255 - 19 2、(x-y)**2 + 64*(x-y)**4 + 3 = x (mod 2**255-19) 3、A**(x_b25) = B (mod 2**255-19) A、B已知 4、x_b25 < 25**10
0x2 求解
BSGS解小区间上的离散对数:
跑了10多分钟跑出来 x_b25 = 79821823136933
经验证 x_b25同时也满足其他3组离散对数方程。
# pow(A,i*m,N) = (B*pow(A,j,N))%N from math import sqrt modN = 2**0xff - 19 h = 25**10 # h = 500000 A = 9230197858975018299629857977411527954550899478307510809210520967346958600039 B = 100 # B = 44538647650896514177408629345693026943093157699461094435091792916255681649098 m = int(sqrt(h)+1) lookup = {} for j in range(0,m): if j%10000==0: print(j) t = (B*pow(A,j,modN))%modN lookup[t] = j print(len(lookup)) for i in range(1,m+2): if i%10000==0: print(i) t = pow(A,i*m,modN) if t in lookup: print(i,lookup[t],m*i-lookup[t]) break
解第一部分:
ans = 79821823136933 base25 = [] t = ans while t: base25.append(t%25) t = t//25 # print(base25) table = [88,91,90,93,92,95,94,81,82,83,80,85,84,87,86,73,72,75,74,77,76,79,78,64,67,65] lookup = {} for i in range(26): lookup[i] = chr(table[i]^0x19) s = '' for n in base25: s += lookup[n] s = s[:-1] + chr(ord(s[-1])-10) print(s)
第一部分为:KCTFREADYK
wolframalpha解方程:
t^2 + 64t^4 + 3 = 355419490699766887897429(mod 2**255-19)
解得:t = 1548396171915056368526513804948765619094392315806578106376668805448390390825
故第二部分为:
t+355419490699766887897429 =1548396171915056368526513804948765619094392315806578461796159505215278288254
完整的key:KCTFREADYKXXXX1548396171915056368526513804948765619094392315806578461796159505215278288254
[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课
最后于 2019-6-23 21:52
被mratlatsn编辑
,原因:
赞赏
他的文章
看原图