KCTF 2022 cm2022复现

字数统计: 4.8k   |   阅读时长≈ 23 分钟

KCTF 2022 cm2022复现

拿到题目放入 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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
int __cdecl main(int argc, const char **argv, const char **envp)
{
  int v3; // edi
  int v4; // eax
  int v6; // esi
  int v7; // eax
  char v9; // [esp+8h] [ebp-40h] BYREF
  char v10[60]; // [esp+9h] [ebp-3Fh] BYREF
  __int16 v11; // [esp+45h] [ebp-3h]
  char v12; // [esp+47h] [ebp-1h]

  v9 = 0;
  memset(v10, 0, sizeof(v10));
  v11 = 0;
  v12 = 0;
  sub_40284A(aInput);
  gets(&v9);
  v3 = -1;
  v4 = 0;
  if ( !v9 )
    goto LABEL_20;
  do
  {
    if ( v4 >= 64 )
      break;
    if ( v10[v4 - 1] == 45 ) 
      v3 = v4;
  }
  while ( v10[v4++] );
  if ( v3 > 0
    && (v6 = v4 - v3, v4 - v3 > 0)
    && (int)sub_4014D0(dword_40A940, &v9, v3, a0123456789abcd) > 0
    && (int)sub_4014D0(&unk_40A964, &v10[v3], v6 - 1, a0123456789abcd) > 0
    && (sub_4014D0(&unk_40A9D0, aIrtzloz6iub, strlen(aIrtzloz6iub), a0123456789abcd),
        sub_401630(&unk_40A9FC, 0),
        sub_401630(&unk_40AA20, 0),
        (int)sub_401690(dword_40A940, &unk_40A964) < 0)
    && (int)sub_401690(dword_40A940, &unk_40A9D0) < 0
    && (int)sub_401690(&unk_40A964, &unk_40A9D0) < 0 )
  {
    v7 = 0;
    while ( 1 )
    {
      dword_40A9F4 = v7 + 1;
      sub_401730(&unk_40A9FC, &unk_40A9FC, dword_40A940);
      sub_401730(&unk_40AA20, &unk_40AA20, &unk_40A964);
      sub_4021A0(&unk_40A9FC, &unk_40A9FC, &unk_40A9D0);
      sub_4021A0(&unk_40AA20, &unk_40AA20, &unk_40A9D0);
      sub_401630(&dword_40A988, 1);
      sub_401820(&dword_40A988, &unk_40A9FC, &dword_40A988);
      if ( !sub_401690(&dword_40A988, dword_40A940) )
      {
        ++dword_40A9F8;
        sub_401CF0(&dword_40A988, &dword_40A988, dword_40A940);
      }
      sub_401630(&unk_40A9AC, 1);
      sub_401730(&unk_40A9AC, &unk_40AA20, &unk_40A9AC);
      if ( !sub_401690(&unk_40A9AC, &unk_40A964) )
      {
        ++dword_40A9F8;
        sub_401F30(&unk_40A9AC, &unk_40A9D0, &unk_40A964);
      }
      if ( dword_40A9F8 == 10 )
        break;
      v7 = dword_40A9F4;
      if ( dword_40A9F4 >= 0x200000 )
        goto LABEL_20;
    }
    sub_40284A(aSuccess);
    return 0;
  }
  else
  {
LABEL_20:
    sub_40284A(aError);
    return 0;
  }
}

​ 在大的 if 判断之前，它的作用就是去验证输入字符串的格式，必须要满足 xxx-xxx 的格式。v3 读出分隔符前半部分的长度，而 v4 为输入的字符串的总长度。

接下来就传入大的 if 判断里去给我们的输入添加约束条件。

