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

import os

# pip install pycryptodome
from Crypto.Cipher import AES

flag = "bctf{??????????????????}"
secret = os.urandom(16)

my_message = "\n".join(
    [
        "Grate the raw potatoes with a cheese grater, place them into a bowl and cover completely with water. Let sit for 10 minutes.",
        "Drain the grated potatoes well; if this is not done thoroughly the potatoes will steam instead of fry.",
        "Mix in chopped onions by hand.",
        "Mix the egg OR flour into the hash brown mixture evenly. This will allow the hash browns to stay together when frying.",
        "Place a large frying pan on medium-high heat and add enough oil to provide a thin coating over the entire bottom of the pan.",
        "When the oil has come up to temperature apply a large handful of potatoes to the pan and reshape into a patty that is about 1/4-1/2 inch (6-12 mm) thick. The thinner the patty, the crispier the hash browns will be throughout.",
        "Flip when they are crisp and brown on the cooking side. They should also stick together nicely before they are flipped. This should take about 5-8 minutes.",
        "The hash browns are done when the new side is brown and crispy. This should take another 3-5 minutes.",
    ]
).encode()


def aes(block: bytes, key: bytes) -> bytes:
    assert len(block) == len(key) == 16
    return AES.new(key, AES.MODE_ECB).encrypt(block)


def pad(data):
    padding_length = 16 - len(data) % 16
    return data + b"_" * padding_length


def hash(data: bytes):
    data = pad(data)
    state = bytes.fromhex("f7c51cbd3ca7fe29277ff750e762eb19")

    for i in range(0, len(data), 16):
        block = data[i : i + 16]
        state = aes(block, state)

    return state


def sign(message, secret):
    return hash(secret + message)


def main():
    print("Recipe for hashbrowns:")
    print(my_message)
    print("Hashbrowns recipe as hex:")
    print(my_message.hex())
    print("Signature:")
    print(sign(my_message, secret).hex())
    print()

    print("Give me recipe for french fry? (as hex)")
    your_message = bytes.fromhex(input("> "))
    print("Give me your signiature?")
    your_signiature = bytes.fromhex(input("> "))
    print()

    print("Your recipe:")
    print(your_message)
    print("Your signiature:")
    print(your_signiature.hex())
    print()

    if b"french fry" not in your_message:
        print("That is not a recipe for french fry!!")
    elif your_signiature != sign(your_message, secret):
        print("That is not a valid signiature!!")
    else:
        print("Thank you very much. Here is your flag:")
        print(flag)


if __name__ == "__main__":
    main()

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

The Challenge#

The Solution#

The Challenge

The Solution