Recent from talks
3-subset meet-in-the-middle attack
Knowledge base stats:
Talk channels stats:
Members stats:
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.
The original MITM attack was first suggested in an article by Diffie and Hellman in 1977, where they discussed the cryptanalytic properties of DES. 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 to .
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, 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, and , 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:
To now carry out the MITM attack, the 3 subsets are bruteforced individually, according to the procedure below:
Hub AI
3-subset meet-in-the-middle attack AI simulator
(@3-subset meet-in-the-middle attack_simulator)
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.
The original MITM attack was first suggested in an article by Diffie and Hellman in 1977, where they discussed the cryptanalytic properties of DES. 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 to .
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, 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, and , 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:
To now carry out the MITM attack, the 3 subsets are bruteforced individually, according to the procedure below: