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.
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
2112(=22)
257(=2 x 256)
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.
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).
In the key-reducing phase, the attacked cipher is split into two subciphers,
f
g
This is done by splitting the key into three subsets instead, namely:
A0
A1
f.
A2
g
To now carry out the MITM attack, the 3 subsets are bruteforced individually, according to the procedure below:
A0
i
A1
j
A2
i
j
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.
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
275.170
280
275.170
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.
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.
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:
k32,k39,k44,k61,k66,k75
k3,k20,k41,k47,k63,k74
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:
A0
A1
A2
One may notice a problem with step 1.3 in the key-reducing phase. It is not possible to directly compare the values of
i
j
i
j
i
j
i
j
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.
For:
275.170
280
275.044
275.584
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
272.9