-
-
[原创] 看雪 2023 KCTF 年度赛 第五题 争分夺秒
-
发表于: 2023-9-13 03:30 10072
-
IDA看伪代码,虽然每个函数都有成百上千行,但中间大多都是无用的死代码。沿着数据流追踪输入值,能够很容易的找出关键代码。
具体做法,就是在IDA中对变量按x取交叉引用,只看弹出的小窗口的指令,即可排除几乎所有的垃圾代码。
然后,逐个函数梳理逻辑,全部完成重命名:
具体的还原结果如下:
从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结构体(见前面的定义),具体逻辑如下:
struct struc_1由8字节的头部和不定长度的buf组合而成。其中前4字节解析为一个整数seed,然后2个字节指示后面buf的长度len,再2个字节被忽略,后面是长度为len的字节串buf。extract_two_structs(sub_458D90)的处理只是做一些长度检查,然后直接把Block强制转换为结构体类型。
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)
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)下断点观察。
check的最后是check_two_buffer检查两个buf。其中buf是一个小端序表示的十六进制大数,检查逻辑同check_two_seed相同,仍然是要求buf作为一个大数与常数模乘常数后等于1。
这里重点是识别出大数运算。一个方法是先从加减乘入手,例如bignum_mul(sub_43C130)的某个循环里有这样的片段:
两个大数从低位开始,对应位相乘(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异或的值)
最终答案:
多解:按照上面的分析,首先seed在DWORD范围内有不止一种取值,其次struct struc_1的两字节_padding可以任意取值,再者buf的长度并没有严格限制,可以在高位补零。三个条件随便改变一点都会产生一个新的解,因此题目有无数个多解。例如,KmJTMUoAAAD1UMTRG+iFRaF+30mmANMCEqF3YPgU8FTyUvX6yePJFbEZXZ8tUvO70stWkJgshd+8oMQQITLP8l5HQPPJxxF0gCxZp/r5ja68Up2kckNKAAABVESbyOlxOm8t5prM6tsrtV9VApTX9NiH1WHIWMEtdKohjkV2bQeZORqMYX9eP7AP1JlenlB3EAchhYJhoiP7R3NzbOYCcnXnqeyDKnjw
。
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
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
struct
struc_1
{
_DWORD seed;
_WORD len;
_WORD _padding;
_BYTE buf[0];
};
struct
struc_1
{
_DWORD seed;
_WORD len;
_WORD _padding;
_BYTE buf[0];
};
// sub_47B430
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;
}
// sub_47B430
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;
}
// sub_458D90
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;
}
// sub_458D90
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;
}
// sub_474170
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;
}
// sub_4C2AB0
__int64
__cdecl get_const_1(_QWORD *a1)
{
*a1 = 879724311i64;
return
32069i64;
}
// sub_4C3AC0
__int64
__cdecl get_const_2(_QWORD *a1)
{
*a1 = 1922656767i64;
return
55057i64;
}
// sub_4CE450
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;
}
// sub_474170
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;
}
[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!