The Sieve-in-the-Middle Attack Of Block Cipher FeW, Piccolo And LBlock

In this paper, we review the method Sieve-in-the-Middle proposed by Anne Canteaut et al in CRYPTO 2013 [1] which improves Meet-in-the-Middle attack in the sense that it provides an attack on a higher number of rounds. Instead of selecting the key candidates by searching for a collision in an intermediate state which can be computed forwards and backwards, we here look for the existence of valid transitions through some middle sbox.Given the same target structures of algorithm and sieving probability, this paper compares the attack rounds of the Sieve-in-the-Middle attack and Meet-in-the-Middle attack. As illustrations, we give the Sieve-in-the-Middle attacks and the Meet-in-the-Middle attacks on block cipher FeW, Piccolo, and Lblock. For FeW-80, we could attack 8 rounds utilizing the Sieve-in-the-Middle method when 7 rounds could be attacked utilizing the Meet-in-the-Middle method. Both the required time complexity and data complexity of the two attack methods are completely same. For Piccolo-128, we only consider the algorithm structure starting from the 3rd round,15 rounds could be attacked by utilizing the Sieve-in-the-Middle method when 12 rounds could be attacked utilizing the Meet-in-the-Middle method. Both the required time complexity and data complexity of the two attack methods are still same. Isobe and Shibutani proposed the Meet-in-the-Middle attack on 21 rounds of Piccolo-128, the whole plaintexts space was required in the attack process which is impossible in most cases. If the adversary could only acquire one known plaintext, disgarding the Biclique and Splice and Cut method adopted in [20], Isobe and Shibutani only could attack 14 rounds of Piccolo-128. For LBlock, we sustain the same given filtering probability. When one known plaintext is obtained,16 rounds of LBlock could be attacked using the Sieve-in-the-Middle method when we can attack 15 rounds of LBlock utilizing the Meet-in-the-Middle method.