What is this?
This is my writeup for Hashbrown, a cryptography challenge from this year's BuckeyeCTF. BuckeyeCTF is a cybersecurity competition hosted annually by the Ohio State University Cybersecurity Club; Anyone can join, but their are special divisons for undergraduates and for OSU students.
The Challenge
The Solution
The first thing I noticed was the recipe for hashbrowns. I haven't tried it, and I'm not an expert on hashbrown technique, but it sounds good.
The second thing I noticed was the functionality of the code. It generates a 16 byte secret key and uses that secret key to sign a message. It then asks the user for a recipe for french fry[sic], and a corresponding signature. If the signature is valid, the flag is revealed.
If an effective digital signature system is used, this is not a CTF challenge (at least not in the crypto category). However, this is a CTF challenge, so let's examine the signature scheme.
The signature is computed by concatenating the secret with the message, and the hashing the result. The hash function first pads the message to 16 bytes (Note that if the message length is already a multiple of 16, 16 bytes of padding are added. Always pay close attention to the code!), then it iteratively encrypts 16 byte blocks of the message with AES, using the previous output as the key. This process starts with a constant initial state, and the final result is used directly as the output of the hash.
What is interesting about this process is that the state after block n, is a pure function of only the state after block n-1 and the contents of block n. This is the crux of the solution; we are given the state of hash after the secret and recipe, and we control our "french fry recipe". Then, we can compute the hash after the secret, recipe, and our recipe with aes(our_recipe, given_state).