TU CTF – Hash’n’bake

This challenge, worth 200 points, exhibits a trivial (and, obviously, non-secure) hash function with the objective to find a keyed hash. The description:

A random goat from Boston hashed our password!
Can you find the full output?

The hash function is defined as:

def to_bits(length, N):
    return [int(i) for i in bin(N)[2:].zfill(length)]
def from_bits(N):
    return int("".join(str(i) for i in N), 2)
CONST2 = to_bits(65, (2**64) + 0x1fe67c76d13735f9)
CONST = to_bits(64, 0xabaddeadbeef1dea)
def hash_n_bake(mesg):
    mesg += CONST
    shift = 0
    while shift < len(mesg) - 64:
        if mesg[shift]:
            for i in range(65):
                mesg[shift + i] ^= CONST2[i]
        shift += 1
    return mesg[-64:]
def xor(x, y):
    return [g ^ h for (g, h) in zip(x, y)]

The following computations will give the hash

PLAIN_1 = "goatscrt"
PLAIN_2 = "tu_ctf??"
def str_to_bits(s):
    return [b for i in s for b in to_bits(8, ord(i))]
def bits_to_hex(b):
    return hex(from_bits(b)).rstrip("L")
if __name__ == "__main__":
    with open("key.txt") as f:
        KEY = to_bits(64, int(f.read().strip("\n"), 16))
    print PLAIN_1, "=>", bits_to_hex(hash_n_bake(xor(KEY, str_to_bits(PLAIN_1))))
    print "TUCTF{" + bits_to_hex(hash_n_bake(xor(KEY, str_to_bits(PLAIN_2)))) + "}"
#  Output
#  goatscrt => 0xfaae6f053234c939
#  TUCTF{****REDACTED****}

So, the problem is: we need to compute the hash without knowing the key (or brute forcing it). The first observation we make is that the hash function is a truncated affine function, i.e., h(m) = f((m \cdot 2^{64} \oplus \texttt{CONST})\cdot \texttt{CONST}_2), with f(a \oplus b) = f(a) \oplus f(b) . There is a quite simple relation emerging: h(k \oplus m) = h(k) \oplus h(m) \oplus h(0) (note: h(0) denotes empty input here). Using this relation, we can do the following. We know h(k \oplus m_1) and h(m_2) and want to determine h(k \oplus m_2). Consider the following relation:

\begin{array}{rl} h(k \oplus m_2) = & h(k) \oplus h(m_2) \oplus h(0) \\ = & h(k) \oplus h(m_1) \oplus h(0) \oplus h(m_1) \oplus h(m_2) \phantom{\bigg(} \\ = & h(k \oplus m_1) \oplus h(m_1) \oplus h(m_2). \end{array}

All terms on the last line of the above equation are known. So, we can easily compute the hash, even without knowing the key. Ha-ha! Computing the above relation using Python can be done in the following manner:

xor(xor(to_bits(64, 0xfaae6f053234c939), hash_n_bake(str_to_bits(PLAIN_1))),hash_n_bake(str_to_bits(PLAIN_2)))

This gives the flag TUCTF{0xf38d506b748fc67}. Sweet 🙂


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s