首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 看雪峰会 看雪商城 证书查询
  1. 看雪社区
  2. CTF对抗
    3. 发新帖
[原创] 看雪 2023 KCTF 年度赛 第十一题 步步逼近
2023-9-29 05:03 10394

[原创] 看雪 2023 KCTF 年度赛 第十一题 步步逼近

mb_mgodlfyn 活跃值
12
2023-9-29 05:03
10394

代码没有加混淆，非常好评

IDA打开，逻辑非常清楚。有一些明面的反调试，如果需要动态调试，patch掉即可。

从main函数开始看：

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
int __cdecl main(int argc, const char **argv, const char **envp)
{
  unsigned int ii; // esi
  int v4; // eax
  int v5; // edi
  int length; // esi
  int v7; // eax
  int i; // ecx
  HWND WindowW; // eax
  int n_0; // esi
  int n_1; // edi
  bool success; // bl
  HANDLE CurrentProcess; // eax
  int n[2]; // [esp+Ch] [ebp-30h] BYREF
  int seed; // [esp+18h] [ebp-24h] BYREF
  BOOL pbDebuggerPresent; // [esp+1Ch] [ebp-20h] BYREF
  char buf[8]; // [esp+20h] [ebp-1Ch] BYREF
  __int16 v19; // [esp+28h] [ebp-14h]
  char v20; // [esp+2Ah] [ebp-12h]
  char Buffer[8]; // [esp+2Ch] [ebp-10h] BYREF
  __int16 v22; // [esp+34h] [ebp-8h]
  char v23; // [esp+36h] [ebp-6h]
 
  v19 = 0;
  *(_QWORD *)n = 0i64;
  *(_QWORD *)buf = 0i64;
  v20 = 0;
  *(_QWORD *)Buffer = 0i64;
  v22 = 0;
  v23 = 0;
  printf("Please input: ");
  ii = 0;
  while ( 1 )
  {
    v4 = getchar();
    if ( v4 == 10 )
      break;
    v5 = ii + 1;
    buf[ii] = v4;
    if ( ii + 1 >= 0xB )
      goto LABEL_41;
    buf[v5] = 0;
    if ( ii == 9 && getchar() != 10 )
      goto LABEL_39;
    ++ii;
    if ( v5 >= 10 )
      goto LABEL_10;
  }
  if ( ii >= 0xB )
  {
LABEL_41:
    __report_rangecheckfailure();
    __debugbreak();
  }
  buf[ii] = 0;
LABEL_10:
  length = 0;
  if ( buf[0] )
  {
    while ( ++length <= 10 )
    {
      if ( !buf[length] )
        goto LABEL_15;
    }
    length = -1;
  }
LABEL_15:
  if ( sscanf(buf, "%lld", n) == 1 )
  {
    v7 = sprintf(Buffer, 11u, "%lld", *(_QWORD *)n);
    if ( length > 0 && v7 > 0 && length == v7 )
    {
      i = 0;
      while ( buf[i] == Buffer[i] )
      {
        if ( ++i >= length )
        {
          if ( *(__int64 *)n > 0 )
          {
            WindowW = FindWindowW(L"OLLYDBG", 0);
            n_0 = n[0];
            n_1 = n[1];
            if ( WindowW )
            {
              n_0 = n[0] | 0xFFFF;
              n[0] |= 0xFFFFu;
            }
            if ( __PAIR64__(n[1], n_0) - 4096 <= 4294963200 )
            {
              if ( CryptAcquireContextW(&hProv, 0, 0, 1u, 0xF0000000) )
              {
                hMutex = CreateMutexW(0, 0, 0);
                if ( hMutex )
                {
                  seed = 0;
                  CryptGenRandom(hProv, 4u, (BYTE *)&seed);
                  srand(seed);
                  global_fail = 0;
                  success = 0;
                  if ( sub_4015A0(n_0, n_1) )
                  {
                    if ( !global_fail )
                    {
                      global_fail = 0;
                      if ( sub_4015A0(n_0 - 1, (__PAIR64__(n_1, n_0) - 1) >> 32) )
                      {
                        if ( global_fail )
                          success = 1;
                      }
                    }
                  }
                  CryptReleaseContext(hProv, 0);
                  CloseHandle(hMutex);
                  pbDebuggerPresent = 0;
                  CurrentProcess = GetCurrentProcess();
                  if ( CheckRemoteDebuggerPresent(CurrentProcess, &pbDebuggerPresent) && pbDebuggerPresent )
                    success = 0;
                  if ( success )
                  {
                    MessageBoxW(0, L"Accepted!", L"Result", 0x40u);
                    return 0;
                  }
                }
              }
            }
          }
          break;
        }
      }
    }
  }
LABEL_39:
  MessageBoxW(0, L"Wrong answer!", L"Result", 0x10u);
  return 0;
}

