#!/usr/bin/env python3
from itertools import product
from time import perf_counter

TARGET = 0x00E7933B61CF5A1E
FINAL_KEY = bytes.fromhex("050a0717070412070615")
HASH = "2bda2998d9b0ee197da142a0447f672537598dad8f8805ce708ba8c4f67ce367639bae9ac6b3e1a84cebb7b403297b794015e9ce43edfb0668ddaa973ebc7e87716f6b30598ba30945d84485e61c1027"
DUMP = bytes.fromhex(
    "d8ad88dad8ad88da54556b8dc807397cc58f31c6d38f31c6c51f5f0841176b7"
    "4d2386b8ec507397cd5137e8c53176b74c51f638ccc187f8cc5175f3053a2f68e"
    "d307397c42083ffc49176b74d41f638cd3386b8ec21f5f0855426afdd4187f8c"
    "c307397c4f083ffcce4f08f9c7287d74521f1c7c41426afdd40f21fcd58f31c6"
    "cc1f638cc107397cd41f5f0849176b74cf386b8e4e176b7453426afd46083ffc"
    "4f176b74d2287d7446272f74c907397c4e426afd44426afdc9187f8cce4f08f9"
    "471f1c7cd40f21fcc88f31c6c51f638ccd07397cc81f3d84c107397cd60f21fc"
    "c5175f30d91f638c4f1f1c7cd507397cc54f08f956426afdc5186b75d24f08f9"
    "48272f74c5187f8c41426afdd2187f8cc407397ccf8f31c646087dfcd4137e8c"
    "48176b74c51f638cc78f31c6c1175f304d426afdc507397ccc287d7449176b74"
    "c7386b8e48426afd54176b7453083ffccf4f08f9d5386b8ed41f5f0849426afd"
    "d4187f8cd307397c411f1c7c45176b74cc8f31c6c51f638c43426afdd44f08f9"
    "52176b74cf386b8e4e1f1c7cc9187f8cc3175f3047087dfcc107397c4d1f1c7c"
    "c5187f8cd24f08f945083ffc4c426afdc54f08f9c1386b8e53272f74c54f08f9"
    "441f1c7cc2175f30591f1c7cd407397cc9287d74c74f08f945176b74d21f638c"
    "541f1c7c4f087dfcd9287d7453176b74c91f3d84ce8f31c6cf07397cce186b75"
    "451f1c7c54176b7448087dfccf8f31c6d507397cd3175f30411f1c7cce07397c"
    "441f1c7c4e176b74c98f31c64ea2f68ec507397c48426afdd5187f8cce4f08f9"
    "441f1c7cd20f21fcc5187f8cc4175f30ce8f31c6c98f31c6ce07397cc5386b8e"
    "54272f74d907397cc6175f30491f1c7cd6175f3045087dfcd8ad88dad8ad88da"
)


def contribution(position, value):
    index = position * 16 + value
    packed = int.from_bytes(DUMP[index * 4:index * 4 + 4], "little") >> 7
    selector = int(HASH[index], 16)
    offset = selector >> 2
    shift = (~selector) & 3
    buf = bytearray(8)
    for n in range(5):
        buf[offset + 4 - n] = (packed & 0x1F) << shift
        packed >>= 5
    return int.from_bytes(buf, "little")


F = [[contribution(p, c) for c in range(16 if p == 9 else 17)] for p in range(10)]


def normalize(password):
    return [ord(char) - ord("A") for char in password]


def decode(password):
    return "".join(
        chr(ord("A") + (value ^ key))
        for value, key in zip(normalize(password), FINAL_KEY)
    )


def pack(values):
    result = 0
    for value in values:
        result = result * 17 + value
    return result


def unpack(value):
    result = [0] * 5
    for i in range(4, -1, -1):
        value, result[i] = divmod(value, 17)
    return result


def solve():
    left = {}
    for values in product(range(17), repeat=5):
        key = F[0][values[0]] ^ F[1][values[1]] ^ F[2][values[2]] ^ F[3][values[3]] ^ F[4][values[4]]
        value = pack(values)
        old = left.get(key)
        if old is None:
            left[key] = value
        elif isinstance(old, list):
            old.append(value)
        else:
            left[key] = [old, value]

    for values in product(range(17), range(17), range(17), range(17), range(16)):
        right = F[5][values[0]] ^ F[6][values[1]] ^ F[7][values[2]] ^ F[8][values[3]] ^ F[9][values[4]]
        matches = left.get(TARGET ^ right)
        if matches is None:
            continue
        matches = matches if isinstance(matches, list) else [matches]
        for match in matches:
            candidate = unpack(match) + list(values)
            password = "".join(chr(ord("A") + value) for value in candidate)
            yield password, decode(password)


start = perf_counter()
solutions = list(solve())
print(f"MITM: {perf_counter() - start:.3f}s")
for password, decoded in solutions:
    print(f"{password} -> {decoded}")
print(f"Solutions: {len(solutions)}")