Problem E
Key "Hash"

A cryptographic hash function is an algorithm that maps data of arbitrary size to data of a fixed size. Hashes are one-way functions which are computationally infeasible to invert or reverse. In a strong hash, the only way to find the original message that produced a given hash would be a brute-force attack. Sometimes attackers keep a hash of the encryption key along with the data as a method of associating keys stored elsewhere to the correct files.

Key Hash

A “key_hash” value can be found within the TLV data structure. This hash is somehow associated to the rest of the data in that structure. Pseudocode for this hash is listed in the malware report. It is safe to assume that this is how the developers look up one of the keys for decrypting the files. The algorithm is described as follows:

This is obviously something of the malware developers’ own creation, and definitely not a cryptographically secure hash. It also appears to only work on data that is $16$-bytes long, which according to the report is because the keys that it hashes are always $16$ bytes long.

In the malware report a large list of random $16$-byte objects is found. These actually appear to be randomly generated this time, which makes you wonder just how many developers worked on this ransomware. You also notice a list of "key_hash" outputs that have been found. You connect the dots and realize some of those random objects might be used as keys in the final decryption layer.

Implement the algorithm above to take random $16$-byte inputs and produce a key_hash.

Once you have a working algorithm, test all the random keys from the list above to see which ones match the list of key_hash outputs you have. Make sure you keep the key - key_hash relationships stored somewhere as it will make future work much easier!

Input

Multiple random $16$-byte objects encoded in HEX separated by newlines.

Output

The RAW output of the key_hash algorithm for each input separated by newlines.

8ea859d168c64f1f754e7c7032f1f85d
c88d4022dcdc435635f5fa4a0d33414a
cdc41d2126ed8f737d987a390a8d75bd
1a169ae91a343fb891995d37a9f9046e
46ea9d8afe42595e2bed2a9102eb20d8
8799479a631ecf7375080608bc7b5f28

67110992:2326286721:2566916433:34471970:4032197778:3991754888
1216692258:2148007936:54525970:948605472:3858231874:3475190104
2172919073:1279262720:17318272:637570065:1028156149:2643705843
402784488:34904577:604258884:2550152216:2426395798:2145289581
1189124362:656512:1210580995:2453803032:2720344763:1473927746
93848466:2181121032:319308164:34890:1902743136:1926498450