输入是一个十进制整数，范围在 [4096, 4294967296] 之间。这个整数需要通过sub_4015A0的验证并且减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
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
char __cdecl sub_4015A0(int a1, int a2)
{
  int dwNumberOfProcessors; // edi
  int v3; // eax
  int v4; // ebx
  _DWORD *v5; // esi
  int i; // esi
  int v8; // [esp+Ch] [ebp-52Ch]
  struct _SYSTEM_INFO SystemInfo; // [esp+10h] [ebp-528h] BYREF
  char Parameter[1024]; // [esp+34h] [ebp-504h] BYREF
  void *Handles[64]; // [esp+434h] [ebp-104h] BYREF
 
  memset(Handles, 0, sizeof(Handles));
  memset(Parameter, 0, sizeof(Parameter));
  memset(&SystemInfo, 0, sizeof(SystemInfo));
  GetSystemInfo(&SystemInfo);
  dwNumberOfProcessors = SystemInfo.dwNumberOfProcessors;
  if ( (int)SystemInfo.dwNumberOfProcessors <= 0 )
    return 0;
  if ( (int)SystemInfo.dwNumberOfProcessors > 64 )
    dwNumberOfProcessors = 64;
  v8 = 10000 / dwNumberOfProcessors;
  if ( IsDebuggerPresent() )
  {
    v3 = v8 >> 4;
    v4 = 0;
    v8 >>= 4;
  }
  else
  {
    v4 = 0;
    if ( dwNumberOfProcessors <= 0 )
      goto LABEL_10;
    v3 = 10000 / dwNumberOfProcessors;
  }
  v5 = Parameter;
  do
  {
    *v5 = a1;
    v5[1] = a2;
    v5[2] = v3;
    Handles[v4] = CreateThread(0, 0, (LPTHREAD_START_ROUTINE)StartAddress, v5, 0, 0);
    v5 += 4;
    v3 = v8;
    ++v4;
  }
  while ( v4 < dwNumberOfProcessors );
LABEL_10:
  if ( WaitForMultipleObjects(dwNumberOfProcessors, Handles, 1, 0xFFFFFFFF) >= dwNumberOfProcessors )
    return 0;
  for ( i = 0; i < dwNumberOfProcessors; ++i )
    CloseHandle(Handles[i]);
  return 1;
}

