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

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:
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 🙂