首页
论坛
课程
招聘
[原创]看雪 2022 KCTF 春季赛 第二题 末日邀请
2022-5-12 01:26 5165

[原创]看雪 2022 KCTF 春季赛 第二题 末日邀请

2022-5-12 01:26
5165

直接拖入IDA。
整个程序的对输入的检查分为几个部分。

第一部分

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
...
  scanf("%s", (char)inputvalue);
  printf("\n现在,你就是韩立,韩立就是你,如遇绝境,吼:男人至死是少年!", v33);
  inputvalue[41] = 0;
  inputlen = strlen(inputvalue);
  v5 = 0;
  inputlen2 = inputlen;
  v6 = inputlen;
  v72 = 0;
  if ( inputlen )
  {
    v7 = inputvalue;
    do
    {
      v5 ^= *v7;
      --v6;
      ++v7;
      v8 = 8;
      do
      {
        v9 = 2 * v5;
        v10 = v9 ^ 7;
        if ( v9 >= 0 )
          v10 = v9;
        v5 = v10;
        --v8;
      }
      while ( v8 );
    }
    while ( v6 );
    inputlen = inputlen2;
    v72 = v10;
  }
  init_crctable();
  v11 = -1;
  for ( i = 0; i < inputlen; ++i )
    v11 = crctable[(unsigned __int8)(v11 ^ inputvalue[i])] ^ (v11 >> 8);
  v67 = ~v11;
...

获取输入长度,然后计算crc32的值(略有修改,标准crc32里的无符号右移在本程序中是有符号右移)
main函数末尾对这个值有检查:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
...
    if ( v67 == 0xF52E0765 )
    {
      printf("\n你一如既往的谨慎,哪怕屠龙在手.........", v61);
      printf(
        "\n"
        "十年后,你终于干掉了赤月恶魔,肃清了赤月邪教,获得了 赤月套装 .\n"
        "恭喜你,少年,你成功了\n"
        "恭喜你,少年,你成功了\n"
        "恭喜你,少年,你成功了\n"
        "恭喜你,少年,你成功了\n"
        "恭喜你,少年,你成功了\n"
        "恭喜你,少年,你成功了\n"
        "恭喜你,少年,你成功了\n"
        "恭喜你,少年,你成功了.",
        v62);
    }
...

第二部分

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
...
  hex_to_int(inputvalue, inputlen);
  v13 = v72;
  v69 = 1;
  v68 = v72 + 1;
  v14 = v68;
  do
  {
    v15 = v13;
    for ( j = 1; j < 200; ++j )
    {
      if ( (v15 & 1) != 0 )
        v15 = 3 * v15 + 1;                      // 3n+1
      else
        v15 >>= 1;
      v66[j] = v15;
    }
    ++v13;
  }
  while ( v13 < v14 );
  v17 = v66[198] | v66[197] | v66[196];         // 4 | 2 | 1 == 7
  v18 = inputlen2;
  if ( v17 != (inputvalue[2] ^ inputvalue[1] ^ inputvalue[0]) )
  {
    printf("\n%s", (char)"你深深明白那些裤衩人在做什么,时不我待.");
    printf(
      "\n%s\n%s",
      (char)"你加入了他们,前世作为高知识分子,你深深明白,赤手空拳的你,肯定不是鹿的对手.");
    printf(
      "\n%s",
      (char)"虽然前世没有被酒色掏空了身体(没那个钱财).但是经常加班的你,灵魂里面根本没有动手能力这个概念.");
    printf("\n%s", (char)"大公鸡攻击了你的小公鸡,GAME OVER ...");
    goto LABEL_57;
  }
...

计算3n+1猜想,由于最后必定落入4->2->1->4的循环,因此 v17 = v66[198] | v66[197] | v66[196] 的值一定等于 4 | 2 | 1 = 7
动态调试发现,v72受所有输入字符的影响,导致循环中的v15可能为负数,只能落入-1 -> -2 -> -1的循环,这显然不是正确答案。