根据cpu数量开不同数量的线程，并行执行StartAddress(sub_4010D0)函数。

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
DWORD __stdcall StartAddress(unsigned int *lpThreadParameter)
{
  int *b; // edi
  int *c; // ebx
  int *d; // esi
  void *a_; // eax
  char v5; // bl
  int v6; // ebx
  int *b_i; // esi
  int v8; // edi
  BOOL v9; // esi
  int v10; // et2
  int i; // esi
  int v12; // eax
  int *c__; // edx
  int new_t1_; // edi
  int new_t0_; // ebx
  int *b_j_; // ecx
  int j_; // eax
  int i_; // esi
  unsigned __int64 v19; // kr08_8
  __int64 v20; // kr10_8
  int i__; // eax
  int c_minus_d; // edx
  int t1; // edi
  int j; // esi
  int *v3_i; // ecx
  unsigned int t0; // ebx
  int new_t0; // kr18_4
  __int64 v28; // rax
  bool v29; // zf
  __int64 v30; // kr20_8
  void (__cdecl *v31)(void *); // edi
  __int64 v33; // [esp-Ch] [ebp-64h]
  __int64 v34; // [esp-Ch] [ebp-64h]
  __int64 v35; // [esp-Ch] [ebp-64h]
  __int64 v36; // [esp-Ch] [ebp-64h]
  int *v37; // [esp-4h] [ebp-5Ch]
  int *b_j; // [esp+10h] [ebp-48h]
  int *v3_i_; // [esp+10h] [ebp-48h]
  int *b_i_; // [esp+14h] [ebp-44h]
  int t1_; // [esp+14h] [ebp-44h]
  int v1_____; // [esp+14h] [ebp-44h]
  int *c_; // [esp+18h] [ebp-40h]
  int j___; // [esp+1Ch] [ebp-3Ch]
  int i___; // [esp+1Ch] [ebp-3Ch]
  int *a; // [esp+20h] [ebp-38h]
  int *b_; // [esp+24h] [ebp-34h]
  int *d_; // [esp+28h] [ebp-30h]
  int t0_; // [esp+2Ch] [ebp-2Ch]
  int t1___; // [esp+2Ch] [ebp-2Ch]
  int a_minus_b; // [esp+38h] [ebp-20h]
  unsigned int t0___; // [esp+38h] [ebp-20h]
  unsigned int x_1; // [esp+40h] [ebp-18h]
  int v54; // [esp+44h] [ebp-14h]
  unsigned int x_0; // [esp+48h] [ebp-10h]
  unsigned int seed; // [esp+50h] [ebp-8h] BYREF
 
  a = (int *)calloc(10000u, 4u);
  b = (int *)calloc(10000u, 4u);
  b_ = b;
  c = (int *)calloc(20000u, 4u);
  c_ = c;
  d = (int *)calloc(20000u, 4u);
  a_ = a;
  d_ = d;
  if ( !a )
    goto LABEL_41;
  if ( !b )
    goto LABEL_40;
  if ( !c )
    goto LABEL_40;
  if ( !d )
    goto LABEL_40;
  v54 = 0;
  if ( (int)lpThreadParameter[2] <= 0 )
    goto LABEL_40;
  while ( 2 )
  {
    WaitForSingleObject(hMutex, 0xFFFFFFFF);
    v5 = global_fail;
    ReleaseMutex(hMutex);
    if ( v5 )
      break;
    seed = 0;
    CryptGenRandom(hProv, 4u, (BYTE *)&seed);
    srand(seed);
    v6 = 0;
    b_i = b;
    b_i_ = b;
    a_minus_b = (char *)a - (char *)b;
    do
    {
      v8 = dword_4031CC[rand() % 7];
      *(int *)((char *)b_i + a_minus_b) = v8;
      v9 = v6 == 0;
      v10 = rand() % (int)((__PAIR64__(v8, v6++) - 1) >> 32);
      *b_i_ = v9 + v10;
      b_i = ++b_i_;
    }
    while ( v6 < 10000 );
    for ( i = 0; i < 20000; ++i )
    {
      v12 = rand();
      c__ = c_;
      c_[i] = dword_4031CC[v12 % 7];
    }
    new_t1_ = 0;
    new_t0_ = 0;
    x_0 = *lpThreadParameter;
    b_j_ = b_;
    x_1 = lpThreadParameter[1];
    j_ = 0;
    i_ = 0;
LABEL_12:
    b_j = b_j_;
    j___ = j_;
    while ( 1 )
    {
      t0_ = new_t0_;
      t1_ = new_t1_;
      if ( j_ >= 10000 && (new_t1_ < 0 || new_t1_ <= 0 && !new_t0_) )
        break;
      if ( i_ >= 20000 )
      {
LABEL_38:
        WaitForSingleObject(hMutex, 0xFFFFFFFF);
        global_fail = 1;
        ReleaseMutex(hMutex);
        b = b_;
        goto LABEL_39;
      }
      if ( j_ >= 10000 )
      {
        v34 = c__[i_];
        v20 = __SPAIR64__(new_t1_, new_t0_) / v34;
        new_t1_ = (unsigned __int64)(__SPAIR64__(new_t1_, new_t0_) / v34) >> 32;
        new_t0_ = v20;
        c__ = c_;
        d_[i_++] = __SPAIR64__(t1_, t0_) % v34;
        j_ = j___;
        b_j_ = b_j;
      }
      else
      {
        new_t1_ = (*b_j + *(int *)((char *)b_j_ + a_minus_b) * __PAIR64__(new_t1_, new_t0_)) >> 32;// v0
        v33 = c_[i_];
        new_t0_ = *b_j + *(int *)((char *)b_j_ + a_minus_b) * new_t0_;
        if ( (__int64)(__SPAIR64__(t1_, t0_) / v33 * __PAIR64__(new_t1_, new_t0_)) < __SPAIR64__(x_1, x_0) )
        {
          j_ = j___ + 1;
          c__ = c_;
          b_j_ = b_j + 1;
          goto LABEL_12;
        }
        v19 = __SPAIR64__(t1_, t0_) / v33;
        new_t1_ = HIDWORD(v19);
        new_t0_ = v19;
        c__ = c_;
        d_[i_++] = __SPAIR64__(t1_, t0_) % v33;
        j_ = j___;
        b_j_ = b_j;
      }
    }
    i__ = i_ - 1;
    i___ = i__;
    c_minus_d = (char *)c__ - (char *)d_;
    t1 = 0;
    j = 9999;
    v3_i = &d_[i__];
    v1_____ = c_minus_d;
    t0 = 0;
    v3_i_ = v3_i;
    while ( 1 )
    {
      t0___ = t0;
      t1___ = t1;
      if ( i__ < 0 && (t1 < 0 || t1 <= 0 && !t0) )
        break;
      if ( j < 0 )
        goto LABEL_38;
      if ( i__ < 0 )
      {
        v36 = a[j];
        v30 = __SPAIR64__(t1, t0) / v36;
        t1 = (unsigned __int64)(__SPAIR64__(t1, t0) / v36) >> 32;
        t0 = v30;
        v29 = (unsigned int)(__SPAIR64__(t1___, t0___) % v36) == b_[j];
LABEL_34:
        if ( !v29 )
          goto LABEL_38;
        i__ = i___;
        --j;
        v3_i = v3_i_;
        c_minus_d = v1_____;
      }
      else
      {
        new_t0 = *v3_i_ + *(int *)((char *)v3_i + c_minus_d) * t0;
        t1 = (*v3_i_ + *(int *)((char *)v3_i + c_minus_d) * __PAIR64__(t1, t0)) >> 32;
        v35 = a[j];
        v28 = __SPAIR64__(t1___, t0) / v35;
        t0 = new_t0;
        if ( (signed __int64)(v28 * __PAIR64__(t1, new_t0)) >= *(_QWORD *)lpThreadParameter )
        {
          t1 = HIDWORD(v28);
          t0 = v28;
          v29 = (unsigned int)(__SPAIR64__(t1___, t0___) % v35) == b_[j];
          goto LABEL_34;
        }
        i__ = i___ - 1;
        c_minus_d = v1_____;
        v3_i = v3_i_ - 1;
        --i___;
        --v3_i_;
      }
    }
    b = b_;
    if ( ++v54 < (int)lpThreadParameter[2] )
      continue;
    break;
  }
LABEL_39:
  a_ = a;
  d = d_;
  c = c_;
LABEL_40:
  free(a_);
LABEL_41:
  if ( b )
  {
    v37 = b;
    v31 = free;
    free(v37);
  }
  else
  {
    v31 = free;
  }
  if ( c )
    v31(c);
  if ( d )
    v31(d);
  if ( NtCurrentPeb()->BeingDebugged )
  {
    WaitForSingleObject(hMutex, 0xFFFFFFFF);
    global_fail = 1;
    ReleaseMutex(hMutex);
  }
  return 0;
}

