Paper 2016/579

Automatic Search of Meet-in-the-Middle and Impossible Differential Attacks

Patrick Derbez and Pierre-Alain Fouque

Abstract

Tracking bits through block ciphers and optimizing attacks at hand is one of the tedious task symmetric cryptanalysts have to deal with. It would be nice if a program will automatically handle them at least for well-known attack techniques, so that cryptanalysts will only focus on finding new attacks. However, current automatic tools cannot be used as is, either because they are tailored for specific ciphers or because they only recover a specific part of the attacks and cryptographers are still needed to finalize the analysis. In this paper we describe a generic algorithm exhausting the best meet-in-the-middle and impossible differential attacks on a very large class of block ciphers from byte to bit-oriented, SPN, Feistel and Lai-Massey block ciphers. Contrary to previous tools that target to find the best differential / linear paths in the cipher and leave the cryptanalysts to find the attack using these paths, we automatically find the best attacks by considering the cipher and the key schedule algorithms. The building blocks of our algorithm led to two algorithms designed to find the best simple meet-in-the-middle attacks and the best impossible truncated differential attacks respectively. We recover and improve many attacks on AES, mCRYPTON, SIMON, IDEA, KTANTAN, PRINCE and ZORRO. We show that this tool can be used by designers to improve their analysis.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CRYPTO 2016
Keywords
automatic searchmeet-in-the-middleimpossible truncated differentialcryptanalysis
Contact author(s)
patrick derbez @ irisa fr
pierre-alain fouque @ irisa fr
History
2016-06-06: received
Short URL
https://ia.cr/2016/579
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/579,
      author = {Patrick Derbez and Pierre-Alain Fouque},
      title = {Automatic Search of Meet-in-the-Middle and Impossible Differential Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2016/579},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/579}},
      url = {https://eprint.iacr.org/2016/579}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.