The Few Chosen’s (TFC) CTF was this weekend and I found it really engrossing. I really enjoyed the breadth and quality of the challenges. Along with quality pwnables which I have really enjoyed lately was some excellent crypto challenges which take me back to my favourite CTF category.
This challenge, JAM, was a problem I haven’t run into a lot lately so I decided to write it up.
Jam - Crypto - 490 points
This challenge reads:
JAM
Found this amazing new game! It's called Jam! It's very hard, though, can
you help me advance faster?
18 solves.
The challenge comes with one python script file called main.py which contains the code as follows:
import random
import re
import string
import sys
from secret import secret, flag
import hashlib
def print_trade_help():
print("----=== Trade ===----")
print("1. Flag - 6 COIN(S)")
print("2. Random String - 1 COIN(S)")
print("3. Nothing - 1 COIN(S)")
print("---------------------")
def print_help():
print("----=== Menu ===----")
print("1. Work!")
print("2. Trade!")
print("3. Recover last session!")
print("4. Check your purse!")
print("5. Print recovery token!")
print("q. Quit!")
print("--------------------")
class Console:
def __init__(self):
self.__secret = secret.encode("utf-8")
self.__hash = hashlib.md5(self.__secret + b' 0').hexdigest()
self.__coins = 0
def work(self):
if self.__coins >= 5:
print("Can't work anymore! You're too tired!")
return
self.__coins += 1
print("You've worked really hard today! Have a coin!")
print("Purse: " + str(self.__coins) + " (+1 COIN)")
self.__hash = hashlib.md5(self.__secret + b' ' + str(self.__coins).encode("utf-8")).hexdigest()
print("To recover, here's your token: " + self.__hash)
def trade(self):
options = {
"1": (6, flag),
"2": (1, ''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(10))),
"3": (1, "You receive nothing.")
}
print_trade_help()
print("What would you like to buy?")
opt = input("> ")
if opt not in options.keys():
print("Invalid option!")
return
if options[opt][0] > self.__coins:
print("You do not have enough coins!")
return
else:
self.__coins -= options[opt][0]
print(options[opt][1])
print("Purse: " + str(self.__coins) + " (-" + str(options[opt][0]) + " COIN(S))")
def recover(self):
print("In order to recover, we need two things from you.")
print("1. How many coins did you have?")
print("> ", end="")
amt_coins = sys.stdin.buffer.readline()[:-1]
print("2. What was your recovery token?")
token = input("> ")
hash_tkn = self.__secret + b" " + amt_coins
hash_for_coins = hashlib.md5(hash_tkn).hexdigest()
if hash_for_coins != token:
print("Incorrect!")
return
self.__coins = int(re.sub("[^0-9]", "", amt_coins.decode("unicode_escape")))
print(self.__coins)
self.__hash = token
print("Recovered successfully!")
def check_purse(self):
print("Purse: " + str(self.__coins))
def get_recovery_token(self):
print(self.__hash)
def start_console(self):
options = {
"1": self.work,
"2": self.trade,
"3": self.recover,
"4": self.check_purse,
"5": self.get_recovery_token,
}
while True:
print_help()
inp = input("> ")
if inp == "q":
print("Quitting.")
sys.exit(0)
if inp not in options.keys():
print("Not a valid option!")
continue
try:
options[inp]()
except Exception:
pass
if __name__ == "__main__":
console = Console()
console.start_console()
However it’s easiest to come up with a plan if we just play the game a little, let’s take a look.
Since the main.py imports a secret flag in a file called secret.py we make one of those locally so we can examine how it works:
$ cat > secret.py
secret = "something"
flag = "TFCCTF{someflag}"
$ python main.py
----=== Menu ===----
1. Work!
2. Trade!
3. Recover last session!
4. Check your purse!
5. Print recovery token!
q. Quit!
--------------------
> 1
You've worked really hard today! Have a coin!
Purse: 1 (+1 COIN)
To recover, here's your token: 28aa352079e88c061ac48859ac3e7de9
----=== Menu ===----
1. Work!
2. Trade!
3. Recover last session!
4. Check your purse!
5. Print recovery token!
q. Quit!
--------------------
> 1
You've worked really hard today! Have a coin!
Purse: 2 (+1 COIN)
To recover, here's your token: 91ba2218985be3f4ba70706ffd53e9a9
----=== Menu ===----
1. Work!
2. Trade!
3. Recover last session!
4. Check your purse!
5. Print recovery token!
q. Quit!
--------------------
> 1
You've worked really hard today! Have a coin!
Purse: 3 (+1 COIN)
To recover, here's your token: d63d8854e6c967e12200ba89886618e1
----=== Menu ===----
1. Work!
2. Trade!
3. Recover last session!
4. Check your purse!
5. Print recovery token!
q. Quit!
--------------------
> 1
You've worked really hard today! Have a coin!
Purse: 4 (+1 COIN)
To recover, here's your token: 5aedb9541ae5b39f2d346f3a0b4eb5a0
----=== Menu ===----
1. Work!
2. Trade!
3. Recover last session!
4. Check your purse!
5. Print recovery token!
q. Quit!
--------------------
> 1
You've worked really hard today! Have a coin!
Purse: 5 (+1 COIN)
To recover, here's your token: a82e43f1272d4efc12bd599bc9f03f2d
----=== Menu ===----
1. Work!
2. Trade!
3. Recover last session!
4. Check your purse!
5. Print recovery token!
q. Quit!
--------------------
> 1
Can't work anymore! You're too tired!
----=== Menu ===----
1. Work!
2. Trade!
3. Recover last session!
4. Check your purse!
5. Print recovery token!
q. Quit!
--------------------
> 2
----=== Trade ===----
1. Flag - 6 COIN(S)
2. Random String - 1 COIN(S)
3. Nothing - 1 COIN(S)
---------------------
What would you like to buy?
> 1
You do not have enough coins!
Ok so the strategy seems clear to me.
The flag is available from the server that runs this service. If we can convince the server we have 6 or more coins. We are only allowed to work 5 times so we cannot get to 6 coins through work alone. We need a way to hack our bank balance :)
Since the game author is nice, they have made it possible for us to recover our session, kind of like a saved game. The recovery works by saving the number of coins you have hashed with some secret. Let’s look at the python code for how that happens:
self.__coins += 1
print("You've worked really hard today! Have a coin!")
print("Purse: " + str(self.__coins) + " (+1 COIN)")
self.__hash = hashlib.md5(self.__secret + b' ' + str(self.__coins).encode("utf-8")).hexdigest()
print("To recover, here's your token: " + self.__hash)
So our recovery token is just the MD5 hash of some secret plus our coin balance. E.g.:
md5('secretstringhere 1')
So when recovering our session, the above would recover the 1 coin we had in our balance.
Since we do not know the server side secret we cannot simply hash something ourselves, or can we? There’s 2 approaches that would work here, the simple case and the more crypto challenge case.
Simple Case
Since we have part of the plaintext ( <space>1)we can attempt to crack the secret portion by using an MD5 cracking tool like hashcat. I actually did try this very quickly with a 14gb wordlist but no luck. I found out later why. The secret was 32 bytes long so unlikely to easily crack.
Crypto Challenge Case
When you create a hash with a fixed secret and known suffix, and that hash is using Merkle–Damgård construction (the MD is MD5 stands for Merkle–Damgård in case you didn’t know :D ) then it is possible to perform a hash length extension attack and arrive at some other MD5 hash that will validate for some unknown prefix but with a new controlled suffix.
So when we have this:
h = md5('unknownprefix' + 'knownsuffix')
We can calculate some hash:
h' = mdf('unknownprefix' + 'knownsuffix' + 'padding' + 'controllable data')
Once calculated, even though we have no idea what 'unknownprefix' was, our hash will calculate as valid!
Solving
We can use one of a variety of tools to do this, commonly used is HashPump and another excellent one is hash_extender by Ron Bowes. Both tools operate very similarly but I used hash_extender for this attack as the hex output was quicker for me to integrate into a solve script.
Since the infrastructure was down some of the time during the CTF I wrote this offline against my own version of the script:
#!/usr/bin/python3
from pwn import *
local = False
# We'd need to bf this on the real server.
secretlen = 32
if local:
p = process("python main.py", shell=True)
else:
p = remote('34.65.54.58', 1343)
p.sendlineafter(b'> ', b'1') # Work once.
p.recvuntil(b'token: ')
token = p.recvline().decode().strip()
log.info('got token: %s' % token)
cmdline = "hash_extender -s %s -f md5 -d ' 1' -a '0' -l %d" % (token, secretlen)
log.info('doing hash length extension with hash_extender: %s' % cmdline)
hp = process(cmdline, shell=True)
hp.recvuntil(b'New signature: ')
exhash = hp.recvline().strip().decode()
log.info('new token: %s' % exhash)
hp.recvuntil(b'New string: ')
exhashdata = unhex(hp.recvline().strip())
log.info('hashdata: %s' % exhashdata)
hp.close()
p.sendlineafter(b'> ', b'3') # Recover last session
p.sendlineafter(b'1. How many coins did you have?\n', exhashdata[1:])
p.sendlineafter(b'2. What was your recovery token?\n> ', exhash.encode())
p.recvline()
result = p.recvline()
if b'Recovered successfully!' in result:
log.success("Attack success, getting flag...")
p.sendlineafter(b'> ', b'2') # Trade
p.sendlineafter(b'> ', b'1') # Flag
flag = p.recvline().decode()
log.success('Flag: %s' % flag)
else:
log.failure('attack failed :(')
p.close()
When running it it worked first go which was helpful!
$ ./solve.py
[+] Starting local process '/bin/sh': pid 1877
[*] got token: 7b396abe1c43f6279710c40931bde0e5
[*] doing hash length extension with hash_extender: hash_extender -s 7b396abe1c43f6279710c40931bde0e5 -f md5 -d ' 1' -a '0' -l 32
[+] Starting local process '/bin/sh': pid 1880
[*] new token: cad338385ef0a229544cf4749e3731cd
[*] hashdata: b' 1\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x10\x01\x00\x00\x00\x00\x00\x000'
[*] Process '/bin/sh' stopped with exit code 0 (pid 1880)
[+] Attack success, getting flag...
[+] Flag: TFCCTF{someflag}
[*] Stopped process '/bin/sh' (pid 1877)
Thanks to hofill and TFC folks for running such a good CTF with a great range of challenges. Made my otherwise rainy and cold weekend good.