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., 
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 🙂
