Some information about task DOUBLE A simple approach to solving this task is an exhaustive search over the combined key spaces: for each key k1 for each key k2 if E(E(p, k1), k2) = c2 exit with k1, k2 This requires in the worst case (20-bit keys) about 2^20 * 2^20 * 2 = 2^41 encryptions. Doing an optimistic 10^6 encryptions per second it would still take more than 25 days. (It can be halved by taking E(p, k1) outside the inner loop.) However, double encryption, as applied in this task, provides much less extra security than may at first seem to be the case. If the key length is n bits for single encryption, then an exhaustive search goes through all possible 2^n keys. Double encryption with two independent n-bit keys may seem to correspond to encryption with a single 2n-bit key. But the so-called "meet-in-the-middle attack" shows that it is actually no stronger than a single (n+1)-bit key. (For that reason, in practice, triple encryption is used for improving security.) The meet-in-the-middle attack works as follows. The given plain text p is encrypted with all possible 2^n keys and the results are stored (one way or another) in a table. Next, the given double-encrypted ciphertext c2 is _decrypted_ with all possible 2^n keys, and each result is checked against the table for a "collision". Such a collision reveals a "double key" used for encryption. The table is best set up as a hashed dictionary, to make both store and retrieve operations fast. The dictionary size needs to allow for more entries than keys to avoid too many hash collissions. Sizing the dictionary to twice the number of keys, and storing a 20-bit key and a 128-bit encrypted message together in 20 bytes, requires 2^21 * 20 = 40MB for the dictionary. This size can be reduced to 8 MB by not storing the message and recomputing it from the stored key. The ten cases have the following characteristics: Case s T k1 k2 Comments ---- - - -------- -------- -------- 1 1 P A... 7... This case is the same as the example 2 1 R C... 5... Can be solved manually with the tool 3 2 P A7... 6E... Can be solved by exhaustive search 4 2 C E1... 8A... Can be solved by exhaustive search 5 4 R A39E... B760... 6 4 R 893D... F66B... 7 4 R 9325... 0000... Extreme key at one end of key space 8 5 C CB053... 7F0F9... 9 5 P A7000... 6E000... Same answer as case 3 10 5 P 59D04... FFFFF... Extreme key at other end of key space where s = number of relevant hexadecimal key digits (task input) T = type of plaintext/ciphertext: P for structured plaintext (random-looking ciphertext) C for structured ciphertext (random-looking plaintext) R for random plaintext/ciphertext k1 = first key (task output) k2 = second key (task output) NOTES All answers can easily be verified by the interactive tool that was provided. All possible key digits 0..F appear in the keys, including duplicates. Structure in the plaintext or ciphertext cannot be exploited. Cases with s=4 can be solved by exhaustive search, but each takes more than one hour. Because these three cases have the same plaintext, they can be attacked together with exhaustive search, to solve three cases for the price of one case plus a little bit. Even a straightforward implementation of the meet-in-the-middle-attack works in seconds. Cases with s=5 require a good implementation of the meet-in-the-middle search. They cannot be solved by exhaustive search within the five hours of the competition. However, case 9 has the same solution as case 3! This can be recognized by inspecting the input files. The AES library allows for roughly 0.5e6 encryptions per second. Decryption is about a factor two slower than encryption.