==sub_401730==：

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
int __cdecl sub_4014D0(int *a1, int a2, int a3, const char *a4)
{
  int v4; // edx
  int v5; // edi
  int v6; // ecx
  int v7; // eax
  int v9; // ebp
  int v10; // eax
  int v11; // esi
  int v12; // eax
  bool v13; // zf
  int *v14; // edx
  int v15; // [esp+10h] [ebp-84h] BYREF
  int v16[32]; // [esp+14h] [ebp-80h] BYREF

  v4 = 0;
  memset(v16, 0, sizeof(v16));
  v5 = a3;
  v6 = strlen(a4);
  if ( a3 > 0 )
  {
    do
    {
      LOBYTE(v15) = *(_BYTE *)(v4 + a2);
      v7 = 0;
      if ( v6 <= 0 )
        return -1;
      while ( a4[v7] != (unsigned __int8)v15 )
      {
        if ( ++v7 >= v6 )
          return -1;
      }
      if ( v7 < 0 )
        return -1;
      v16[v4++] = v7;
    }
    while ( v4 < a3 );
  }
  v9 = 0;
  if ( !v16[a3 - 1] )
    return 0;
  v16[a3] = 0;
  if ( a3 )
  {
    v10 = v16[0];
    do
    {
      v11 = v5;
      if ( v5 >= 1 )
      {
        do
        {
          v12 = v16[v11];
          v16[v11 - 1] += v6 * (v12 % 256);
          v16[v11--] = v12 / 256;
        }
        while ( v11 >= 1 );
        v10 = v16[0];
      }
      *((_BYTE *)a1 + v9++ + 4) = v10;
      v10 /= 256;
      v13 = v5 == 0;
      v16[0] = v10;
      if ( v5 > 0 )
      {
        v14 = &v16[v5 - 1];
        do
        {
          if ( *v14 )
            break;
          --v5;
          --v14;
        }
        while ( v5 > 0 );
        v13 = v5 == 0;
      }
    }
    while ( !v13 );
    if ( v9 >= 32 )
      return -1;
  }
  *a1 = v9;
  return v9;
}

​ 通过动态调试可以分析出这个函数对我们输入的数据进行了某种加密，使用到了 '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'。

这个常量字符串的长度为 62，并且在其中涉及对我们的输入字符串的每一位去 table 中寻址下标。很难不去往 base62 的方向猜测。我们再来观察它的加密。