StartAddress的参数lpThreadParameter包含一个long long整数（来自用户输入）和一个循环次数参数（此参数来自sub_4015A0，为10000/dwNumberOfProcessors）。每一次循环检查，都会随机生成一组新的a、b、c、d数据，然后结合用户输入的整数x做运算，并根据运算情况为global_fail赋值。
结合sub_4015A0，实际上是把10000次的检查按照cpu数量平分到多个进程中。如果要通过main函数中第一次global_fail==0的检查，需要10000次循环中生成的随机数据都通过检查。程序要求10000组随机数据都通过测试，实际上是要求在随机数据产生范围内的所有可能值都能通过验证（只是这个空间太大无法逐一检验），所以，从破解角度需要找到的是一个通用的值，这里的多线程可以当做障眼法。

StartAddress函数有很多__PAIR64__，能看出来实际上是64位整数的运算，但程序本身是32位的，伪代码看起来非常难受。

基于以上分析，先对整体校验逻辑做一个重写：（基于Linux x64环境）
（其实这一步并不容易，因为要保证逻辑完全一致，而且不容易动态调试验证，实际花费的时间和精力非常大，而且过程中确实推翻逻辑了很多次）

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
102
103
104
105
106
107
108
109
#include <stdio.h>
#include <stdlib.h>
#include <sys/random.h>
 