第三部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
...
  const_9 = v17 + 2;
  v20 = v18 - const_9 - 7;
  if ( inputvalue[3] != 20 )                    // chr(20+55) = 'K'
  {
...
  if ( inputvalue[4] != 12 )                    // 'C'
  {
...
  if ( inputvalue[5] != 29 )                    // 'T'
  {
...
  if ( inputvalue[6] != 15 )                    // 'F'
  {
...

确定输入的第3-6个字符是"KCTF"。由第二部分,可以认为在正确的输入下v17是常量7。

第四部分

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
...
  v21 = 0;
  inputlen2 = 0;
  if ( const_9 > 0 )
  {
    v22 = 1;
    do
    {
      v23 = inputvalue[v22 + 6] + 10 * v70;
      v24 = v23 - 926365495;
      if ( v23 <= 1262703685 )
        v24 = v23;
      v70 = v24;
      if ( v24 % v69 )
        goto LABEL_50;
      v21 = inputlen2 + 1;
      v22 = v69 + 1;
      inputlen2 = v21;
      ++v69;
    }
    while ( v21 < const_9 );
  }
  if ( v21 != const_9 )
  {
...

迭代输入的第7-15位共九个数字,将其逐渐加位转换为整数,然后验证能被位数整除。由于位数不超过9,所以v23 <= 1262703685的条件永远不会成立。
这个校验的Python等价代码:

1
2
3
4
5
6
7
def checknum(s : str):
    assert len(s) == 9
    for i in range(1, 10):
        n = int(s[:i])
        if n % i:
            return False
    return True

容易发现在数位长度为偶数时除数也是偶数,因此偶数位必须都是偶数才有可能整除。

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
...
  v25 = const_9 - 1;
  if ( const_9 - 1 > 0 )
  {
    v26 = const_9 - 1;
    do
    {
      v27 = 0;
      if ( v25 > 0 )
      {
        do
        {
          v28 = inputvalue[v27 + 7];
          v29 = inputvalue[v27 + 8];
          if ( v28 > v29 )
          {
            inputvalue[v27 + 7] = v29;
            inputvalue[v27 + 8] = v28;
          }
          ++v27;
        }
        while ( v27 < v25 );
        v3 = 0;
      }
      --v25;
      --v26;
    }
    while ( v26 );
  }
  hex_to_int("1234567890_ABCDEFGHIJKLMNOPQRSTUVWXYZ", const_9);
  v30 = 0;
  if ( const_9 > 0 )
  {
    while ( a1234567890Abcd[v30] == inputvalue[v30 + 7] )
    {
      if ( ++v30 >= const_9 )
        goto LABEL_41;
    }
    goto LABEL_49;
  }
...

这里对第7-15个字符做冒泡排序,然后验证值为1-9,因此可确定第7-15个字符是'1'-'9'的全排列

 

对奇数位的5个数和偶数位的4个数的全排列分别遍历:

1
2
3
4
5
6
7
8
9
10
11
12
13
def guessnum():
    it1 = list(itertools.permutations(['1', '3', '5', '7', '9'], 5))
    it2 = list(itertools.permutations(['2', '4', '6', '8'], 4))
    for l1 in it1:
        for l2 in it2:
            s = ""
            for i in range(4):
                s += l1[i]+l2[i]
            s += l1[4]
            if checknum(s):
                print(s)
 
guessnum()

得到唯一符合要求的结果:381654729

 

至此,可确定正确的输入满足正则:???KCTF381654729.*

 

题目做到这里时先写了爆破crc的程序(见第六部分),但是没爆出结果。后来才发现是因为忘记调用init_crctable()初始化crc table……
痛哭流涕……(此时题目一血还未出现)

第五部分

(因为前一部分的失误,浪费了不少时间在这里整理sub_4010E1的逻辑,其实这个函数完全无用)

1
2
3
4
5
6
...
  v31 = &inputvalue[const_9 + 7];
  sub_4010E1(v31, v20);
  if ( v20 <= 0 )
  {
...

sub_4010E1的核心是8字节到8字节的一个线性变换,Python的等价写法为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def sar8(n, k):
    n |= 0xff00 if n & 0x80 else 0
    n >>= k % 8
    return n & 0xff
 
def sub_4010E1(s):
    assert len(s) % 8 == 0
    r = b""
    for i in range(0, len(s), 8):
        src = s[i:i+8]
        dst = bytearray(8)
        for j in range(7):
            tmp = (src[j] << (7-j)) | sar8(src[j+1], j+1)
            tmp = (2*tmp) | 1
            dst[j] = (src[0] ^ tmp) & 0xff
        tmp = (2 * src[7]) | 1
        dst[7] = (src[0] ^ tmp) & 0xff
        r += dst
    return r

对于它的求解,可以用z3一把梭:(注意z3的BitVec重载的>>是算术右移)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solve_sub_4010E1(r):
    src = [BitVec(f'src{i}', 8) for i in range(8)]
    dst = [0]*8
    for j in range(7):
        tmp = (src[j] << (7-j)) | (src[j+1] >> (j+1))
        tmp = (2*tmp) | 1
        dst[j] = (src[0] ^ tmp) & 0xff
    tmp = (2 * src[7]) | 1
    dst[7] = (src[0] ^ tmp) & 0xff
    s = Solver()
    for i in range(8):
        s.add(dst[i] == r[i])
    print(s.check())
    m = s.model()
    print(m)
    ans = bytes(m[src[i]].as_long() for i in range(8))
    return ans

这部分检查的是输入值从第16个字节开始的部分:

1
2
3
4
5
6
7
...
    while ( (asc_4055C0[v3] ^ (unsigned __int8)v31[v3]) == asc_403DC8[v3] )
    {
      if ( ++v3 >= v20 )
        goto LABEL_45;
    }
...

asc_4055C0asc_403DC8异或,然后以8字节为单位求解,发现无解

第六部分

现在只有前三个字节未知。crc是可逆的,不过3个字节还是直接爆破更简单,直接复制IDA反编译的伪代码:

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
54
55
56
#include <stdio.h>
#include <string.h>
 
int crctable[256];
 
int init_crctable()
{
  signed int i; // esi
  int *v1; // edx
  signed int crc; // edi    // in normal crc, it should be unsigned
  int v3; // ebx
 
  i = 0;
  v1 = crctable;
  do
  {
    crc = i;
    v3 = 8;
    do
    {
      crc = (crc >> 1) ^ ((crc & 1) != 0 ? 0xEDB88320 : 0);// ? https://juejin.cn/post/6976011284244332552
      --v3;
    }
    while ( v3 );
    *v1 = crc;
    ++i;
    ++v1;
  }
  while ( v1 < &crctable[256] );
  return 0;
}
 
int crc32(char *inputvalue, int inputlen) {
  int i;
  int v11 = -1;
  int v67;
  for ( i = 0; i < inputlen; ++i )
    v11 = crctable[(unsigned char)(v11 ^ inputvalue[i])] ^ (v11 >> 8);
  v67 = ~v11;
  return v67;
}
 
int main(void) {
    init_crctable();    // do not forget this line !!!
    char buf[] = "124KCTF381654729";
    int len = strlen(buf);
    for (int i = 0; i <= 0xffffff; i++) {
        *(int *)&buf[0] = i;
        buf[3] = 'K';
        int r = crc32(buf, len);
        if (r == 0xF52E0765) {
            printf("%s\n", buf);
        }
    }
    return 0;
}

秒出结果:421KCTF381654729,输入程序中验证通过。


【公告】 [2022大礼包]《看雪论坛精华22期》发布!收录近1000余篇精华优秀文章!

最后于 2022-5-13 11:58 被mb_mgodlfyn编辑 ,原因:
收藏
点赞0
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回