1
2
3
4
5
6
7
8
9
if ( v5 >= 1 )
      {
        do
        {
          v12 = v16[v11];
          v16[v11 - 1] += v6 * (v12 % 256);
          v16[v11--] = v12 / 256;
        }
        while ( v11 >= 1 );

​ v16 是我们字符串向虽然这个循环第一个取的是向 table 中寻址的下标。虽然这个加密先取的额外的元素，但是由于初始值为零。所以第一轮加密没有任何影响。紧接着对我们输入倒序处理，后面一位乘上 62 的结果加上前一位，这样的行为能感觉出来加密的位的权重应该是按照字符串的正序上升的。 我们输入数值尝试我们的加密结果：11 -> 0x3F = 63 、12 -> 0x7D = 125 相当于 62 进制中的 11 和 21 转换十进制的结果。所以尝试着带着这样的思路去认识这段加密过程。这个循环会将字符串的低位当作 62 进制的高位进行进制展开,比如 10112 = 1 * 2^3^ + 0 * 2^2^ + 1 * 2^1^ + 1 * 2^0^ ，然后将其按照小端序进行存储。并且将加密后的长度存储在地址的第一个 int （也就是前四个字节）处。我们可以发现其实存储的位置：dword_40A940 等。其实是一个结构体结构，总长度为 0x24。第一个成员是一个 int，第二个成员是个八个元素的dword数组。我们在 IDA 的 Local Types 窗口创建新的结构体：

1
2
3
4
struct number{
int len;
int num[8]
}

并将其同步到 idb。F5刷新，这样程序的可读性就大大增强了。

言归正传，我们可以看到这个函数调用了三次，观察传入的参数，我们可以发现三部分分别是对输入序列号的前半部分、后半部分和固定字符串IRtzloZ6iuB进行base62。接下来是函数 ==sub_401630==。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int __cdecl sub_401630(number *a1, int a2)
{
  int result; // eax

  a1->num[0] = a2;
  LOBYTE(a1->num[1]) = 0;
  for ( result = 4; result > 0; --result )
  {
    if ( *((_BYTE *)&a1->len + result + 3) )
      break;
  }
  a1->len = result;
  return result;
}

可以看到这是个对结构体进行设置的函数。将结构体内的数组的首元素设置为传入的第二个参数，然后将其他位置设零。可以看到这里设置了两个结构体。

==sub_401690==

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
int __cdecl sub_401690(number *a1, number *a2)
{
  int len; // eax
  int v4; // esi
  unsigned __int8 *v5; // eax
  unsigned __int8 v6; // cl
  int v7; // esi

  len = a1->len;
  if ( a1->len > a2->len )
    return 1;
  if ( a1->len < a2->len )
    return -1;
  v4 = len - 1;
  if ( len - 1 >= 0 )
  {
    v5 = (unsigned __int8 *)a2->num + v4;
    do
    {
      v6 = v5[(char *)a1 - (char *)a2];
      if ( v6 > *v5 )
        return 1;
      if ( v6 < *v5 )
        return -1;
      --v4;
      --v5;
    }
    while ( v4 >= 0 );
  }
  v7 = sub_402360(&dword_40A9AC, dword_40A9F4);
  if ( v7 == sub_401630((number *)&dword_40A988, 4) )
  {
    sub_402490(&dword_40A9AC, &dword_40A988, dword_40A9F4);
    sub_402360(&dword_40A988, dword_40A9F8);
  }
  return 0;
}

​ 可以看到这个函数的返回值只有1，0，-1。所以可以猜测这是个涉及判断的函数。可以看到这个函数首先比较长度，长度小的数值肯定小，那么就直接返回了，若长度相同那就先从高位向低位的顺序开始比较。函数最后的 if 部分通过调试发现对这些全局变量和返回值均没有什么影响，而且函数大概率会在那些比较长度和大小的地方返回，所以暂不讨论。

​ 那么既然这是个比较函数，那 main 函数 if 条件判断的最后三个条件判断从句所添加到的约束就为：前半 base62 结果大于后半且均小于固定字符串 base62 结果的大小。

​ if 分支结束后，我们就进入了 while 大循环，循环次数为 0x200000 次。对于这种大循环我们肯定要找到离开循环的条件，也就是 dword_40A9F4 全局变量的值等于十的时候 success，这就是解题的关键。可以看到有两个分支都可以使得该全局变量自加 1。那我们首要的思路就为在大循环中进入分支 10 次。

==sub_401730==

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
signed int __cdecl sub_401730(number *a1, number *a2, number *a3)
{
  int v3; // edx
  int len; // edi
  int v5; // esi
  int v6; // ebp
  int v7; // ebx
  char v10[33]; // [esp+10h] [ebp-24h] BYREF
  __int16 v11; // [esp+31h] [ebp-3h]
  char v12; // [esp+33h] [ebp-1h]

  v3 = 0;
  memset(v10, 0, sizeof(v10));
  v11 = 0;
  v12 = 0;
  len = a3->len;
  v5 = a2->len;
  v6 = a2->len;
  if ( a2->len < a3->len )
    v6 = a3->len;
  v7 = 0;
  if ( v6 > 0 )
  {
    do
    {
      if ( v7 < v5 )
        v3 += *((unsigned __int8 *)a2->num + v7);
      if ( v7 < len )
        v3 += *((unsigned __int8 *)a3->num + v7);
      v10[v7] = v3;
      v3 >>= 8;
      ++v7;
    }
    while ( v7 < v6 );
    for ( ; v3; v3 >>= 8 )
      v10[v7++] = v3;
    for ( ; v7 > 0; --v7 )
    {
      if ( v10[v7 - 1] )
        break;
    }
  }
  a1->len = v7;
  qmemcpy(a1->num, v10, v7);
  if ( sub_402360(&dword_40A9AC, dword_40A9F4) == 4 )
  {
    sub_402490(&dword_40A988, &dword_40A988, dword_40A9F4);
    sub_402360(&dword_40A988, dword_40A9F8);
  }
  return v7;
}

​ 可以看到这个函数的逻辑就是有一个临时变量 a3 去记录 a2 结构体里的数组值和 a3 结构体里的数组值的和。因为存入数组是按小端序存储，所以累加时正向取值即可，然后存入一个临时的数组，再将临时数组里的值复制进 a1 结构体的数组成员。所以我们可以得知这个函数是一个 add 函数。这个函数在大循环中出现两次，作用就是累加序列号加密后的前半段和后半段。

==sub_4021A0==

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
int __cdecl sub_4021A0(number *a1, number *a2, number *a3)
{
  number *v3; // ebx
  int v4; // eax
  int v6; // eax
  int i; // esi
  char v8; // bl
  char v9; // al
  int len; // edx
  number v11; // [esp+10h] [ebp-64h] BYREF
  char v12[61]; // [esp+34h] [ebp-40h] BYREF
  __int16 v13; // [esp+71h] [ebp-3h]
  char v14; // [esp+73h] [ebp-1h]

  memset(v12, 0, sizeof(v12));
  v3 = a3;
  v13 = 0;
  v14 = 0;
  v4 = cmp(a2, a3);
  if ( v4 >= 0 )
  {
    if ( v4 )
    {
      v6 = a2->len - a3->len;
      v11.len = a3->len;
      qmemcpy(v11.num, (char *)a2->num + v6, v11.len);
      for ( i = v6; i >= 0; --i )
      {
        if ( cmp(&v11, v3) >= 0 )
        {
          v8 = v12[i];
          do
          {
            ++v8;
            sub_401820(&v11, &v11, a3);
          }
          while ( cmp(&v11, a3) >= 0 );
          v12[i] = v8;
          v3 = a3;
        }
        if ( i > 0 )
        {
          sub_4023A0(&v11, &v11, 8);
          v9 = *((_BYTE *)&a2->len + i + 3);
          LOBYTE(v11.num[0]) = v9;
          if ( !v11.len )
            v11.len = v9 != 0;
        }
      }
      len = v11.len;
      qmemcpy(a1->num, v11.num, v11.len);
      a1->len = len;
      sub_401920(&dword_40A988, &unk_40A9FC, &unk_40AA20);
      if ( cmp((number *)&dword_40A988, (number *)&dword_40A9AC) > 0 && dword_40A9F8 > 0 )
      {
        sub_402490(&dword_40A988, &dword_40A988, dword_40A9F4);
        add((number *)&dword_40A9AC, (number *)dword_40A940, (number *)dword_40A964);
        sub_401820(&dword_40A988, &dword_40A988, &dword_40A9AC);
      }
      return v11.len;
    }
    else
    {
      a1->len = 0;
      LOBYTE(a1->num[0]) = 0;
      return 0;
    }
  }
  else
  {
    a1->len = a2->len;
    qmemcpy(a1->num, a2->num, a2->len);
    return a3->len;
  }
}

​ 观察这个函数，发现他经过 cmp 函数之后想要干的事情在 sub_401820 中，我们先来分析这个函数。

==sub_401820==

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
signed int __cdecl sub_401820(number *a1, number *a2, number *a3)
{
  int v3; // edx
  int len; // edi
  int v5; // esi
  int v6; // ebp
  int v7; // ebx
  char v10[29]; // [esp+10h] [ebp-20h] BYREF
  __int16 v11; // [esp+2Dh] [ebp-3h]
  char v12; // [esp+2Fh] [ebp-1h]

  v3 = 0;
  memset(v10, 0, sizeof(v10));
  v11 = 0;
  v12 = 0;
  len = a3->len;
  v5 = a2->len;
  v6 = a2->len;
  if ( a2->len < a3->len )
    v6 = a3->len;
  v7 = 0;
  if ( v6 > 0 )
  {
    do
    {
      if ( v7 < v5 )
        v3 += *((unsigned __int8 *)a2->num + v7);
      if ( v7 < len )
        v3 -= *((unsigned __int8 *)a3->num + v7);
      v10[v7] = v3;
      v3 >>= 8;
      ++v7;
    }
    while ( v7 < v6 );
    for ( ; v3; v3 >>= 8 )
    {
      if ( v7 >= 32 )
        break;
      v10[v7++] = v3;
    }
    for ( ; v7 > 0; --v7 )
    {
      if ( v10[v7 - 1] )
        break;
    }
  }
  a1->len = v7;
  qmemcpy(a1->num, v10, v7);
  if ( sub_402360(&dword_40A9D0, dword_40A9F4) == 4 )
  {
    sub_402360(&dword_40A9AC, dword_40A9F8);
    sub_402490(&dword_40A9AC, &dword_40A9AC, dword_40A9F4);
  }
  return v7;
}

​ 可以看到，这个函数与 add 函数格式比较相似，我们可以看到 v3 取了 a2 又减去了 a3，然后将结果存入 a1。可以得知这是一个 sub 函数。

​ 那么回到之前的函数，如果 a2 大于 a3 则循环递减 a3，直到 a2 小于 a3，所以这应该是一个向 a3 取模的函数，同样的后面的 if 判断我们同样留坑。那么这个函数分别调用了两次，我们算一下发现 常量字符串 base62 的结果为：10000000000000000000（10^19^），也就是序列号 base62 的前半和后半的循环累加结果分别向该数取模。

​ 我们根据分析好的内容对函数重命名：

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
while ( 1 )
    {
      dword_40A9F4 = v7 + 1;
      add(&unk_40A9FC, &unk_40A9FC, dword_40A940);
      add(&unk_40AA20, &unk_40AA20, dword_40A964);
      mod(&unk_40A9FC, &unk_40A9FC, &dword_40A9D0);
      mod(&unk_40AA20, &unk_40AA20, &dword_40A9D0);
      set(&dword_40A988, 1);
      sub(&dword_40A988, &unk_40A9FC, &dword_40A988);
      if ( !cmp((int)&dword_40A988, (int)dword_40A940) )
      {
        ++dword_40A9F8;
        sub_401CF0(&dword_40A988, &dword_40A988, dword_40A940);
      }
      set(&dword_40A9AC, 1);
      add(&dword_40A9AC, &unk_40AA20, &dword_40A9AC);
      if ( !cmp((int)&dword_40A9AC, (int)dword_40A964) )
      {
        ++dword_40A9F8;
        sub_401F30(&dword_40A9AC, &dword_40A9D0, dword_40A964);
      }
      if ( dword_40A9F8 == 10 )
        break;
      v7 = dword_40A9F4;
      if ( dword_40A9F4 >= 0x200000 )
        goto errrror;
    }

​ 这样我们就得出了循环中第一个 if 的判断条件：序列号前半的每一轮累加结果若与 10^19^ 取模再减一等于自身，则进入分支，写成表达式为：

1
(first_half * radix) mod (10000000000000000000) - 1 == first_half

​ 同样的第二个分支对应的也就是对序列号后半的约束：

1
(second_half * radix) mod (10000000000000000000) + 1 == second_half

​ 接下来我们看进入分支后执行的函数：

​ ==sub_401CF0==

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
int __cdecl sub_401CF0(number *a1, number *a2, number *a3)
{
  int v3; // edx
  int len; // ebx
  int v5; // edi
  int v7; // ebp
  int v8; // esi
  int v9; // ecx
  int v10; // eax
  unsigned __int8 *v11; // ecx
  int v12; // eax
  int v13; // eax
  int v14; // [esp+10h] [ebp-4Ch]
  int v15; // [esp+14h] [ebp-48h]
  int v16; // [esp+18h] [ebp-44h]
  char v17[61]; // [esp+1Ch] [ebp-40h] BYREF
  __int16 v18; // [esp+59h] [ebp-3h]
  char v19; // [esp+5Bh] [ebp-1h]

  v3 = 0;
  memset(v17, 0, sizeof(v17));
  v18 = 0;
  len = a3->len;
  v19 = 0;
  v5 = a2->len;
  v15 = len;
  v14 = a2->len;
  if ( len + a2->len <= 32 )
  {
    v7 = 0;
    v16 = len + v5 - 1;
    if ( v16 <= 0 )
      goto LABEL_20;
    do
    {
      v8 = v7;
      if ( v7 >= v5 )
        v8 = v5 - 1;
      v9 = v7;
      if ( v7 >= len )
        v9 = len - 1;
      v10 = v7 - v9;
      if ( v7 - v9 <= v8 )
      {
        v11 = a3->num + v9;
        do
          v3 += *v11-- * *(a2->num + v10++);  /* 功能实现 */
        while ( v10 <= v8 );
        v5 = v14;
        len = v15;
      }
      v12 = v16;
      v17[v7] = v3;
      v3 >>= 8;
      ++v7;
    }
    while ( v7 < v12 );
    for ( ; v3; v3 >>= 8 )
      v17[v7++] = v3;
    for ( ; v7 > 0; --v7 )
    {
      if ( v17[v7 - 1] )
        break;
    }
    if ( v7 <= 32 )
    {
LABEL_20:
      qmemcpy(a1->num, v17, v7);
      a1->len = v7;
    }
    else
    {
      a1->len = 0;
      LOBYTE(a1->num[0]) = 0;
    }
    sub_401920(&dword_40A988, &unk_40A9FC, &unk_40AA20);
    if ( cmp(&dword_40A988, &dword_40A9AC) > 0 && dword_40A9F8 > 0 )
    {
      sub_402490(&dword_40A988, &dword_40A988, dword_40A9F4);
      add(&dword_40A9AC, dword_40A940, dword_40A964);
      sub(&dword_40A988, &dword_40A988, &dword_40A9AC);
    }
    set(&dword_40A988, 4);
    sub_4023A0(&dword_40A9AC, &dword_40A988, 3);
    if ( dword_40A9F8 > 0 && *(&dword_40A9D4 + dword_40A9B0) == dword_40A9B0 )
    {
      add(&dword_40A988, &dword_40A988, &dword_40A9AC);
      v13 = sub_402360(&dword_40A988, dword_40A9F4);
      *(&dword_40A9D4 + dword_40A98C) += 4;
      sub_4023A0(&dword_40A988, &dword_40A988, v13);
      sub(&dword_40A9AC, &dword_40A988, &dword_40A9AC);
    }
    return v7;
  }
  else
  {
    a1->len = 0;
    LOBYTE(a1->num[0]) = 0;
    return a3->len + a2->len;
  }
}

​ 可以看到这个函数最主要实现功能的就在那一行：v3 += *v11-- * *(a2->num + v10++) v11 指向 a3，v3 指向 a1.所以这个函数实现的功能为 a2 与 a3 相乘结果保存在 a1.但我们可以发现传入的 a1 为 dword_40A988。这个全局变量每轮循环都会重新传入 set 函数进行设置，所以这个函数意义不大。

同样的我们来分析第二个分支：

==sub_401F30== 

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
int __cdecl sub_401F30(number *a1, number *a2, number *a3)
{
  number *v3; // ebx
  int v4; // eax
  int len; // ebp
  int v7; // ebp
  int i; // esi
  char v9; // bl
  char v10; // al
  int j; // ebp
  int v12; // eax
  number v13; // [esp+Ch] [ebp-64h] BYREF
  char v14[61]; // [esp+30h] [ebp-40h] BYREF
  __int16 v15; // [esp+6Dh] [ebp-3h]
  char v16; // [esp+6Fh] [ebp-1h]

  memset(v14, 0, sizeof(v14));
  v3 = a2;
  v15 = 0;
  v16 = 0;
  v4 = cmp(a2, a3);
  if ( v4 >= 0 )
  {
    if ( v4 )
    {
      len = a2->len;
      v13.len = a3->len;
      v7 = len - v13.len;
      qmemcpy(v13.num, a2->num + v7, v13.len);
      for ( i = v7; i >= 0; --i )
      {
        if ( cmp(&v13, a3) >= 0 )
        {
          v9 = v14[i];
          do
          {
            ++v9;
            sub(&v13, &v13, a3);	/* 功能实现 */
          }
          while ( cmp(&v13, a3) >= 0 );
          v14[i] = v9;
          v3 = a2;
        }
        if ( i > 0 )
        {
          sub_4023A0(&v13, &v13, 8);
          v10 = *(&v3->len + i + 3);
          LOBYTE(v13.num[0]) = v10;
          if ( !v13.len )
            v13.len = v10 != 0;
        }
      }
      for ( j = v7 + 1; j > 0; --j )
      {
        if ( *(&v13.num[7] + j + 3) )
          break;
      }
      qmemcpy(a1->num, v14, j);
      a1->len = j;
      sub(&dword_40A9AC, &stru_40AA20, dword_40A964);
      add(&dword_40A988, &stru_40A9FC, dword_40A940);
      if ( !cmp(&dword_40A988, &dword_40A9AC) || dword_40A9F8 > 0 )
      {
        sub_402490(&dword_40A988, &dword_40A988, dword_40A9F4);
        sub_402360(&dword_40A988, dword_40A9F8);
      }
      set(&dword_40A988, 4);
      sub_4023A0(&dword_40A9AC, &dword_40A988, 3);
      if ( dword_40A9F8 > 0 && *(&dword_40A9D4 + dword_40A9B0) == dword_40A9B0 )
      {
        add(&dword_40A988, &dword_40A988, &dword_40A9AC);
        v12 = sub_402360(&dword_40A988, dword_40A9F4);
        *(&dword_40A9D4 + dword_40A98C) += 4;
        sub_4023A0(&dword_40A988, &dword_40A988, v12);
        sub(&dword_40A9AC, &dword_40A988, &dword_40A9AC);
      }
      return j;
    }
    else
    {
      a1->len = 1;
      LOBYTE(a1->num[0]) = 1;
      return 1;
    }
  }
  else
  {
    a1->len = 0;
    LOBYTE(a1->num[0]) = 0;
    return 0;
  }
}

​ 可以看到这个函数是将 a2 循环递减 a3。将循环次数存进 a1.不难看出实现的功能是地板除。但是同样的，a1 同为每轮循环要重新设置的全局变量，所以明面上作用不大。

​ 主要的函数看的差不多了，该去求解了。在这里我们稍微思考一下，真的可以满足达成5组这样的输入吗？给的模数为 10^19^，而循环次数最多只有 10^6^ 数量级级。我们求解的条件是当循环数与模数互质的情况下才会有解且解唯一，那么就是说我们无论如何输入也只能在某一轮循环进入分支，也只能达成两次而已，我们需要别的去增加达成次数的点。

​ 这里有一个值得我们注意的地方，这个题目中使用了极其多的全局变量，也就是说不需要传入参数即可完成对它们值的修改，我们的达成次数（接下来管他叫 achieve）正是一个全局变量。我们发现在 mul 函数和 div 函数中都有一段类似的代码，我们把一些内存识别为结构体拿出来看看：

1
2
3
4
5
6
7
8
9
10
set(&stru_40A988, 4);
sub_4023A0(&stru_40A9AC.len, &stru_40A988.len, 3);
if ( achieve_40A9F8 > 0 && *&stru_40A9D0.num[stru_40A9AC.num[0]] == stru_40A9AC.num[0] )
{
  add(&stru_40A988, &stru_40A988, &stru_40A9AC);
  v13 = sub_402360(&stru_40A988, dword_40A9F4);
  stru_40A9D0.num[stru_40A988.num[0]] += 4; 
  sub_4023A0(&stru_40A988.len, &stru_40A988.len, v13);
  sub(&stru_40A9AC, &stru_40A988, &stru_40A9AC);
}

​ 可以看到这个 if 的判断条件涉及 achieve，并且进入分支后会对一个地址的内容加 4。 我们由衷的希望那个地址是 achieve，所以我们来验证这个可能性。首先 achieve 大于 0 那是肯定的，毕竟只有进入分支才能执行到这个 if。想要理解后面的判断就需要去分析前面函数sub_4023A0 给 stru_40A9AC.num[0]的赋值结果。

==sub_4023A0==

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
signed int __cdecl sub_4023A0(number *a1, number *a2, int a3)
{
  int v3; // ebx
  int v4; // edx
  int len; // edi
  signed int result; // eax
  int i; // esi
  char v10[61]; // [esp+Ch] [ebp-40h] BYREF
  __int16 v11; // [esp+49h] [ebp-3h]
  char v12; // [esp+4Bh] [ebp-1h]
  int v13; // [esp+54h] [ebp+8h]

  v3 = 0;
  memset(v10, 0, sizeof(v10));
  v11 = 0;
  v12 = 0;
  v4 = a3 >> 3;
  len = a2->len;
  v13 = a2->len + (a3 >> 3);
  if ( v13 <= 32 )
  {
    for ( i = 0; ; ++i )
    {
      if ( i < len )
        v3 += *(a2->num + i) << (a3 % 8);	/* 功能实现 */
      v10[v4 + i] = v3;
      v3 >>= 8;
      if ( i >= len && !v3 )
        break;
    }
    for ( result = v13 + 1; result > 0; --result )
    {
      if ( *(v10 + result + 23) )
        break;
    }
    if ( result <= 32 )
    {
      qmemcpy(a1->num, v10, result);
      a1->len = result;
    }
    else
    {
      a1->len = 0;
      LOBYTE(a1->num[0]) = 0;
    }
  }
  else
  {
    a1->len = 0;
    LOBYTE(a1->num[0]) = 0;
    return v4 + a2->len;
  }
  return result;
}

​ 这个函数可以看到主要功能的那句代码对 a2 左移了 a3 位，而左移相当于乘上 2^n^ 所以可以得知此函数实现乘以 2 的 a3 次幂的功能。而我们看最外面的 main 函数：set(&stru_40A988, 1) 这个结构体被设为了 1。所以这个函数将该结构体的值设置成 2^4 = 32。

​ 接下来，*&stru_40A9D0.num[stru_40A9AC.num[0]] == stru_40A9AC.num[0] ) 就相当于 stru_40A9D0.num[32] == 32 ，stru_40A9D0.num 的地址相当于 0x40A9D0 + 4，0x40A9D0 + 4 + 32 = 0x40A9F4，也就是循环基数。也就是说我们的循环次数达到32次的时候可以进入该分支。

​ 这下一切都很明确了，(XXX_half * radix) mod (10000000000000000000) +- 1 == XXX_half，radix就等于一。这里记录一下 python 求逆元的方法：

若 (k * n) mod p = 1，k 与 p 互质（即有唯一解情况）

n = pow(k, -1, p)

解题脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
table = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'

def b62Tostr(decode_int):
    global table
    str = ''
    while decode_int:
        str += table[decode_int % 62]
        decode_int //= 62
    return str
        
def main():     
    part1 = pow(31, -1, 10**19)
    flag1 = b62Tostr(part1)
    part2 = pow(-31, -1, 10**19)
    flag2 = b62Tostr(part2)
    print(flag1 + '-' + flag2)

if __name__ == '__main__':
    main()

序列号：ZSxZerX4xb4-jyvP7x12lI7

  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！

扫一扫，分享到微信

微信分享二维码
  • Copyrights © 2022-2023 Syclover.Kama
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信