Three-Subset Meet-in-the-Middle Attack on Reduced XTEA

This paper presents an improved single-key attack on a block-cipher XTEA by using the three-subset meet-in-the-middle (MitM) attack. Firstly, a technique on a generic block-cipher is discussed. It points out that the previous work applying the splice-and-cut technique to the three-subset MitM attack contains incomplete arguments, and thus it requires a very large data complexity, which is close to the code book. This paper gives a corrected procedure to keep the data complexity small. Secondly, the three-subset MitM attack is applied for reduced-round XTEA, which is a 64-bit block-cipher with 64-round Feistel network and a 128-bit key. 25 rounds are attacked with 9 known plaintexts and 2120.40 XTEA computations, while the previous best single-key attack only reaches 23 rounds. In the chosen-plaintext model, the attack is extended to 28 rounds with 237 chosen-plaintexts and 2120.38 computations.