int dword_4031CC[7] = { 2, 4, 5, 6, 7, 8, 13 };
 
long long a[10000];
long long b[10000];
long long c[20000];
long long d[20000];
 
void initialize(void) {
    int seed = 0;
    getrandom(&seed, 4, 0);
    srand(seed);
    for (int i = 0; i < 10000; i++) {
        int tmp = dword_4031CC[rand() % 7];
        a[i] = tmp;
        b[i] = (i == 0) + (rand() % tmp);    // ?
    }
    for (int i = 0; i < 20000; i++) {
        int tmp = dword_4031CC[rand() % 7];
        c[i] = tmp;
    }
}
 
int check(long long x, int count) {
    for (int k = 0; k < count; k++) {
        int i = 0;
        int j = 0;
        while (1) {
            if (j >= 10000 && t <= 0) {
                break;
            }
            if (i >= 20000) {
                return 0;
            }
            if (j >= 10000) {
                d[i] = t % c[i];
                t /= c[i];
                i += 1;
            }
            else {
                long long newbigt = b[j] + a[j] * t;
                long long newsmallt = t / c[i];
                if (newsmallt * newbigt < x) {
                    j += 1;
                    t = newbigt;
                }
                else {
                    d[i] = t % c[i];
                    t = newsmallt;
                    i += 1;
                }
            }
        }
        i -= 1;
        t = 0;
        j = 9999;
        while (1) {
            if (i < 0 && t <= 0) {
                break;
            }
            if (j < 0) {
                return 0;
            }
            if (i < 0) {
                if ( ! (t % a[j] == b[j]) ) {
                    return 0;
                }
                t /= a[j];
                --j;
            }
            else {
                long long newbigt = d[i] + c[i] * t;
                long long newsmallt = t / a[j];
                if (newsmallt * newbigt >= x) {
                    if (! (t % a[j] == b[j])) {
                        return 0;
                    }
                    t = newsmallt;
                    --j;
                }
                else {
                    i -= 1;
                    t = newbigt;
                }
            }
        }
    }
    return 1;
}
 
int main(void) {
    long long x = 0;
    scanf("%lld", &x);
    if (x >= 4096 && x <= 4294967296) {
        if (check(x, 10000) && !check(x-1, 10000)) {
            printf("Accepted!\n");
        }
        else {
            printf("Wrong answer!\n");
        }
    }
    else {
        printf("Wrong answer!\n");
    }
    return 0;
}

基于重写后的代码继续分析：

每轮检查有四个全局数组a、b、c、d，其中a和c的值只能取2, 4, 5, 6, 7, 8, 13这七个数之一，b的值则不能超过对应位a的值。

之后的第一个循环，可以先想象成一个人在网格图上游走形成路径的过程：
(i,j)是坐标，t是实时负重，x是负重限额
每次行走一步，每一步只能选择向右(j+=1)或向下(i+=1)
如果向右走，则会拾起物品（b[j]）增加负重（t = b[j] + a[j] * t）；如果向下走，则会丢弃物品（d[i]减少负重（t = t / c[i]）
具体向哪边走，则由两个方向下一步的负重乘积与x的大小关系决定，如果太小则向右走增加负重，如果太大则向左走减少负重，使得当前负重t始终在x附近震荡
最后，当向右行走10000步后，如果剩余负重大于0，继续不断向下走并丢弃物品（d[i]）直到负重为0停止

第一个循环结束后会形成一个轨迹。而第二个循环是从终点开始反向，每一步根据情况决定向上走还是向左走（丢弃b[j]）。如果决定向上走，则重新拾取丢弃的物品（d[i]）增加负重（t = d[i] + c[i] * t）；如果决定向左走，则丢弃物品减少负重（t = t / a[j]），但要保证与正向路径向右走时拾取的物品（b[j]）重量相等。
由于物品的重量都是随机的，所以要保证每次反向向左走时的判断成立，反向路径必须与正向路径完全重叠。此外可得到一个推论，即正反路径在相同坐标点的负重也一定是相同的。

但是，对于正反路径相同的坐标点(i,j)，用于决定下一步判断的a、b、c、d值的索引不同，正向路径是i或j，反向路径是i-1或j-1（虽然循环中没有减一，但是注意到进入第二轮循环之前已经预先对i和j减了一），这就使得反向的每一步并不是平凡的一定沿着正向的相反方向，而是要根据实际情况而定；而我们的目标是找到一个合适的x使得这个条件无论如何都能成立。

（题外话：不知道这个抽象是不是出题人预设的数学模型，但单从这个抽象来看感觉应该有纯数学的解法，而且应该非常优雅无需爆破，可惜想了很久也没想出来）
（题外话2：题目的背景故事给的是数据在七颗不同链路卫星之间通信的问题，所以以上抽象应该不是出题人的预设；另，按照卫星链路的故事找到了一篇专利通信系统中前向和反向链路切换边界的平衡方法和设备，摘要是“一种使前向链路切换边界的位置与反向链路切换边界匹配的方法和设备。选择一个定义每个基台接收功率和发射导频功率乘积的系统常数。在基台测量反向链路功率电平，并用前向链路功率电平补偿反向链路负载以保持乘积常数。从而使前向链路切换边界对准反向链路切换边界并同处一个位置”，其中“乘积常数”、前向链路对准反向链路“并同处一个位置”的描述感觉非常契合代码逻辑，可惜从文中也没看出解法）

想不到优雅的求解那就只好爆破了。（p.s.本届KCTF的逆向题这么都这么偏爱爆破……）。原始输入的范围有42亿个取值，再加上每个取值都要做两层嵌套的万级循环，显然太多，要考虑下如何缩小范围。

观察一：

注意正向行进时的方向判定条件 (b[j] + a[j] * t) * (t / c[i]) < x，其中a、b、c、x都有范围限定，因此可以反推出t的范围限定（大致在0到sqrt(13/2*x)的区间）；而已知a、b、c、t的取值范围后，由于它们都是整数，所以该不等式的左侧取值也是有限的。

用一个粗糙的Python脚本把它们全部找出并存下来：（如果用C写，要自己处理去重和排序；即使用C++标准库stl有实现，但也远没有Python方便）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def p64(n):
    return n.to_bytes(8, "little")
 
s = set()
 
