Paper 2013/324

Sieve-in-the-Middle: Improved MITM Attacks (Full Version)

Anne Canteaut, María Naya-Plasencia, and Bastien Vayssiere


This paper presents a new generic technique, named sieve-in-the-middle, which improves meet-in-the-middle attacks 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. Combining this technique with short bicliques allows to freely add one or two more rounds with the same time complexity. Moreover, when the key size of the cipher is larger than its block size, we show how to build the bicliques by an improved technique which does not require any additional data (on the contrary to previous biclique attacks). These techniques apply to PRESENT, DES, PRINCE and AES, improving the previously known results on these four ciphers. In particular, our attack on PRINCE applies to 8 rounds (out of 12), instead of 6 in the previous cryptanalyses. Some results are also given for theoretically estimating the sieving probability provided by some subsets of the input and output bits of a given sbox.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Full version of the extended abstract published in the proceedings of CRYPTO 2013
Meet-in-the-middleblock ciphersbicliquessboxmatching algorithms
Contact author(s)
Anne Canteaut @ inria fr
2014-09-09: revised
2013-06-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Anne Canteaut and María Naya-Plasencia and Bastien Vayssiere},
      title = {Sieve-in-the-Middle: Improved MITM Attacks (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2013/324},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.