IDA看伪代码，虽然每个函数都有成百上千行，但中间大多都是无用的死代码。沿着数据流追踪输入值，能够很容易的找出关键代码。
具体做法，就是在IDA中对变量按x取交叉引用，只看弹出的小窗口的指令，即可排除几乎所有的垃圾代码。
然后，逐个函数梳理逻辑，全部完成重命名：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | 00401000 antidebug1
00401870 antidebug2
00402220 antidebug_should_always_return_0
00402690 strlen_
00404DA0 is_digit_or_charactor
00407E40 is_valid_base64_char
004082F0 base64_decode_char
0040A580 base64_decode
0041F1A0 bzero_
0041F1D0 memcpy__
0041F210 bignum_neg
00421970 bignum_get_number_count
00423810 bignum_new
00423E80 bignum_free
004253C0 bignum_zero
00426150 bignum_from_int64
00427790 memcpy_
00429980 bignum_copy
0042A290 bignum_cmp
0042ED20 bignum_cmp_with_int64
00430670 bignum_check_is_zero
004323F0 bignum_byte_shl
00437AA0 bignum_add
0043B150 bignum_sub
0043C130 bignum_mul
00444F30 bignum_divmod
0044EA60 bignum_mod
0044FFB0 crc32_internal
00453B90 crc32
00455F70 sub_455F70
00455F80 check_last_four_bytes
00458D90 extract_two_structs
0045F640 check_two_buffer
00474170 check_two_dword
0047B430 check
0048BBB0 initialize_const_mul_number_and_mod_bignum_1
004A7F90 initialize_const_mul_number_and_mod_bignum_2
004C2AB0 get_const_1
004C3AC0 get_const_2
004C50C0 check_mul_mod_equals_to_1_
004CE450 check_mul_mod_equals_to_1
004D2250 alloc_square
004D45A0 set_square_value
004D6450 get_square_value
004D76B0 initialize_square
004DF410 shuffle_square
004E1620 xor_buf_value
004E7300 bzero__
004E7FE0 do_malloc
004E81E0 do_free_
004E8D70 do_srand
004EACB0 do_rand
004EB910 _main
|
具体的还原结果如下：
1 2 3 4 5 6 7 | struct struc_1
{
_DWORD seed;
_WORD len;
_WORD _padding;
_BYTE buf[0];
};
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | int __cdecl check(char *a1)
{
_BYTE *Block;
unsigned int b64decode_len;
struct struc_1 *v1298;
struct struc_1 *v1297;
if ( base64_decode(a1, &Block, &b64decode_len) )
{
if ( check_last_four_bytes(Block, b64decode_len) )
{
if ( extract_two_structs(Block, b64decode_len - 4, &v1298, &v1297) )
{
if ( check_two_dword(v1298->seed, v1297->seed) )
{
xor_buf_value(v1298->seed, v1298->buf, v1298->len);
xor_buf_value(v1297->seed, v1297->buf, v1297->len);
if ( check_two_buffer(v1298->buf, v1298->len, v1297->buf, v1297->len) )
{
return 1;
}
}
}
}
}
return 0;
}
|
从main函数入手，第一个调用的函数是check(sub_47B430)函数，然后是base64解码（这一步只要跟进base64_decode(sub_40A580)函数，注意到is_valid_base64_char(sub_407E40)对字符合法性的检查（有'+'和'/'），以及base64_decode_char(sub_4082F0)函数访问了0x4FBD18的base64编码表，应该能立刻反应过来，也可以结合动态调试再确认一下）。
之后，对解码后的Block变量取交叉引用，发现如果antidebug_should_always_return_0(sub_402220)函数（这个函数非常短，里面调用了antidebug1和antidebug2，通过一些常见方法检查了调试器是否附加）没有返回0，则会对它加一些rand随机值的操作。为了方便后续调试，可以直接把antidebug_should_always_return_0 patch为永远返回0。
继续，Block首先被分为了末尾4个字节和前面的字节，check_last_four_bytes(sub_455F80)函数调用了crc32(sub_453B90)对前面的字节计算crc32，然后与末尾4个字节比较。（如何确定是crc32？首先，crc32(sub_453B90)函数对参数取交叉引用有 v104 = v162[(unsigned __int8)(v104 ^ a1[i9])] ^ (v104 >> 8); ，然后对v162取交叉引用找到crc32_internal(sub_44FFB0)，通过交叉引用看到有计算式 v187 = (v187 >> 1) ^ 0xEDB88320;。这两个算式和常量显然是crc32。当然，仍然可以通过动态调试进一步确认。）
下一步，extract_two_structs(sub_458D90)函数把Block的前面字节解析为两个struct struc_1结构体（见前面的定义），具体逻辑如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | int __cdecl extract_two_structs(_BYTE *a1, signed int a2, struct struc_1 **a3, struct struc_1 **a4)
{
if ( (unsigned int)a2 >= 0x10 )
{
*a3 = (struct struc_1 *)a1;
if ( (*a3)->len && (*a3)->len <= (unsigned int)(a2 - 16) )
{
*a4 = (struct struc_1 *)&a1[(*a3)->len + 8];
if ( (*a4)->len && (*a4)->len <= a2 - 16 - (unsigned int)(*a3)->len )
{
return 1;
}
else
{
*a4 = 0;
}
}
else
{
*a3 = 0;
}
}
return 0;
}
|
struct struc_1由8字节的头部和不定长度的buf组合而成。其中前4字节解析为一个整数seed，然后2个字节指示后面buf的长度len，再2个字节被忽略，后面是长度为len的字节串buf。extract_two_structs(sub_458D90)的处理只是做一些长度检查，然后直接把Block强制转换为结构体类型。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | int __cdecl check_two_dword(unsigned int a1, unsigned int a2)
{
_DWORD v342;
_QWORD v599;
v342 = 0;
v599 = 0i64;
v342 = get_const_1(&v599);
if ( check_mul_mod_equals_to_1(v342, a1, v599) )
{
v342 = get_const_2(&v599);
if ( check_mul_mod_equals_to_1(v342, a2, v599) )
{
return 1;
}
}
return 0;
}
__int64 __cdecl get_const_1(_QWORD *a1)
{
*a1 = 879724311i64;
return 32069i64;
}
__int64 __cdecl get_const_2(_QWORD *a1)
{
*a1 = 1922656767i64;
return 55057i64;
}
int __cdecl check_modpow_equals_to_1(__int64 a1, __int64 a2, unsigned __int64 a3)
{
_QWORD v230;
v230 = a1 * a2;
if ( v230 % a3 == 1 )
{
return 1;
}
return 0;
}
|
check_two_dword(sub_474170)检查了两个seed的正确性，检查逻辑分别是 32069 * seed1 % 879724311 == 1 和 55057 * seed2 % 1922656767 == 1。这里直接求模逆即可得到两个seed的值：827548202 和 1131586717。（但是，在_DWORD的范围内实际上并非唯一，因为加上模数的倍数不影响等式，不过这里的多解很少，暂时不用考虑）。
（p.s. Python3.8以上版本的内置pow函数支持模逆运算，所以只要 pow(32069, -1, 879724311) 即可得到827548202，无需第三方库(如gmpy2等)或自己写egcd）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | void __cdecl xor_buf_value(unsigned int Seed, _BYTE *buf, int len)
{
char square_value;
_DWORD *square;
int const_16;
int v257;
int v257;
int i_;
const_16 = 16;
initialize_square(const_16, &square);
shuffle_square(square, const_16, Seed);
v257 = 0;
v257 = 0;
i_ = 0;
while ( i_ < len )
{
square_value = get_square_value(square, const_16, v257, v278);
buf[i_] ^= square_value;
if ( !(i_ % const_16) )
{
++v257;
v278 = 0;
}
++v278;
}
}
|
check函数随后对两个buf各自做了xor_buf_value(sub_4E1620)，根据输入的seed初始化了srand种子(在shuffle_square往下的某个很深层的函数中)，然后多次调用rand生成了一个16*16的随机二维数组，然后循环取值与buf的每个字节异或。
由于前面有check_two_dword(sub_474170)对seed的检查，所以这里的seed可以认为是常量，因此无需逆向square的生成过程，只需要动态调试获取最终与buf异或的值即可完成逆向。
注意这里的细节，check(sub_47B430)函数对v1298->buf实际上调用了3次xor_buf_value(sub_4E1620)，前后的垃圾代码中还穿插了成对的循环异或。虽然化简后等同于只做了一次xor_buf_value(sub_4E1620)的异或，但是如果在这里下断点看到的值并不等于输入，最好在后面的check_two_buffer(sub_45F640)下断点观察。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | int __cdecl check_two_buffer(_BYTE *buf1, int buf1_len, _BYTE *buf2, int buf2_len)
{
memcpy_(buf, buf1, buf1_len);
a_const_int = initialize_const_mul_number_and_mod_bignum_1(&a_length_74_const_bignum, &v1463);
memcpy_(a_length_74_const_bignum_, a_length_74_const_bignum, v1463);
bignum_from_int64(Block, a_const_int);
if ( check_mul_mod_equals_to_1_(Block, buf, a_length_74_const_bignum_) )
{
memcpy_(buf, buf2, buf2_len);
a_const_int = initialize_const_mul_number_and_mod_bignum_2(&a_length_74_const_bignum, &v1463);
memcpy_(a_length_74_const_bignum_, a_length_74_const_bignum, v1463);
bignum_from_int64(Block, a_const_int);
if ( check_mul_mod_equals_to_1_(Block, buf, a_length_74_const_bignum_) )
{
return 1;
}
}
return 0;
}
|
check的最后是check_two_buffer检查两个buf。其中buf是一个小端序表示的十六进制大数，检查逻辑同check_two_seed相同，仍然是要求buf作为一个大数与常数模乘常数后等于1。
这里重点是识别出大数运算。一个方法是先从加减乘入手，例如bignum_mul(sub_43C130)的某个循环里有这样的片段：
1 2 3 4 5 6 7 8 9 10 11 12 13 | ...
v494 = 0;
...
while ( v589 < v210 )
{
...
v287 = v494 + a2[v589] * a1[i57];
Block[i57 + v589] = (_BYTE)v287;
v494 = v287 & 0xFF00;
v494 >>= 8;
...
}
...
|
两个大数从低位开始，对应位相乘(a2[v589] * a1[i57])，然后加上进位(v494)，所得结果的低位存储在当前位置，高位右移作为下一位的进位，这是典型的高精度乘法的计算过程。
而除法的流程一般是先检查除数是否为0，然后从高位开始对齐做减法，然后向右移位，如此循环直到低位，返回商和余数。bignum_divmod(sub_444F30)完全包含以上的所有流程，它的前两个参数分别是被除数和除数，后两个参数是输出的商和余数。
常数提取自initialize_const_mul_number_and_mod_bignum_1(sub_48BBB0)和initialize_const_mul_number_and_mod_bignum_2(sub_4A7F90)。参照get_const_1(sub_4C2AB0)和get_const_2(sub_4C3AC0)，其返回值应该是乘数，模数则通过第一个参数指针带出，模数的位数由第二个参数指针带出。通过交叉引用很容易找出这些常量，其中模数是长为74字节的大数。
两个检查式分别为 2865244763 * buf1 % 13407712312341506807290785620513810006013432881349817380059896195876647865383040511615194818142561216049323742693301651262826523009904773019126031607880381917510353811872243158275 == 1 和 2207598431 * buf2 % 11504884415388796500219489938877037570907236266221216736789242959943502559932358261444533399595441834388023078747736743001176901105009843107005500447845023069935116586106537423621 == 1，求解结果分别为6956654053800499230326290699174323596088081767147313465648406350971187122655244055152548005625866216241904992654364553316321828514212984633351921722043990261110066970542167578377和6030658962721950361155533835702172940609579189992003760553378343560660612412076910216892955114510943618804706539422649399614037254978869753190882492376528406540173851407196912984。
综合以上分析，可以得到正确的输入：（其中key1和key2是xor_buf_value函数中与buf异或的值）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | import base64
import zlib
def i2b(n, count = None):
if not count:
count = (n.bit_length()+7) // 8
return n.to_bytes(count, 'little')
def bxor(a, b):
assert len(a) == len(b)
return bytes(x^y for x,y in zip(a,b))
seed1 = 827548202
seed2 = 1131586717
xx = 6956654053800499230326290699174323596088081767147313465648406350971187122655244055152548005625866216241904992654364553316321828514212984633351921722043990261110066970542167578377
yy = 6030658962721950361155533835702172940609579189992003760553378343560660612412076910216892955114510943618804706539422649399614037254978869753190882492376528406540173851407196912984
bseed1 = i2b(seed1, 4)
bseed2 = i2b(seed2, 4)
bxx = i2b(xx)
byy= i2b(yy)
key1 = bytes.fromhex("FC 07 AC BD 91 E9 5C 33 95 E5 C3 D0 FE 3E 0F 6E 86 2B 36 B2 3A 35 58 1C 68 32 0E C1 66 75 A5 4F 3B 4A 29 54 B1 B9 6A DA CE A3 B7 AB 16 9C 2D 72 B4 BA C4 AF DC 24 11 31 A1 70 B3 20 69 A6 0D 50 3C 5A 6F EE 6B 18 1D 59 62 3F")
key2 = bytes.fromhex("0C 39 C7 CA A2 4B AA 71 CD 3E BA E3 1F DC 29 91 3D 63 81 DF 2E 6F FD 25 68 E4 7D B2 26 BB 73 79 5F 75 56 E2 ED C5 8D C9 8B AC 13 A6 C3 0D EA 6B 11 76 52 93 77 0B 65 5E B5 8F 3C 6C 99 51 09 5C 38 66 A5 A7 88 E9 AD E6 96 B3")
bxxx = bxor(bxx, key1)
byyy = bxor(byy, key2)
tmp1 = bseed1 + i2b(len(bxx), 2) + b'\0\0' + bxxx
tmp2 = bseed2 + i2b(len(byy), 2) + b'\0\0' + byyy
crc = zlib.crc32(tmp1+tmp2)
s = tmp1+tmp2+i2b(crc, 4)
r = base64.b64encode(s)
print(r)
|
最终答案：
1 | KmJTMUoAAAD1UMTRG+iFRaF+30mmANMCEqF3YPgU8FTyUvX6yePJFbEZXZ8tUvO70stWkJgshd+8oMQQITLP8l5HQPPJxxF0gCxZp/r5ja68Up2kckNKAAAAVESbyOlxOm8t5prM6tsrtV9VApTX9NiH1WHIWMEtdKohjkV2bQeZORqMYX9eP7AP1JlenlB3EAchhYJhoiP7R3NzbOYCcnXnqewe7SYM
|
多解：按照上面的分析，首先seed在DWORD范围内有不止一种取值，其次struct struc_1的两字节_padding可以任意取值，再者buf的长度并没有严格限制，可以在高位补零。三个条件随便改变一点都会产生一个新的解，因此题目有无数个多解。例如，KmJTMUoAAAD1UMTRG+iFRaF+30mmANMCEqF3YPgU8FTyUvX6yePJFbEZXZ8tUvO70stWkJgshd+8oMQQITLP8l5HQPPJxxF0gCxZp/r5ja68Up2kckNKAAABVESbyOlxOm8t5prM6tsrtV9VApTX9NiH1WHIWMEtdKohjkV2bQeZORqMYX9eP7AP1JlenlB3EAchhYJhoiP7R3NzbOYCcnXnqeyDKnjw。
[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界
