A lock with two keys
A cipher clerk decided that the sixteen-bit key of a home-made cipher was too short and began encrypting every message twice: first with key k1, then with key k2. “Now there are thirty-two unknown bits,” the clerk reasoned, “four billion options.” You have intercepted two blocks of ciphertext and know the plaintext that corresponds to them: the messages begin with the first words of War and Peace in English translation. Find both keys.
The cipher works like this. A block is a 32-bit number X, its halves are L = X div 216 and R = X mod 216. A key k is a number from 0 to 65,535. Eight rounds, i = 0, 1, …, 7: the pair (L, R) is replaced by (R, L xor F(R, k, i)), where
$$F(r, k, i) = \operatorname{rotl}_5\big(((r \oplus k) \cdot 40503 + i) \bmod 2^{16}\big),$$
and rotl5 is a cyclic shift of a sixteen-bit number by 5 bits to the left: (v · 32 + v div 211) mod 216. The ciphertext of a block is 216 · L + R after eight rounds. The double lock: C = Ek2(Ek1(P)).
It is guaranteed that exactly one pair of keys (k1, k2) takes both known blocks to both intercepted ones.
Input
Two lines, each with a plaintext block P and its ciphertext C, numbers from 0 to 232 − 1.
Output
Two numbers: k1 and k2.
Examples
Example 1
1466264684 4203669661 740315250 3310296384
11134 6751
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Searching all pairs of keys is 232 double encryptions, more than four billion. Even in Go that is tens of seconds. But what can be computed knowing only k1? And only k2?
2Hint 2
Every round is invertible: from (R, L xor F(R)) the pair (L, R) is recovered, because F depends only on R, which is known. So the cipher can be not only applied but also wound back.
3Hint 3
A pair of keys has been found whose middles coincided on the first block. Is it the answer?
4The idea
The middle M = Ek1(P) = Dk2(C) is computed from both sides. Encrypt the first known block with all 216 keys k1 and store the middles in a dictionary “middle → keys”. Decrypt the first intercepted block with all keys k2 and look each middle up in the dictionary. A match is a candidate answer. The work is 2 · 216 cipher calls instead of 232. This is meeting in the middle.
5Walkthrough
It remains to weed out chance coincidences. There are 232 pairs of keys and also 232 possible middle values, so besides the real pair, on average one more meets in the middle by pure chance. Check each candidate with the second known block: a false pair passes with probability 2−32, and the statement guarantees that only one pair does.
Decrypting a round: if after the round the pair is (L′, R′), then before it L = R′ xor F(L′, k, i) and R = L′. The rounds are wound back in reverse order, from the seventh to the zeroth.
The dictionary can be replaced by a sorted list of pairs (middle, key) and binary search; that is how the article’s listing does it. 216 entries of memory are needed.
5+Solution
6Complexity
2 · 216 encryptions and decryptions of 8 rounds each and 216 dictionary lookups: a fraction of a second even in Python. Searching pairs would take 215 times longer.
7Common mistakes
- The first match is the answer. The most common mistake. In all tests except the example and one of the tests with extreme keys, a chance candidate meets in the middle first, and the answer without a check by the second block is wrong.
- Searching pairs of keys. Correct, but 4 billion double encryptions do not fit in the time limit.
- The reverse order of rounds. In decryption the round number i enters F, so you have to go from 7 to 0; going from 0 to 7 gives not the inverse function but some other one. Chance coincidences in the middle remain, but none passes the check with the second block, and there is no answer at all.
- Overflow in the product. In Go the product of two sixteen-bit numbers in the type
uint16is taken modulo 216 by itself, as needed; in Python the result has to be cut explicitly with the mask& 0xFFFF.