RomHack CTF 2021 - PXEboot

reverse

PXEboot

The challenge description gave us a link to an http server containing a qemu command.
qemu-system-i386 -boot n -device e1000,netdev=mynet0 -netdev user,id=mynet0,bootfile=http://46.101.23.188:30172/

By launching it and sniffing the traffic with tcpdump we were able to extract the binary it was downloading from the server.

Analyzing the binary

The binary was a boot file for a x86_64 system. Upon execution it asked for an input, outputted some data and returned an error.

Static analysis through ghidra lead to the discovery of some functions, many of which had weird opcodes not well understood by the decompiler. Since we could not really understand what was happening we ended up attaching gdb to the binary through qemu, getting the base address, setting it up correctly in ghidra, and, by putting up some breakpoints, we managed to get hold of the function reading our input.

A note on manual fuzzing

The I/O functions of the binary were hard to understand since they used some hardware interrupts. One of my teammates ended up fuzzing the input manually and managed to understand that we were supposed to enter a number of integers in the range 0-127 separated by spaces. Moreover those integers had to be ordered smaller to bigger, without repetitions.

A mutating binary

The binary was then reading our input, loading it into an array of integers, and calling a function which returned executable code in the memory area 0x100000.
We tried to disassemble that function but ghidra was unable to understand it and even with the help of gdb it seemed like the instruction pointer was jumping around in memory leading nowhere useful (we even managed to get a crash just by stepping forward in the code).
After a while of trying to understand what that function was doing, we ended up just setting a breakpoint at 0x100000 and hoping that the code generated was not dependent on our input, and indeed it was not.

Here are some examples of codes 
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
0x100000:	push   ebp
0x100001:	mov    ebp,esp
0x100003:	mov    eax,0x14b549
0x100008:	pop    ebp
0x100009:	ret    
0x10000a:	nop
0x10000b:	nop
 
0x100000:	push   ebp
0x100001:	mov    ebp,esp
0x100003:	mov    eax,DWORD PTR [ebp+0x2c]
0x100006:	mov    DWORD PTR [eax],0x0
0x10000c:	mov    eax,0x38eaa8
0x100011:	pop    ebp
0x100012:	ret    
0x100013:	nop

0x100000:	push   ebp
0x100001:	mov    ebp,esp
0x100003:	mov    eax,DWORD PTR [ebp+0x30]
0x100006:	mov    DWORD PTR [eax],0x0
0x10000c:	mov    eax,0xdaf7c7
0x100011:	pop    ebp
0x100012:	ret
  
0x100000:	push   ebp
0x100001:	mov    ebp,esp
0x100003:	mov    eax,DWORD PTR [ebp+0x34]
0x100006:	mov    DWORD PTR [eax],0x0
0x10000c:	mov    eax,0xf65013
0x100011:	pop    ebp
0x100012:	ret    
0x100013:	nop
 
0x100000:	push   ebp
0x100001:	mov    ebp,esp
0x100003:	mov    eax,DWORD PTR [ebp+0x34]
0x100006:	mov    eax,DWORD PTR [eax]
0x100008:	cmp    eax,DWORD PTR [ebp+0xc]
0x10000b:	jge    0x100014
0x10000d:	mov    eax,0x7e7ded
0x100012:	jmp    0x100019
0x100014:	mov    eax,0xaae625
0x100019:	pop    ebp
0x10001a:	ret
 
0x100000:	push   ebp
0x100001:	mov    ebp,esp
0x100003:	mov    eax,DWORD PTR [ebp+0x34]
0x100006:	mov    eax,DWORD PTR [eax]
0x100008:	test   eax,eax
0x10000a:	jle    0x100013
0x10000c:	mov    eax,0xbd9e77
0x100011:	jmp    0x100018
0x100013:	mov    eax,0xc99e8f
0x100018:	pop    ebp
0x100019:	ret
 
