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 🙂