for t in range(173391):
    for a in [2, 4, 5, 6, 7, 8, 13]:
        for c in [2, 4, 5, 6, 7, 8, 13]:
            for b in range(a):
                tt = (a * t + b) * (t // c)
                if 4096 <= tt < (1<<32):
                    s.add(tt)
 
print(len(s))  # 9823158
ss = sorted(s)
 
for i, c in enumerate(ss):
    if c == 1898766391:
        print(ss[i-1])
 
r = b"".join(p64(c) for c in ss)
 
with open("nums.bin", "wb") as f:
    f.write(r)

可以看到这里左侧只有9823158种不同的取值，从十亿量级直接下降了一百倍到了千万量级。

观察二：

原始程序的检查是正向路径全部走完再从终点开始检查反向路径；但基于之前的分析，路径重合实际要求每一步都重叠，所以可以正向每走一步就即时检查该步能否反向，如果不通则立刻判定失败提前返回。这一步预期能大量剪枝，不合适的x值很可能在几步之内就会产生无法反向的行进，而不必先花费万步把正向路径走完再检查。

观察三：

原程序会执行10000次检验，每次都会生成一组新的a、b、c、d数据，然后再跑两个路径循环。首先，只有正确的x值能通过全部随机数据空间的检验，那么错误的x值大概只需要几组随机结果的检查就会暴露出问题，此时也可以直接宣告失败，不必继续生成新的随机数据检验；其次，如果某个x未通过某组随机数据的检查，我们仍然可以用这组随机数据继续检查下一个x而不必每次都重新初始化。

原本对每个可能的取值的检查都要做二重循环，且两层都是万级别，则计算量是十亿*万*万；
观察一使得取值空间从十亿降到了千万；观察二使得对大多数的值，检查的外层循环从万降到了个位数；观察三使得对大多数的值，检查的内层循环从万降到了个位数。所以总的计算量降到了千万，变得勉强可以接受。
（p.s. 这里降到了千万级的计算量一度不敢继续下手爆破，而是还在继续找优化点，因为以往做常规逆向题，哪怕不确定的答案只有几个复杂度都很搞了，千万级的计算量根本不敢想象有爆破的可能，还要担心爆破代码写错的风险；但这届KCTF的几道暴力题，int32以内（亿级别）的遍历似乎都平淡无奇……）

爆破脚本：
（注意两处注释的细节）

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/random.h>
 
#define MIN(i, j) (((i) < (j)) ? (i) : (j))
#define MAX(i, j) (((i) > (j)) ? (i) : (j))
 
int dword_4031CC[7] = { 2, 4, 5, 6, 7, 8, 13 };
 
long long a[10000];
long long b[10000];
long long c[20000];
long long d[20000];
 
void initialize(void) {
    int seed = 0;
    getrandom(&seed, 4, 0);
    srand(seed);
    for (int i = 0; i < 10000; i++) {
        int tmp = dword_4031CC[rand() % 7];
        a[i] = tmp;
        // b[i] = (i == 0) + (rand() % tmp);    // 这里似乎是原程序的逻辑，但是i==0时多加的一个1有打破b[i]<a[i]的可能感觉很奇怪；考虑到随机数据只是用来验证结果，也不差这一组，干脆去掉
        b[i] = rand() % tmp;
    }
    for (int i = 0; i < 20000; i++) {
        int tmp = dword_4031CC[rand() % 7];
        c[i] = tmp;
    }
}
 
int check(long long x, int count) {
    for (int k = 0; k < count; k++) {
        int i = 0;
        int j = 0;
        long long t = 0;
        while (1) {
            int cond = 0;
            if (j >= 10000 && t <= 0) {
                break;
            }
            if (i >= 20000) {
                return 0;
            }
            if (j >= 10000) {
                d[i] = t % c[i];
                t /= c[i];
                i += 1;
                cond = 2;
            }
            else {
                long long newbigt = b[j] + a[j] * t;
                long long newsmallt = t / c[i];
                if (newsmallt * newbigt < x) {
                    j += 1;
                    t = newbigt;
                    cond = 1;
                }
                else {
                    d[i] = t % c[i];
                    t = newsmallt;
                    i += 1;
                    cond = 2;
                }
             
            }
            {
                int ii = i - 1;
                int jj = j - 1;
                if (i >= 1 && j >= 1) {
                    long long backnewbigt = d[ii] + c[ii] * t;
                    long long backnewsmallt = t / a[jj];
                    int dnoc = backnewsmallt * backnewbigt >= x;
                    if ((cond == 2 && !dnoc) || (cond == 1 && dnoc)) {
                        ;
                    }
                    else {
                        return 0;
                    }
                }
            }
        }
        initialize();
    }
    return 1;
}
 
 
long long nums[10023982];
 
 
long long initialize_nums(void) {
    long long k = 9823158;
    int fd = open("nums.bin", O_RDONLY);
    int r = read(fd, nums, k * 8);
    if (r != k * 8) {
        printf("data error\n");
    }
    close(fd);
    return k;
}
 
 
int main(int argc, char **argv) {
    initialize();
    long long maxk = initialize_nums();
    int lowbound = atoi(argv[1]);
    int highbound = atoi(argv[2]);
    for (long long k = MAX(4096, lowbound); k < MIN(maxk, highbound); k++) {
        long long i = nums[k] + 1;    // 由于程序的判断条件是i<x和i>=x，i是作为左开右闭的区间上边界存在，而我们要找的最小x是区间的下边界，所以对前一个区间的上边界加一即得后一个区间的下边界
        if (k % 100000 == 0) {
            printf("%lld %lld %lld\n", k, i, maxk);
        }
        int r = check(i, 10000);
        if (r) {
            printf("success %lld %lld\n", k, i);
        }
    }
    return 0;
}

Linux x64环境下 gcc -O3 优化编译，再配合一个脚本分十个进程一起跑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/bin/sh
 
./a.out 0 1000000 &
./a.out 1000000 2000000 &
./a.out 2000000 3000000 &
./a.out 3000000 4000000 &
./a.out 4000000 5000000 &
./a.out 5000000 6000000 &
./a.out 6000000 7000000 &
./a.out 7000000 8000000 &
./a.out 8000000 9000000 &
./a.out 9000000 10000000 &
 
wait
1
2
3
4
5
6
7
...
success 6501826 1898766093
...
 
real    5m47.718s
user    29m25.453s
sys     0m5.094s

只用了5分多钟（即使单线程也只需30分钟），找到了唯一的正确答案：

1
1898766093

（不过，我还是觉得题目应该有完全0爆破的解法，期待作者出题文档的公开）


[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法

最后于 2023-9-29 05:11 被mb_mgodlfyn编辑 ，原因：
收藏
点赞・4
打赏
分享
最新回复 (3)
青眼白龙
雪    币： 3104
活跃值： (3767)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
青眼白龙 2023-9-29 13:25
2 楼
0
确实像是有优雅的数学的解法……
秋狝
雪    币： 19410
活跃值： (29069)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
秋狝 2023-9-29 21:36
3 楼
1
感谢分享
看场雪
雪    币： 10845
活跃值： (1049)
能力值： (RANK：190 )
在线值：
发帖
回帖
粉丝
私信
看场雪 3 2023-10-3 09:56
4 楼
0

赛期这么短的时间内，LZ的分析已经很不错了

WP中的‘负重’比喻也非常像
此题的出题思想源头 来自于一个计算机界的基本问题：进制转换
BASE64 是进制转换领域中的一个简单特例。然而对于混合进制之间的转换，并不容易
此题的设计思路是：当进制限定在{2, 4, 5, 6, 7, 8, 13}范围内时，挑战设计一种线性时间复杂度的进制转换算法
此题仅是一个特例（为了将破解的时间难度控制在‘有人能解，人又不太多’的范围内）

最后于 2023-10-3 09:57 被看场雪编辑 ，原因：
游客
登录 | 注册 方可回帖
　回帖　 表情 雪币赚取及消费
高级回复
返回