0x100000:	push   ebp
0x100001:	mov    ebp,esp
0x100003:	mov    eax,DWORD PTR [ebp+0x34]
0x100006:	mov    eax,DWORD PTR [eax]
0x100008:	mov    edx,eax
0x10000a:	mov    eax,DWORD PTR [ebp+0x8]
0x10000d:	add    eax,edx
0x10000f:	movzx  eax,BYTE PTR [eax]
0x100012:	test   al,al
0x100014:	jns    0x10001d
0x100016:	mov    eax,0xc1948a
0x10001b:	jmp    0x100022
0x10001d:	mov    eax,0x8fe835
0x100022:	pop    ebp
0x100023:	ret
 
0x100000:	push   ebp
0x100001:	mov    ebp,esp
0x100003:	mov    eax,DWORD PTR [ebp+0x2c]
0x100006:	mov    edx,DWORD PTR [eax]
0x100008:	mov    eax,DWORD PTR [ebp+0x34]
0x10000b:	mov    eax,DWORD PTR [eax]
0x10000d:	mov    ecx,eax
0x10000f:	mov    eax,DWORD PTR [ebp+0x8]
0x100012:	add    eax,ecx
0x100014:	movzx  eax,BYTE PTR [eax]
0x100017:	movzx  ecx,al
0x10001a:	mov    eax,DWORD PTR [ebp+0x10]
0x10001d:	add    eax,ecx
0x10001f:	movzx  eax,BYTE PTR [eax]
0x100022:	movzx  eax,al
0x100025:	add    edx,eax
0x100027:	mov    eax,DWORD PTR [ebp+0x2c]
0x10002a:	mov    DWORD PTR [eax],edx
0x10002c:	mov    eax,0x557e2f
0x100031:	pop    ebp
0x100032:	ret 
  
0x100000:	push   ebp
0x100001:	mov    ebp,esp
0x100003:	mov    eax,DWORD PTR [ebp+0x30]
0x100006:	mov    edx,DWORD PTR [eax]
0x100008:	mov    eax,DWORD PTR [ebp+0x34]
0x10000b:	mov    eax,DWORD PTR [eax]
0x10000d:	mov    ecx,eax
0x10000f:	mov    eax,DWORD PTR [ebp+0x8]
0x100012:	add    eax,ecx
0x100014:	movzx  eax,BYTE PTR [eax]
0x100017:	movzx  ecx,al
0x10001a:	mov    eax,DWORD PTR [ebp+0x14]
0x10001d:	add    eax,ecx
0x10001f:	movzx  eax,BYTE PTR [eax]
0x100022:	movzx  eax,al
0x100025:	add    edx,eax
0x100027:	mov    eax,DWORD PTR [ebp+0x30]
0x10002a:	mov    DWORD PTR [eax],edx
0x10002c:	mov    eax,0xca9362
0x100031:	pop    ebp
0x100032:	ret

0x100000:	push   ebp
0x100001:	mov    ebp,esp
0x100003:	mov    eax,DWORD PTR [ebp+0x34]
0x100006:	mov    eax,DWORD PTR [eax]
0x100008:	lea    edx,[eax+0x1]
0x10000b:	mov    eax,DWORD PTR [ebp+0x34]
0x10000e:	mov    DWORD PTR [eax],edx
0x100010:	mov    eax,0xf65013
0x100015:	pop    ebp
0x100016:	ret

0x100000:	push   ebp
0x100001:	mov    ebp,esp
0x100003:	mov    eax,DWORD PTR [ebp+0x34]
0x100006:	mov    eax,DWORD PTR [eax]
0x100008:	cmp    eax,DWORD PTR [ebp+0xc]
0x10000b:	jge    0x100014
0x10000d:	mov    eax,0x7e7ded
0x100012:	jmp    0x100019
0x100014:	mov    eax,0xaae625
0x100019:	pop    ebp
0x10001a:	ret
 
