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., , with . There is a quite simple relation emerging: (note: denotes empty input here). Using this relation, we can do the following. We know and and want to determine . Consider the following relation:

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 🙂

### Like this:

Like Loading...