-
-
[原创] 第八题 薛定谔之猫 WriteUp
-
2018-7-1 19:51 2826
-
Pediy CTF 2018 - 薛定谔之猫 WriteUp
首先拿到程序,发现程序非常的复杂,IDA反编译代码中存在很多函数传进去了63个参数,猜测应该是将一个很大的对象直接传了进去。
首先发现程序里有奇怪的一个handler:
v11 = a1 ^ 0x1F2E3D00; if ( a3 == 523124224 ) return a2 ^ 0x1F2E3D00; v13 = a4; v14 = a4; if ( v11 ) { v13 = (int (__stdcall *)(int))hash((int)a4, v11 - (_DWORD)a4, 0); v14 = v13; } if ( !v13 ) return hash((int)a4, v11 - (_DWORD)a4, dword_40F1B8[(unsigned __int8)a3]); switch ( (unsigned __int8)(a3 ^ dword_40F3B8[((unsigned int)v13 >> 8) & 0xF]) ) { case 2u: result = v14(a5); break; case 3u: result = ((int (__stdcall *)(int, int))v14)(a5, a6); break; case 4u: result = ((int (__stdcall *)(int, int, int))v14)(a5, a6, a7); break; case 5u: result = ((int (__stdcall *)(int, int, int, int))v14)(a5, a6, a7, a8); break; case 6u: result = ((int (__stdcall *)(int, int, int, int, int))v14)(a5, a6, a7, a8, a9); break; case 7u: result = ((int (__stdcall *)(int, int, int, int, int, int))v14)(a5, a6, a7, a8, a9, a10); break; case 8u: result = ((int (__stdcall *)(int, int, int, int, int, int, int))v14)(a5, a6, a7, a8, a9, a10, a11); break; default: result = ((int (*)(void))v14)(); break; } return result; }
将第一个参数先与固定值异或,作为起始地址,然后带着起始地址和长度进入一个哈希函数,计算出哈希值后跳转过去。这里可以发现,被哈希的字节在代码段中,所以用0xCC做软件断点的调试方法在这里行不通,需要使用硬件断点来将程序断下。当然,也可以人工计算出哈希值,然后patch掉这个函数,用正确的函数替换。
经过很多次的调试,发现程序中操作的那个巨大的对象,实际上是一个任意进制大整数的对象。定义大概是这样:
__int32 base; // 进制 __int32 is_invalid; // 是否正常,是则0 __int32 length; // 长度 __int8 is_negative; // 是否是负数,是则1 __int8 buf[0x200]; // 内容
一段一段地看程序:
v155 = &v111; system(aCls); v3 = 0; v135 = 0; memset(&v136, 0, 0x60u); v137 = 0; v138 = 0; printf((int)&unk_40F170, (int)s1); fgets(&v135, 100, &stru_40F418); v4 = strlen(&v135); if ( v4 > 0 ) { v5 = *(&v134 + v4); v6 = &v134 + v4; if ( v5 == 10 ) *v6 = 0; } result = handler( 0x1F6E1EC3, 0x4A4EBD2C, 0x6787, (int (__stdcall *)(int))byte_40143C, (int)&v135, strlen(&v135), v111, v112, v113, v114.base, v114.invalid); // 4013c0 -> 是否是字母数字 if ( !result ) return result; v8 = (num *)operator new(0x210u); if ( v8 ) { LOBYTE(v8->invalid) = 0; v8->base = 256; v8->is_negative = 0; v8->length = 0; v3 = v8; memset(v8->num_buf, 0, 0x200u); } v147 = (int)v3; result = (unsigned __int8)init_num_by_str( v3, &v135, strlen(&v135), strlen(a0123456789abcd), (int)a0123456789abcd, 45, 43); v154 = (num *)result;
读入最长100字节的Flag,判断是否为字母数字,然后以01234……ABCD……abcd……为字符集,将Flag作为62进制数储存。
LOBYTE(result) = result != 0; if ( !(_BYTE)result ) return result; v9 = v3->base; if ( v3->base < 2u || v9 > 0x100 ) return result; v10 = v3->length; for ( result = 0; result < v10; ++result ) { if ( (unsigned __int8)v3->num_buf[result] >= v9 ) return result; } v11 = (num *)handler( 0x1F6E1EA0, -655007228, 2, (int (__stdcall *)(int))&loc_40158E, v111, v112, v113, v114.base, v114.invalid, v114.length, *(int *)&v114.is_negative); // 返回0x100 v12 = v3->base; v13 = v3->base == (_DWORD)v11; v148 = v11; if ( !v13 ) { v149 = v3->is_negative; a3 = 1; init_num_by_buf(&v131, v12, &a3, 1u, 0); init_num_by_buf(&v129, (int)v11, &a3, 1u, 0); v14 = (int)&v11->base + 1; v15 = (num *)operator new(528 * v14); lpMem = v15; v156 = 0; if ( v15 ) { v151 = v15; if ( v14 - 1 >= 0 ) { v154 = (num *)v14; do { new_empty_num(v151); v13 = v154 == (num *)1; v151 = (num *)((char *)v151 + 528); v154 = (num *)((char *)v154 - 1); } while ( !v13 ); } } else { v15 = 0; } v152 = v15; v156 = -1; v16 = (num *)operator new(528 * v14); v154 = v16; v156 = 1; if ( v16 ) { loop_function_call((int)v16, 528, v14, (int (__thiscall *)(int))new_empty_num); v17 = v154; } else { v17 = 0; } v18 = v148; v15->base = v3->base; v15->is_negative = 0; lpMem = v17; v156 = -1; v17->base = (int)v18; v17->is_negative = 0; if ( v14 > 1 ) { v151 = (num *)((char *)v15 + 528); v19 = v17; v144 = (char *)((char *)v15 - (char *)v17); v154 = (num *)(v14 - 1); do { qmemcpy(&v110, &v131, 0x210u); v20 = add_num((num *)((char *)v19 + (_DWORD)v144), &a2, v110); qmemcpy(v151, v20, 0x210u); v142 = (num *)((char *)v19 + 528); qmemcpy(&v108, &v129, 0x210u); v21 = add_num(v19, &a6, v108); v19 = v142; v22 = v21; v23 = v154; qmemcpy(v142, v22, 0x210u); v151 = (num *)((char *)v151 + 528); v154 = (num *)((char *)v23 - 1); } while ( v23 != (num *)1 ); } v24 = v147; qmemcpy(&a1, (const void *)v147, 0x210u);
这个神奇的handler居然还有返回某个数的功能……这里返回的是0x100。
这里的作用是在内存中生成了一个1-256的表,存1-256这些数字作为256进制大整数。
new_empty_basen_num(&v132, (int)v148, 0); qmemcpy(&v107, v152, 0x210u); v144 = 0; if ( cmp_num(&a1, v107) ) { v154 = (num *)((char *)v152 + 528 * (_DWORD)v148); do { qmemcpy(&v106, v154, 0x210u); mod_num(&a1, v24, (int)&savedregs, (int)&v109, (int)&v154[1].num_buf[246], (int)&v127, v106); v24 = 0; if ( v148 ) { v151 = v152; while ( 1 ) { qmemcpy(&v104, v151, 0x210u); if ( !cmp_num(&v127, v104) ) break; ++v24; v151 = (num *)((char *)v151 + 528); if ( v24 >= (unsigned int)v148 ) goto LABEL_34; } qmemcpy(&v126, (char *)lpMem + 528 * v24, 0x210u); qmemcpy(&v103, &v127, 0x210u); qmemcpy(&a1, minus_num(&a1, &a2, v103), 0x210u); qmemcpy(&v102, v154, 0x210u); v101 = &a6; qmemcpy( &a1, (const void *)div_num(&a1, v24, (int)&savedregs, (int)&v105, (int)&v154[1].num_buf[246], *(num *)&v101), 0x210u); v25 = v144; sub_402B40((int)&v126, (signed int)v144); v144 = v25 + 1; qmemcpy(&v91, &v126, 0x210u); qmemcpy(&v132, add_num(&v132, &v124, v91), 0x210u); } LABEL_34: qmemcpy(&v90, v152, 0x210u); } while ( cmp_num(&a1, v90) ); v24 = v147; } v26 = v149; qmemcpy((void *)v24, &v132, 0x210u); *(_BYTE *)(v24 + 12) = v26; }
这里标完函数之后,就显得很清晰,经典的进制转换结构,把62进制的Flag转换为256进制bytes。(话说不是有个进制转换的函数吗,为啥不用那个= = )
v27 = (unsigned __int8 *)operator new(0x104u); memset(v27, 0, 0x104u); v145 = v27; result = *(_DWORD *)(v147 + 8); qmemcpy(v27, (const void *)(v147 + 13), result); LOBYTE(result) = *v27; if ( *v27 < 1u ) return result; if ( (unsigned __int8)result > 0x18u ) return result; LOBYTE(v154) = v27[1]; if ( (unsigned __int8)v154 < 1u ) return result; if ( (unsigned __int8)v154 > 0x18u ) return result; v28 = v27[2]; if ( v28 < 1u ) return result; if ( v28 > 0x18u ) return result; v29 = v27[3]; if ( v29 < 1u ) return result; if ( v29 > 0x18u ) return result; result = (unsigned __int8)result; if ( (unsigned __int8)result + 4 != (unsigned __int8)v154 ) return result; result += v27[2] + v27[3] + 8; if ( result != *(_DWORD *)(v147 + 8) ) return result;
这里就开始check了,读出前四个字节,判断范围在(1, 0x18),并且bytes[0] + 4 == bytes[1], bytes[1] + bytes[2] + bytes[3] + 4 == 总长度。
v30 = handler(527310496, 882113057, 0, (int (__stdcall *)(int))&loc_401662, v94, v95, v96, v97, v98, v99, v100); // 返回 0x400 v144 = (char *)operator new(v30); v31 = (num *)operator new(0x210u); v32 = v31; v154 = v31; v156 = 2; if ( v31 ) { v33 = *v145; v31->base = (int)v148; LOBYTE(v31->invalid) = 0; v31->length = v33; v31->is_negative = 0; memset(v31->num_buf, 0, 0x200u); qmemcpy(v31->num_buf, v145 + 4, v33); if ( !check_num(v31) ) LOBYTE(v32->invalid) = 1; lpMem = v32; } else { lpMem = 0; } v93 = 528; v156 = -1; v152 = (num *)*v145; v34 = (num *)operator new(0x210u); v35 = v34; v154 = v34; v156 = 3; if ( v34 ) { v36 = v145[1]; v34->base = (int)v148; LOBYTE(v34->invalid) = 0; v34->length = v36; v34->is_negative = 0; memset(v34->num_buf, 0, 0x200u); qmemcpy(v34->num_buf, v145 + 4, v36); if ( !check_num(v34) ) LOBYTE(v35->invalid) = 1; v151 = v35; } else { v151 = 0; } v156 = -1; v152 = (num *)((char *)v152 + 4); v37 = (num *)operator new(0x210u); v154 = v37; v156 = 4; if ( v37 ) { v38 = v145[2]; v37->base = (int)v148; LOBYTE(v37->invalid) = 0; v37->length = v38; v37->is_negative = 0; memset(v37->num_buf, 0, 0x200u); qmemcpy(v37->num_buf, &v145[(_DWORD)v152 + 4], v38); if ( !check_num(v37) ) LOBYTE(v37->invalid) = 1; v154 = v37; } else { v154 = 0; } v39 = v145[2]; v156 = -1; v142 = v154; v152 = (num *)((char *)v152 + v39); v40 = (num *)operator new(0x210u); v139 = v40; v156 = 5; if ( v40 ) { v41 = v145[3]; v40->base = (int)v148; LOBYTE(v40->invalid) = 0; v40->length = v41; v40->is_negative = 0; memset(v40->num_buf, 0, 0x200u); qmemcpy(v40->num_buf, &v145[(_DWORD)v152 + 4], v41); if ( !check_num(v40) ) LOBYTE(v40->invalid) = 1; v148 = v40; } else { v148 = 0; } v152 = v148; v156 = -1;
这里是按顺序读4段并放到4个大整数对象中。稍微整理一下可以得到这样的结构:(按实际数字顺序)
========================================================= | d | c | (4) | a |len_d|len_c|len_b|len_a| =========================================================
其中a和前面4字节合起来作为b。
init_num_by_str(&num1, s1, strlen(s1), strlen(a0123456789abcd_0), (int)a0123456789abcd_0, 45, 43); init_num_by_str(&num2, ::a2, strlen(::a2), strlen(a0123456789abcd_0), (int)a0123456789abcd_0, 45, 43); v42 = 0; v43 = 0; while ( v43 >= 35 ) { LABEL_72: if ( ++v43 >= 36 ) { if ( *((_BYTE *)lpMem + 12) ) { v42 = 1; *v144 = 45; } qmemcpy(&v132, lpMem, 0x210u); change_base(&v132, 36); v45 = v132.length - 1; for ( i = v144; v45 >= 0; i[v42 - 1] = byte_40F0B0[v47] ) { ++v42; v47 = (unsigned __int8)v132.num_buf[v45--]; } i[v42] = 0; goto LABEL_78; } } v44 = &aBcdefghijklmno[v43]; while ( byte_40F0B0[v43] != *v44 ) { if ( (signed int)++v44 >= 0x40F0D4 ) goto LABEL_72; }
载了固定的两个字符串成64进制大整数,然后将之前的a转换成36进制bytes。
v143 = 100; v141 = 0; v48 = sub_4010A0((int)v144, strlen(v144), 5, &v143, (unsigned int *)&v141); v93 = v141 - 1; v92 = *(_DWORD *)(v147 + 8); lpMem = (LPVOID)handler( 0x1F6E1EA0, 0x13114F0D, 0x6780, (int (__stdcall *)(int))&loc_401ABF, (int)v145, v92, v141 - 1, v94, v95, v96, v97); // -> hash
这里这两个函数比较重要。将a转成的36进制bytes传给4010A0函数,算一下,然后再算一下整个256进制bytes的哈希。
4010A0函数:
v5 = 0; a = (unsigned int *)a4; *a5 = 0; v7 = __5 - 1; *a4 = 0; b = 0; c = 0; if ( __5 - 1 > 0 ) { do { --v7; *a = 2 * (*a | 1); } while ( v7 ); } v28 = 0; v8 = *a | 1; v30 = 0; *a = v8; v9 = v8; v10 = len; v27 = v9; // 0x1f if ( len <= 0 ) return 0; v26 = len; while ( 1 ) { v11 = *(_BYTE *)(v5 + buf); if ( v11 >= 0x41u && v11 <= 0x5Au ) { v12 = v11 - 65; goto LABEL_14; } if ( v11 >= 0x61u && v11 <= 0x7Au ) { v12 = v11 - 97; goto LABEL_14; } if ( v11 >= 0x30u && v11 <= 0x39u ) break; LABEL_42: v30 = ++v5; --v26; if ( v5 >= v10 ) return 0; } v12 = v11 - 22; LABEL_14: v13 = 0; v25 = v12; v29 = 0; while ( 1 ) { v14 = v25 % 6; v31 = v25 % 6; v15 = ((unsigned int)v25 - v14) / 6; v25 = v15; if ( !v13 ) v28 = (unsigned __int8)v15 > 0u; v16 = sub_401080(*a); // 返回最大的2的整数次方的因子 v17 = sub_401080(b); v18 = sub_401080(c); x1 = v16; x2 = v17; x3 = v18; if ( !v16 ) { v14 = v31; x1 = 100; } if ( !v17 ) x2 = 100; if ( !v18 ) x3 = 100; switch ( v14 ) { case 0: if ( x1 >= x2 ) return 0; *a -= v16; b += v16; *a5 = v16; break; case 1: if ( x1 >= x3 ) return 0; c += v16; *a -= v16; *a5 = v16; break; case 2: if ( x2 >= x1 ) return 0; b -= v17; *a += v17; *a5 = v17; break; case 3: if ( x2 >= x3 ) return 0; b -= v17; c += v17; *a5 = v17; break; case 4: if ( x3 >= x1 ) return 0; *a += v18; c -= v18; *a5 = v18; break; case 5: if ( x3 >= x2 ) return 0; c -= v18; b += v18; *a5 = v18; break; default: break; } if ( !--v27 && !*a && v26 == 1 && !v28 ) return 1; v13 = v29 + 1; v22 = __OFSUB__(v29 + 1, 2); v21 = v29++ - 1 < 0; if ( !(v21 ^ v22) ) { v10 = len; v5 = v30; goto LABEL_42; } } }
这个函数我懵逼了很久……一开始将36进制字节转回数字,然后拆成低位和高位,分别扔进那个case里面去做操作……验证要0x1F次操作全部成功完成,v6的值变为0. 这个东西,实际上是一个汉诺塔小游戏。
a b c分别为3根柱子,用二进制位表示每一个权值的盘子(所以取二进制最后一个1,实际上是取到最上的一块盘子),权值小的放在权值大的上面,0x1F刚好是(11111),即5个盘子权值分别为16 8 4 2 1,最少的移动次序正好是31次。用0-5表示6种移动,两次合并为一个36进制字节。
手动玩一玩,得到一个序列:
[1, 0, 5, 1, 2, 3, 1, 0, 5, 4, 2, 5, 1, 0, 5, 1, 2, 3, 1, 2, 5, 4, 2, 3, 1, 0, 5, 1 ,2 ,3, 1]
// 这里似乎存在多解……没有check最后放在第2个还是第3个上
合并相邻的两个操作:(最后多余的一个必须是0)
[1, 11, 20, 1, 29, 32, 1, 11, 20, 13, 29, 20, 1, 11, 20, 1]
转为36进制bytes:
blub36blun3ublub
// 怎么看上去这么正常……怕不是这本来是单独的一道题……
转为数字:
3dd7c4ddec9ae7c5e8c1
这个就是a。
接下来是哈希函数,但是到这里的时候信息明显不足,这里选择暂且patch程序跳过这个check,继续向下分析。
if ( !v48 ) goto GG; init_num_by_int(&v129, 0); qmemcpy(&v87, &v129, 0x210u); if ( !cmp_num(v154, v87) ) goto GG; init_num_by_int(&v129, 0); qmemcpy(&v86, &v129, 0x210u); v49 = cmp_num(v148, v86); if ( v49 == 0 || lpMem != 0 ) goto GG; lpMem = (LPVOID)1; v154 = 0; if ( v141 != 1 ) goto GG; v50 = 3; v156 = 6; v147 = 3; while ( v50 < 10 ) { if ( !v50 ) { v89 = 0; v88 = 1; v51 = v151->base; v149 = 1; init_num_by_buf(&v129, v51, &v149, 1u, 0); qmemcpy(&v130, &v129, 0x210u); LABEL_90: v89 = 0; v88 = 1; v53 = v152->base; a3 = 1; init_num_by_buf(&v120, v53, &a3, 1u, 0); qmemcpy(&v126, &v120, 0x210u); LABEL_95: v89 = 0; v88 = 1; v55 = v142->base; v150 = 1; init_num_by_buf(&v124, v55, &v150, 1u, 0); v56 = &v124; goto LABEL_100; } v52 = 0; qmemcpy(&v132, v151, 0x210u); while ( v52 < v147 - 1 ) { qmemcpy(&v84, v151, 0x210u); ++v52; qmemcpy(&v132, (const void *)mul_num(&v118, v84), 0x210u); } qmemcpy(&v130, &v132, 0x210u); if ( !v147 ) goto LABEL_90; v54 = 0; qmemcpy(&a1, v152, 0x210u); while ( v54 < v147 - 1 ) { qmemcpy(&v84, v152, 0x210u); ++v54; qmemcpy(&a1, (const void *)mul_num(&v115, v84), 0x210u); } qmemcpy(&v126, &a1, 0x210u); if ( !v147 ) goto LABEL_95; v57 = 0; qmemcpy(&v127, v142, 0x210u); while ( v57 < v147 - 1 ) { qmemcpy(&v84, v142, 0x210u); ++v57; qmemcpy(&v127, (const void *)mul_num(&v117, v84), 0x210u); } v56 = &v127; LABEL_100: qmemcpy(&v131, v56, 0x210u); qmemcpy(&v84, &v126, 0x210u); v58 = add_num(&v131, &v116, v84); qmemcpy(&v83, &v130, 0x210u); if ( !cmp_num(v58, v83) ) { v143 = 0; break; } if ( !v143 ) { v140 = 1; _CxxThrowException(&v140, &_TI1H); } init_num_by_int(&a6, v143); v66 = v142; qmemcpy(&v82, &a6, 0x210u); v81 = &a2; div_num(v142, (int)v142, (int)&savedregs, (int)&v85, (int)&v126, *(num *)&v81); qmemcpy(&v79, &a2, 0x210u); if ( !cmp_num(v66, v79) ) v154 = (num *)((char *)v154 + 1); v50 = v147++ + 1; } if ( (signed int)v154 > 10 ) v143 = 0; v156 = -1;
这里乍一看是去check c的立方+d的立方=b的立方,但上过高中的人都知道,这个方程是不存在整数解的。再看下面有个除法,若除数为零则扔出一个异常。如果前面的步骤全部正确,这里这个除数必须为零,即这个异常必须被触发。
看一看Exception Handler结构体,发现是跳到这里:
mov [ebp+lpMem], 2 mov eax, offset loc_40211C retn
显然,就是为下面的lpMem = 2创造条件的。
if ( lpMem == (LPVOID)2 ) { ++v143; qmemcpy(&a2, v152, 0x210u); qmemcpy(&v131, v152, 0x210u); v131.is_negative = a2.is_negative == 0; qmemcpy(&v82, &v131, 0x210u); add_num(v142, &a6, v82); // c-d qmemcpy(&a2, &num2, 0x210u); qmemcpy(&v80, &a2, 0x210u); if ( !cmp_num(&a6, v80) ) { init_num_by_int(&v123, 4); qmemcpy(&v78, &v123, 0x210u); mul_num(&v121, v78); init_num_by_int(&v122, 2); qmemcpy(&v70, &v122, 0x210u); mul_num(&v119, v70); qmemcpy(&v131, &num1, 0x210u); qmemcpy(&v69, &v121, 0x210u); v59 = add_num(&v119, &v114, v69); // 2c+4d qmemcpy(&v130, &v131, 0x210u); if ( v59->base != v131.base ) change_base(&v130, v59->base); v150 = v59->is_negative; v60 = v150; if ( v150 == v130.is_negative ) { v61 = v59->length; v62 = 0; if ( v61 < v130.length ) v61 = v130.length; if ( v61 > 0 ) { v63 = (char *)&v130 - (char *)v59; v64 = v59->num_buf; v154 = (num *)(-13 - (_DWORD)v59); do { v65 = v64[v63]; if ( (unsigned __int8)*v64 >= v65 ) { if ( (unsigned __int8)*v64 > v65 ) v62 = 1; } else { v62 = -1; } ++v64; } while ( (signed int)v154 + (signed int)v64 < v61 ); v60 = v150; } if ( v60 ) v62 = -v62; if ( !v62 ) --v143; } } } if ( !v143 ) return handler(527310531, 880460335, 19168, (int (__stdcall *)(int))&loc_40158E, v71, v72, v73, v74, v75, v76, v77); GG: v67 = 0; v68 = 0; do v67 += v68++; while ( v68 < 3 ); return printf((int)asc_40F0AC, v94); }
这里计算了c+(-d)和2c+4d,然后和之前载入的两个64进制数比较。可以解出c和d。
c = 0x9c5d44875c2a969b2d8d6e76abd1b81a123f9 d = 0x9c5d44875c2a93e24ed0b8784c9260ed63913
这样的话,a c d全部确定,且长度域也确定,剩下4个字节,根据哈希函数返回0确定。
爆破得到:
0x2c2f1ca7
全部连起来得到数字
0x09c5d44875c2a93e24ed0b8784c9260ed6391309c5d44875c2a969b2d8d6e76abd1b81a123f92c2f1ca73dd7c4ddec9ae7c5e8c113130e0a
转为62进制,即为Flag
6OqTbC16uYclIp3aqSoJuSpYO4I9JodXMs1oaaI40wwzue79rqVxXflyoZeLxs3Q1yxO1yUoz06