3-subset meet-in-the-middle attack

The 3-subset meet-in-the-middle (hereafter shortened MITM) attack is a variant of the generic meet-in-the-middle attack, which is used in cryptology for hash and block cipher cryptanalysis. The 3-subset variant opens up the possibility to apply MITM attacks on ciphers, where it is not trivial to divide the keybits into two independent key-spaces, as required by the MITM attack.

The 3-subset variant relaxes the restriction for the key-spaces to be independent, by moving the intersecting parts of the keyspaces into a subset, which contains the keybits common between the two key-spaces.

History

The original MITM attack was first suggested in an article by Diffie and Hellman in 1977, where they discussed the cryptanalytic properties of DES. ^[1] They argued that the keysize of DES was too small, and that reapplying DES multiple times with different keys could be a solution to the key-size; however, they advised against using double-DES and suggested triple-DES as a minimum, due to MITM attacks (Double-DES is very susceptible to a MITM attack, as DES could easily be split into two subciphers (the first and second DES encryption) with keys independent of one another, thus allowing for a basic MITM attack that reduces the computational complexity from ${\displaystyle 2^{112}(=2^{2\times 56})}$ to ${\displaystyle 2^{57}(=2\times 2^{56})}$.

Many variations has emerged, since Diffie and Hellman suggested MITM attacks. These variations either makes MITM attacks more effective, or allows them to be used in situations, where the basic variant cannot. The 3-subset variant was shown by Bogdanov and Rechberger in 2011, ^[2] and has shown its use in cryptanalysis of ciphers, such as the lightweight block-cipher family KTANTAN.

Procedure

As with general MITM attacks, the attack is split into two phases: A key-reducing phase and a key-verification phase. In the first phase, the domain of key-candidates is reduced, by applying the MITM attack. In the second phase, the found key-candidates are tested on another plain-/ciphertext pair to filter away the wrong key(s).

Key-reducing phase

In the key-reducing phase, the attacked cipher is split into two subciphers, ${\displaystyle f}$ and ${\displaystyle g}$, with each their independent keybits, as is normal with MITM attacks. Instead of having to conform to the limitation that the keybits of the two subciphers should be independent, the 3-subset attack allows for splitting the cipher into two subciphers, where some of the bits are allowed to be used in both of the subciphers.

This is done by splitting the key into three subsets instead, namely:

• ${\displaystyle A_{0}}$ = the keybits the two subciphers have in common.
• ${\displaystyle A_{1}}$ = the keybits distinct to the first subcipher, ${\displaystyle f.}$
• ${\displaystyle A_{2}}$ = the keybits distinct to the second subcipher, ${\displaystyle g}$

To now carry out the MITM attack, the 3 subsets are bruteforced individually, according to the procedure below:

1. For each guess of ${\displaystyle A_{0}}$:
   1. Calculate the intermediate value ${\displaystyle i}$ from the plaintext, for all key-bit combinations in ${\displaystyle A_{1}}$
   2. Calculate the intermediate value ${\displaystyle j}$, for all key-bit combinations in ${\displaystyle A_{2}}$
   3. Compare ${\displaystyle i}$ and ${\displaystyle j}$. When there is a match. Store it is a key-candidate.

Key-testing phase

Each key-candidate found in the key-reducing phase, is now tested with another plain-/ciphertext pair. This is done simply by seeing if the encryption of the plaintext, P, yields the known ciphertext, C. Usually only a few other pairs are needed here, which makes the 3-subset MITM attack, have a very little data complexity.

Example

The following example is based on the attack done by Rechberger and Bogdanov on the KTANTAN cipher-family. The naming-conventions used in their paper is also used for this example. The attack reduces the computational complexity of KTANTAN32 to ${\displaystyle 2^{75.170}}$, down from ${\displaystyle 2^{80}}$ if compared with a bruteforce attack. A computational complexity of ${\displaystyle 2^{75.170}}$ is of 2014 still not practical to break, and the attack is thus not computationally feasible as of now. The same goes for KTANTAN48 and KTANTAN64, which complexities can be seen at the end of the example.

The attack is possible, due to weaknesses exploited in KTANTAN's bit-wise key-schedule. It is applicable to both KTANTAN32, KTANTAN48 and KTANTAN64, since all the variations uses the same key-schedule. It is not applicable to the related KANTAN family of block-ciphers, due to the variations in the key-schedule between KTANTAN and KANTAN.

Overview of KTANTAN

KTANTAN is a lightweight block-cipher, meant for constrained platforms such as RFID tags, where a cryptographic primitive such as AES, would be either impossible (given the hardware) or too expensive to implement. It was invented by Canniere, Dunkelman and Knezevic in 2009. ^[3] It takes a block size of either 32, 48 or 64 bits, and encrypts it using an 80-bit key over 254 rounds. Each round utilizes two bits of the key (selected by the key schedule) as round key.

Attack

Preparation

In preparation to the attack, weaknesses in the key schedule of KTANTAN that allows the 3-subset MITM attack was identified. Since only two key-bits are used each round, the diffusion of the key per round is small - the safety lies in the number of rounds. Due to this structure of the key-schedule, it was possible to find a large number of consecutive rounds, which never utilized certain key-bits.

More precisely, the authors of the attack found that:

• Round 1 to 111 never uses the key-bits: ${\displaystyle k_{32},k_{39},k_{44},k_{61},k_{66},k_{75}}$
• Round 131 to 254 never uses the key-bits: ${\displaystyle k_{3},k_{20},k_{41},k_{47},k_{63},k_{74}}$

This characteristics of the key-schedule is used for staging the 3-subset MITM attack, as we now are able to split the cipher into two blocks with independent key-bits. The parameters for the attack are thus:

• ${\displaystyle A_{0}}$ = the keybits used by both blocks (which means the rest 68 bits not mentioned above)
• ${\displaystyle A_{1}}$ = the keybits used only by the first block (defined by round 1-111)
• ${\displaystyle A_{2}}$ = the keybits used only by the second block (defined by round 131-254)

Key-reducing phase

One may notice a problem with step 1.3 in the key-reducing phase. It is not possible to directly compare the values of ${\displaystyle i}$ and ${\displaystyle j}$, as ${\displaystyle i}$ is calculated at the end of round 111, and ${\displaystyle j}$ is calculated at the start of round 131. This is mitigated by another MITM technique called partial-matching. The authors found by calculating forwards from the intermediate value ${\displaystyle i}$, and backwards from the intermediate value ${\displaystyle j}$ that at round 127, 8 bits was still unchanged in both ${\displaystyle i}$ and ${\displaystyle j}$ with a probability one. They thus only compared part of the state, by comparing those 8 bits (It was 8 bits at round 127 for KTANTAN32. It was 10 bits at round 123 and 47 bits at round 131 for KTANTAN48 and KTANTAN64, respectively). Doing this yields more false positives, but nothing that increases the complexity of the attack noticeably.

Key-testing phase

KTANTAN32 requires on average 2 pairs now to find the key-candidate, due to the false positives from only matching on part of the state of the intermediate values. KTANTAN48 and KTANTAN64 on average still only requires one plain-/ciphertext pair to test and find the correct key-candidates.

Results

For:

• KTANTAN32, the computational complexity of the above attack is ${\displaystyle 2^{75.170}}$, compared to ${\displaystyle 2^{80}}$ with an exhaustive key search. The data complexity is 3 plain-/ciphertext pairs.
• KTANTAN48, the computational complexity is ${\displaystyle 2^{75.044}}$ and 2 plain-/ciphertext pairs are needed.
• KTANTAN64 it is ${\displaystyle 2^{75.584}}$ and 2 plain-/ciphertext pairs are needed.

The results are taken from the article by Rechberger and Bogdanov.

This is not the best attack on KTANTAN anymore. The best attack as of 2011 is contributed to Wei, Rechberger, Guo, Wu, Wang and Ling which improved upon the MITM attack on the KTANTAN family. ^[4] They arrived at a computational complexity of ${\displaystyle 2^{72.9}}$ with 4 chosen plain-/ciphertext pairs using indirect partial-matching and splice & cut MITM techniques.

Notes

1. Whitfield Diffie, Martin E. Hellman. "Exhaustive Cryptanalysis of the NBS Data Encryption Standard"
2. Andrey Bogdanov and Christian Rechberger. "A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN"
3. Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. "KATAN & KTANTAN — A Family of Small and Efficient Hardware-Oriented Block Ciphers"
4. Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang, and San Ling. "Improved Meet-in-the-Middle Cryptanalysis of KTANTAN"