首页
社区
课程
招聘
[原创] 看雪 2023 KCTF 年度赛 第五题 争分夺秒
2023-9-13 03:30 9656

[原创] 看雪 2023 KCTF 年度赛 第五题 争分夺秒

2023-9-13 03:30
9656

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
// 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;
}

从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
// 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;
}

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
// 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;
}

check_two_dword(sub_474170)检查了两个seed的正确性,检查逻辑分别是 32069 * seed1 % 879724311 == 155057 * seed2 % 1922656767 == 1。这里直接求模逆即可得到两个seed的值:8275482021131586717。(但是,在_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
// sub_45F640
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 == 12207598431 * buf2 % 11504884415388796500219489938877037570907236266221216736789242959943502559932358261444533399595441834388023078747736743001176901105009843107005500447845023069935116586106537423621 == 1,求解结果分别为69566540538004992303262906991743235960880817671473134656484063509711871226552440551525480056258662162419049926543645533163218285142129846333519217220439902611100669705421675783776030658962721950361155533835702172940609579189992003760553378343560660612412076910216892955114510943618804706539422649399614037254978869753190882492376528406540173851407196912984


综合以上分析,可以得到正确的输入:(其中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 = bxx
# key2 = byy
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)
# print(s.hex())
 
r = base64.b64encode(s)
 
print(r)

最终答案:

1
KmJTMUoAAAD1UMTRG+iFRaF+30mmANMCEqF3YPgU8FTyUvX6yePJFbEZXZ8tUvO70stWkJgshd+8oMQQITLP8l5HQPPJxxF0gCxZp/r5ja68Up2kckNKAAAAVESbyOlxOm8t5prM6tsrtV9VApTX9NiH1WHIWMEtdKohjkV2bQeZORqMYX9eP7AP1JlenlB3EAchhYJhoiP7R3NzbOYCcnXnqewe7SYM

多解:按照上面的分析,首先seed在DWORD范围内有不止一种取值,其次struct struc_1的两字节_padding可以任意取值,再者buf的长度并没有严格限制,可以在高位补零。三个条件随便改变一点都会产生一个新的解,因此题目有无数个多解。例如,KmJTMUoAAAD1UMTRG+iFRaF+30mmANMCEqF3YPgU8FTyUvX6yePJFbEZXZ8tUvO70stWkJgshd+8oMQQITLP8l5HQPPJxxF0gCxZp/r5ja68Up2kckNKAAABVESbyOlxOm8t5prM6tsrtV9VApTX9NiH1WHIWMEtdKohjkV2bQeZORqMYX9eP7AP1JlenlB3EAchhYJhoiP7R3NzbOYCcnXnqeyDKnjw


[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

收藏
免费 2
打赏
分享
最新回复 (1)
雪    币: 20925
活跃值: (30213)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
秋狝 2023-9-15 09:52
2
1
感谢分享
游客
登录 | 注册 方可回帖
返回