Problem D
Key Exhaust

According to the malware report, a “random” 16 byte key is generated and used together with $S(k)$ to produce a stream of key bytes, which is then XORed onto the data. Under the encrypted data always lies the serialized data structure that begins with the header “tlv_format_6”. When you see this header value, you will know that you have correctly decrypted the data. The malware report has an appendix that lists 20 of these keys that have been found “in the wild” in other instances of this ransomware attack worldwide:

You immediately notice that these keys are not actually random; the developers used a severely broken random number generation scheme. Also they appear to have created 8-bytes of data and are using the HEX representation as the key bytes. Analyze the structure and build a “cracker” that will exhaust over the entire non-random keyspace and crack the next layer of encrypted data. The ransomware only “randomly” generates $4096$ keys. Let’s get cracking!

Think about a set of rules that hold true for all the given keys. This should lead you to a general exhaust of the key space to create all possible keys. If you are testing more than $4096$ keys, there is some structure that you are not accounting for. Think about how the sets of unknown bytes relate to each other. Assume that this is a uniformly random sampling of the keys created by the malware.

In the samples below you have $12$ bytes that starts an encrypted stream and you know that the plaintext is “tlv_format_6”. Remember the stream cipher creates key bytes of whatever size you need and is XORed with the plaintext to create the ciphertext. You can just apply the stream again to the ciphertext to recover the plaintext.

Input

A new-line separated list of data, the first line contains just the number of encrypted data streams that follow. On each new line, a 12 HEX byte data stream encrypted with the modified RC4 algorithm you have figured out in the previous steps.

Output

Output a new-line separated list of keys (1 per line) that decrypt the given data in the same order that the data was read from the input list.

a86eebf364de89279daf598d
a12d49067ec3559da37ab880
6efe04ed370c2b42d22daf29
9523c2e6cac0b6fe0e6ce36c

043efbc1154feab0
0d8df2721e9ee161
0449fbb6155aeaa5
0feff01010f0ef0f