在我导安排下作为防守方出了个题到看雪 2023·KCTF 上, 第十一题 步步逼近, 有幸拿了精致奖, 第一次参加这类比赛, 属实是走大运了. 这里把出题思路和题解贴一下, 和看雪的是一样的, 原文链接 https://bbs.kanxue.com/thread-278478.htm.
题目分析
输入与结果
简单试错以及使用 IDA 获取伪代码可以知道题目的输入是一个不超过 10 位的十进制数字, 并且将范围限制在了 4K (0x1000) 至 4G (0x100000000) 之间 (包含两头端点). 所以解出此题的关键在于弄清楚题目如何对输入的数字进行验证.
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
|
printf("Please input: ");
v0 = 0;
while ( 1 )
{
v1 = _getchar();
if ( v1 == 10 )
break;
v2 = v0 + 1;
_Buffer[v0] = v1;
if ( v0 + 1 >= 0xB )
goto LABEL_43;
_Buffer[v2] = 0;
if ( v0 == 9 && _getchar() != 10 )
goto LABEL_41;
++v0;
if ( v2 >= 10 )
goto LABEL_10;
}
if ( v0 >= 0xB )
{
LABEL_43:
__report_rangecheckfailure();
__debugbreak();
JUMPOUT(*(_DWORD *)__security_check_cookie);
}
_Buffer[v0] = 0;
LABEL_10:
v3 = 0;
if ( _Buffer[0] )
{
while ( ++v3 <= 10 )
{
if ( !_Buffer[v3] )
goto LABEL_15;
}
v3 = -1;
}
LABEL_15:
if ( sscanf_s(_Buffer, "%lld", &x) == 1 )
{
v4 = sprintf_s(v18, 0xBu, "%lld", x);
if ( v3 > 0 && v4 > 0 && v3 == v4 )
{
v5 = 0;
while ( _Buffer[v5] == v18[v5] )
{
if ( ++v5 >= v3 )
{
if ( SHIDWORD(x) >= 0 && (SHIDWORD(x) > 0 || (_DWORD)x) )
{
v6 = FindWindowW(L"OLLYDBG", 0);
v7 = HIDWORD(x);
v8 = x;
if ( v6 )
{
v8 = x | 0xFFFF;
LODWORD(x) = x | 0xFFFF;
}
if ( __PAIR__(HIDWORD(x), v8) - 4096 <= 0xFFFFF000 )
|
如果输入错误, 则弹框提示 Wrong answer!, 输入正确则弹框提示 Accepted!.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
MessageBoxW(0, L"Accepted!", L"Result", 0x40u);
return 0;
}
}
}
}
}
break;
}
}
}
}
LABEL_41:
MessageBoxW(0, L"Wrong answer!", L"Result", 0x10u);
|
验证机制
程序只有一些简单的反调试检测, 没有太多 anti, 主要难度还是在算法原理上, 因此可以比较容易逆向出算法流程和对应的伪代码.
核心部分是一个编码算法和一个解码算法, 而输入的序列号是两个算法的参数, 程序通过对随机输入进行编码与解码操作, 并检测是否能正确还原出原始输入序列来判断序列号是否正确.
用 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
|
while ( 1 )
{
v51 = v16;
v43 = v15;
if ( v18 >= 10000 && (v15 < 0 || v15 <= 0 && !v16) )
break;
if ( v19 >= 20000 )
{
LABEL_38:
WaitForSingleObject(g_worker_mutex, 0xFFFFFFFF);
g_has_error = 1;
ReleaseMutex(g_worker_mutex);
v2 = v49;
goto LABEL_39;
}
if ( v18 >= 10000 )
{
v22 = *(_DWORD *)&v14[4 * v19];
v23 = __PAIR__(v15, v16) % v22;
HIDWORD(v53) = HIDWORD(v23);
v24 = __PAIR__(v15, v51) / v22;
v15 = (unsigned __int64)(__PAIR__(v15, v51) / v22) >> 32;
v16 = v24;
v14 = v45;
*(_DWORD *)&v50[4 * v19++] = v23;
v18 = v46;
v17 = (int)v40;
}
else
{
v20 = *v40 + *(_DWORD *)(v17 + v54) * __PAIR__(v15, v16);
v15 = HIDWORD(v20);
v55 = v20;
v39 = *(_DWORD *)&v45[4 * v19];
v16 = v20;
v53 = (signed __int64)__PAIR__(v43, v51) % v39;
if ( (signed __int64)((signed __int64)__PAIR__(v43, v51) / v39 * v20) < (signed __int64)__PAIR__(v56, v58) )
{
v18 = v46 + 1;
v14 = v45;
v17 = (int)(v40 + 1);
goto LABEL_12;
}
v21 = (signed __int64)__PAIR__(v43, v51) / v39;
v15 = v21 >> 32;
v16 = v21;
v14 = v45;
*(_DWORD *)&v50[4 * v19++] = v53;
v18 = v46;
v17 = (int)v40;
}
}
|
解码部分
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
|
while ( 1 )
{
v54 = v30;
v52 = v27;
if ( v25 < 0 && (v27 < 0 || v27 <= 0 && !v30) )
break;
if ( v28 < 0 )
goto LABEL_38;
if ( v25 < 0 )
{
v34 = *((_DWORD *)in_r + v28);
HIDWORD(v53) = (unsigned __int64)(__PAIR__(v27, v54) % v34) >> 32;
v35 = __PAIR__(v27, v54) / v34;
v27 = (unsigned __int64)(__PAIR__(v27, v54) / v34) >> 32;
v30 = v35;
v33 = (unsigned int)(__PAIR__(v52, v54) % v34) == v49[v28];
LABEL_34:
if ( !v33 )
goto LABEL_38;
v25 = v47;
--v28;
v29 = (int)v41;
v26 = v44;
}
else
{
v31 = *(_DWORD *)v41 + *(_DWORD *)(v26 + v29) * __PAIR__(v27, v30);
v27 = HIDWORD(v31);
LODWORD(v53) = v31;
v32 = *((_DWORD *)in_r + v28);
v30 = v31;
v55 = __PAIR__(v52, v54) % v32;
b_high = (unsigned __int64)(__PAIR__(v52, v54) / v32) >> 32;
b_low = __PAIR__(v52, v54) / v32;
if ( (signed __int64)(__PAIR__(v52, v54) / v32 * v31) >= *(_QWORD *)parameters )
{
v30 = b_low;
v27 = b_high;
v33 = v55 == v49[v28];
goto LABEL_34;
}
v25 = v47 - 1;
v26 = v44;
v29 = (int)(v41 - 4);
--v47;
v41 -= 4;
}
}
|
算法流程不是太复杂, 可以看出是一种自定义的混合进制编解码算法, 而输入的序列号作为参数来控制算法正确运行, 算法涉及到的关键参数如下图:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
in_r = _calloc(10000u, 4u);
in = _calloc(10000u, 4u);
v2 = in;
v49 = in;
out_r = (char *)_calloc(20000u, 4u);
v4 = out_r;
v45 = out_r;
out = (char *)_calloc(20000u, 4u);
b_low = *(_DWORD *)parameters;
v17 = (int)v49;
b_high = *((_DWORD *)parameters + 1);
|
b: 输入的序列号整数.in: 随机输入序列.in_r: 随机输入序列的进制序列.out_ 开头的则是输出结果.
解码算法流程与编码算法几乎一致, 但是把编码的输入和输出交换了一下, 同时进行了倒序处理, 并对解码序列与原始随机输入序列进行比较, 判断是否还原成功.
而验证步骤的关键伪代码还原如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
g_has_error = 0;
v9 = 0;
if ( check_error_in_x(__PAIR__(v7, v8)) )
{
if ( !g_has_error )
{
g_has_error = 0;
if ( check_error_in_x(__PAIR__(v7, v8) - 1) )
{
if ( g_has_error )
v9 = 1;
}
}
}
|
要求对于输入的 b 能够使算法正确工作, 但是 b - 1 不能使算法正确工作.
解题思路
暴力枚举
此题的输入数据范围是介于 4K 到 4G 之间的一个整数, 可以考虑把核心算法单独摘出来整理重写, 然后进行暴力枚举.
但是枚举的难度在于, 原程序使用的随机输入序列长度为 10000, 且使用多线程进行了约 10000 轮测试, 也就是说纯随机情况下, 如果数据量不够大, 很可能造成误判, 从而无法枚举出正确的序列号, 因此枚举的时间成本很高, 只是一个保底下策.
公式枚举
程序的算法是一个用于混合进制序列的编解码算法, 且需要一个控制参数来使算法正确工作. 而程序的验证机制是 b 正确且 b - 1 错误, 可以合理推测能够使算法正确工作的参数不止一个, 应该是一个连续区间, 且题目的正确答案是这个区间的左端点, 因此我们需要找出参数的取值规律, 从而快速求解答案.
翻一下逆向后的代码, 可以找到程序使用的进制集是 { 2, 4, 5, 6, 7, 8, 13 }, 且输入和输出使用了同一组进制.
1
2
3
4
5
| .rdata:004031C8 _TEST_RADIX_LEN:
.rdata:004031C8 dw 7, 0
.rdata:004031CC ; int TEST_RADIX[]
.rdata:004031CC _TEST_RADIX dd 2, 4, 5, 6, 7, 8, 13 ; DATA XREF: do_error_check(x)+114
.rdata:004031CC ; do_error_check(x)+15E
|
猜想 b 的取值与进制组合有关, 因此可以从简单的入手, 暴力枚举小区间, 寻找规律.
分别设置以下几种方式去进行枚举, 可以得到正确的取值区间如下:
- 输入进制
{ 2 }, 输出进制 { 2 }: [1, 5], [7, 18], [21, 39], [43, 68], [73, 105], ...
- 输入进制
{ 2 }, 输出进制 { 3 }: [1, 7], [11, 26], [33, 57], [67, 100], [113, 155], ...
- 输入进制
{ 3 }, 输出进制 { 3 }: [1, 10], [17, 38], [51, 84], [103, 148], ...
- 输入进制
{ 2 }, 输出进制 { 2, 3 }: [1, 5], [7, 7], [11, 18], [21, 26], [33, 39], [43, 57], [67, 68], [73, 100], [113, 150], ...
- 输入进制
{ 2, 3 }, 输出进制 { 2, 3 }: [1, 5], [7, 7], [17, 18], [21, 26], [33, 38], [51, 57], [67, 68], [73, 84], [113, 148], ...
观察一下可以发现, 对于混合进制的情况, 正确的取值区间是通过单个的输入输出进制的取值区间取交集得到的:
{ 2 }_{ 2, 3 } = { 2 }_{ 2 } & { 2 }_{ 3 }{ 2, 3 }_{ 2, 3 } = { 2 }_{ 2, 3 } & { 3 }_{ 3 }
因此, 只要能找出单个的输入输出进制的取值区间规律就能解出题目.
继续观察寻找规律, 可以发现规律:
{ 2 }_{ 2 }: [4 * n^2 - (4 + 2) * n + 3, 4 * n^2 + n]{ 2 }_{ 3 }: [6 * n^2 - (6 + 2) * n + 3, 6 * n^2 + n]{ 3 }_{ 3 }: [9 * n^2 - (9 + 2) * n + 3, 9 * n^2 + n]
因此可以得到通项公式为: [r1 * r2 * n^2 - (r1 * r2 + 2) * n + 3, r1 * r2 * n^2 + n]
而题目使用了 7 种不同的进制, 且输入输出进制相同, 因此共需要枚举 21 种情况, 然后取交集最终得到题目里正确的取值范围, 并取左端点作为序列号.
这里需要注意的是, 取交集这个操作并不高效, 但是可以翻过来操作, 每次将错误取值区间筛去, 能够更快速的计算出正确答案, 这里贴一下核心计算代码.
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
| void search_b(long long start, long long end)
{
long long p = 0;
long long n_s = 0;
long long n_e = 0;
long long b1 = 0;
long long b2 = 0;
long long b_count = end - start + 1;
bool* full_set = calloc((size_t)b_count, sizeof(bool));
if (!full_set)
return;
memset(full_set, 1, (size_t)b_count * sizeof(bool));
for (int i = 0; i < in_r_len; i++) {
for (int j = i; j < out_r_len; j++) {
p = in_r[i] * out_r[j];
n_s = left_floor(p, start);
n_e = right_ceil(p, end);
for (long long n = n_s; n <= n_e; n++) {
b1 = left(p, n);
b2 = right(p, n);
if (b1 < start)
b1 = start;
if (b2 > end)
b2 = end;
for (long long b_idx = b1 - start; b_idx <= b2 - start; b_idx++) {
full_set[b_idx] = 0;
}
}
}
}
for (long long b_s = 0; b_s < b_count; b_s++) {
if (full_set[b_s]) {
for (long long b_e = b_s; b_e < b_count; b_e++) {
if (!full_set[b_e]) {
printf("Valid: [%lld, %lld] Count: %lld\n", b_s + start, b_e - 1 + start, b_e - b_s);
b_s = b_e;
break;
}
}
}
}
if (full_set)
free(full_set);
return;
}
|
最终答案
最后算出来题目的进制组合下 100 亿范围内只有这些正确区间:
1
2
3
4
| Valid: [1, 5] Count: 5
Valid: [7, 9] Count: 3
Valid: [1898766093, 1898766391] Count: 299
Valid: [79233213543, 79233230703] Count: 17161
|
题目要求范围在 4K 到 4G 的范围, 因此序列号为 1898766093, 输入之后得到正确结果 Accepted!.
题目及源代码
看雪的帖子里有下载地址, 这里也贴一下蓝奏云的下载链接.
蓝奏云: 2023KCTF竞赛.zip