This, right here, is probably my favorite challenge out of the entire CTF. What we have here is a rust source code file, aswell as the server IP and port. There are also three hints:
- Your IGUID is not used as an index into the hashmap. Only the result of the “proprietary algorithm” is used.
- Although your IGUID is not used as an index into the hashmap… it is still stored as a vector of bytes in “used_keys”.
- How proprietary is this “proprietary algorithm”, anyway?
Vulnerability hunting
So, first, we’re going to take a look at the Rust source code. At the beginning of the main function, some intialization is taking place:
Essentially, the flag is being read from some irrelevant source, and a hashset and hashmap are created (for all intents and purposes currently: they’re basically dictionaries). Some decoration text is printed, and some accounts containing a dummy flag are created. We don’t need to worry about them; they aren’t relevant to the solution.
Next, a loop is started, which basically just continuously asks for us to enter a command and then reacts accordingly. The commands are as follows:
The “help”, “info”, and “rover” commands just print out static text. It’s the flag related ones we’re after that offer us the ability to submit data the server will respond to.
Let’s first have a look at the “plant a flag” and “check a flag” commands. After all, it’s the whole reason we’re here, no?
You may have spotted it already. As you can see, there are two ways we can get the flag printed to us. One way is if we wait 100 years or so and are ready to “begin colonization”. Another way is if we manage to supply an input which isn’t in the used_iguids dictionary but who’s hash already exists in the plot map dictionary.
This is a textbook hash collision attack. If we somehow provide two inputs such that HASH(input1)==HASH(input2) without those inputs being identical, we will be able to satisfy the criteria above and move the program execution right where we want it, and to that “fatal error” you see above.
Now, that’s great! We basically found the vulnerability. But there’s one more thing: we don’t know the hashing algorithm used! I mean, hello? How are we going to find a hash collision if we don’t even know how to hash our input?
One clue we can get regarding the algorithm is the “rover” text that gets outputted when we enter the “rover” command.
340282366920938463463374607431768211456 is just the expanded version of 2**128. Given Hint #3 (“How proprietary is this “proprietary algorithm”, anyway?”), we could use that possible outputs number as a clue to look for.
A general rule for hashing is that the amount of possible outputs is equal to 2**[bit_size_of_hash]. Since we have 2**128, we are looking for an algorithm that generates 128 bit hashes, which are 16 bytes.
Now, think about it. What is commonly known, has horrendous-enough hash collision resistence, and outputs hashes of 16 bytes? That’s right! MD5. So, let’s take a shot in the dark and assume that the back-end “proprietary” algorithm here is MD5.
Exploitation
All we really have to do now is just find two values that hash to the same hash (under MD5). It’s simple enough really. Infact, I could go and lie about how cool I am, using HashClash or something like that. But the actual answer is that I actually spent most of my time trying to understand HashClash, until I eventually gave up and just googled until I found someone mention two inputs that hash to the same hash on StackOverflow.
Anyway, with that out of the way, we’re set. Let’s design the exploit script.
from hashlib import md5
from pwn import *
#"proprietary algorithm" is a hashing function
#when we execute "plant a flag" on some IGUID, the used_iguids array gets our input appended to it
#then, it uses this hashing function to place our flag into the main hashmap under the index HASH(input)
#when we execute "check a flag", however, then if the used_iguids array does NOT contain our input, we..
# 1. compute HASH(input2)
# 2. check the main hashmap if it contains any entry with the index of HASH(input2)
# 3. if it does, a "FLAG ALREADY FOUND" error is created, printing out the flag. otherwise, print that no flag was found
#this means that, since used_iguids deals with the PLAINTEXT rather than the HASH RESULT,
#if we create an "input2" value such that HASH(input2) == HASH(input1), where "input1" is what we specified in the "plant a flag" option,
#we will be able to abuse the aforementioned "check a flag" functionality to throw the "FLAG ALREADY FOUND" error and, thus, get the flag and bypass the "wait 100 years" functionality
#all we need to do now is figure out the "proprietary algorithm" used, so we can perform an offline hash collision to generate our two inputs
#the rover text tells us that 340282366920938463463374607431768211456 different outputs are generated using the algorithm
#since that number is 2^128, it could be determined that the hash output itself is 128 bits
#MD5 is the most commonly used algorithm with an output of 128 bits
#this StackOverflow comment shares us two messages with the same MD5 hash: https://stackoverflow.com/a/35224715
msg1 = bytes.fromhex("4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2")
msg2 = bytes.fromhex("4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2")
assert(msg1 != msg2)
assert(md5(msg1).digest() == md5(msg2).digest())
#we will now connect to the instance
with remote("crypto.bcactf.com", 49157) as r:
#create our IGUID with the first message
r.sendlineafter(b"Enter a command:\n", b"plant a flag")
r.sendlineafter(b"hexadecimal):\n", msg1.hex().encode("ascii"))
#now, we will check a flag with our second message, which is different from msg1 but with the same hash as msg1
r.sendlineafter(b"Enter a command:\n", b"check a flag")
r.sendlineafter(b"hexadecimal):\n", msg2.hex().encode("ascii"))
r.interactive()
There’s our flag right there. bcactf{[email protected][email protected][email protected]}