0x100000:	push   ebp
0x100001:	mov    ebp,esp
0x100003:	mov    eax,DWORD PTR [ebp+0x34]
0x100006:	mov    eax,DWORD PTR [eax]
0x100008:	test   eax,eax
0x10000a:	jle    0x100013
0x10000c:	mov    eax,0xbd9e77
0x100011:	jmp    0x100018
0x100013:	mov    eax,0xc99e8f
0x100018:	pop    ebp
0x100019:	ret

0x100000:	push   ebp
0x100001:	mov    ebp,esp
0x100003:	mov    eax,DWORD PTR [ebp+0x34]
0x100006:	mov    eax,DWORD PTR [eax]
0x100008:	mov    edx,eax
0x10000a:	mov    eax,DWORD PTR [ebp+0x8]
0x10000d:	add    eax,edx
0x10000f:	movzx  edx,BYTE PTR [eax]
0x100012:	mov    eax,DWORD PTR [ebp+0x34]
0x100015:	mov    eax,DWORD PTR [eax]
0x100017:	lea    ecx,[eax-0x1]
0x10001a:	mov    eax,DWORD PTR [ebp+0x8]
0x10001d:	add    eax,ecx
0x10001f:	movzx  eax,BYTE PTR [eax]
0x100022:	cmp    dl,al
0x100024:	ja     0x10002d
0x100026:	mov    eax,0x6de42c
0x10002b:	jmp    0x100032
0x10002d:	mov    eax,0xc99e8f
0x100032:	pop    ebp
0x100033:	ret

0x100000:	push   ebp
0x100001:	mov    ebp,esp
0x100003:	sub    esp,0x18
0x100006:	mov    DWORD PTR [esp],0x101000
0x10000d:	mov    eax,DWORD PTR [ebp+0x28]
0x100010:	call   eax
0x100012:	mov    eax,0x9080c5
0x100017:	leave  
0x100018:	ret
 
0x100000:	push   ebp
0x100001:	mov    ebp,esp
0x100003:	mov    eax,0x1
0x100008:	pop    ebp
0x100009:	ret

We guessed that the result value in eax was the one deciding which code should be loaded on the next run in the loop. Moreover on the stack we found our input and two arrays of 128 bytes. By reading the codes we realized that they were using our input as indexes for the two arrays, summing the values contained at the locations specified. More codes allowed us to have an upper and lower bounds on those two sums, specifically the first one had to be greather or equal than 1579 and the second one lower or equal than 244.
I dumped the two arrays and passed them to one of my teammates, which implemented a solution for the knapsack problem setting up the weights of the values in a smart way.

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
def knapsack01_dp(items, limit):
    table = [[0 for w in range(limit + 1)] for j in range(len(items) + 1)]

    for j in range(1, len(items) + 1):
        wt, val = items[j-1]
        for w in range(1, limit + 1):
            if wt > w:
                table[j][w] = table[j-1][w]
            else:
                table[j][w] = max(table[j-1][w],
                                  table[j-1][w-wt] + val)

    result = []
    w = limit
    for j in range(len(items), 0, -1):
        was_added = table[j][w] != table[j-1][w]

        if was_added:
            wt, val = items[j-1]
            result.append(items[j-1])
            w -= wt

    return result, len(result)

x = 244 #sum(data2[...]) <= 244
y = 1579 #sum(data1[...]) >= 1579

items = [(d,data1[data2.index(d)]-d) for d in data2]

sol, l = knapsack01_dp(items, x)
print(l)
s1 = 0
s2 = 0
for x in sol:
    s1 += data1[data2.index(x[0])]
    s2 += x[0]

print(s1, s2)

indici = []

for x in sol:
    indici.append(data2.index(x[0]))

There was probably a more efficient solution but this allowed us to obtain a list of indexes satisfying the constraints.
[8, 22, 28, 32, 34, 37, 43, 48, 50, 53, 69, 70, 76, 84, 104, 108, 112, 117, 127]

By inputting them in the program we got the flag:
HTB{1t3ms_0v3r_PXE}