Paper 2018/813

Programming the Demirci-Sel{ç}uk Meet-in-the-Middle Attack with Constraints

Danping Shi, Siwei Sun, Patrick Derbez, Yosuke Todo, Bing Sun, and Lei Hu

Abstract

Cryptanalysis with SAT/SMT, MILP and CP has increased in popularity among symmetric-key cryptanalysts and designers due to its high degree of automation. So far, this approach covers differential, linear, impossible differential, zero-correlation, and integral cryptanalysis. However, the Demirci-Selcuk meet-in-the-middle (DS-MITM) attack is one of the most sophisticated techniques that has not been automated with this approach. By an in-depth study of Derbez and Fouque's work on DS-MITM analysis with dedicated search algorithms, we identify the crux of the problem and present a method for automatic DS-MITM attack based on general constraint programming, which allows the cryptanalysts to state the problem at a high level without having to say how it should be solved. Our method is not only able to enumerate distinguishers but can also partly automate the key-recovery process. This approach makes the DS-MITM cryptanalysis more straightforward and easier to follow, since the resolution of the problem is delegated to off-the-shelf constraint solvers and therefore decoupled from its formulation. We apply the method to SKINNY, TWINE, and LBlock, and we get the currently known best DS-MITM attacks on these ciphers. Moreover, to demonstrate the usefulness of our tool for the block cipher designers, we exhaustively evaluate the security of 8!=40320 versions of LBlock instantiated with different words permutations in the F functions. It turns out that the permutation used in the original LBlock is one of the 64 permutations showing the strongest resistance against the DS-MITM attack. The whole process is accomplished on a PC in less than 2 hours. The same process is applied to TWINE, and similar results are obtained.

Note: This is an extended version of the paper "Programming the Demirci-Selcuk Meet-in-the-Middle Attack with Constraints" including supplementary materials.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in ASIACRYPT 2018
Keywords
Demirci-Sel{ç}uk meet-in-the-middle attackAutomated cryptanalysisConstraint programmingMILP
Contact author(s)
sunsiwei @ iie ac cn
History
2018-09-11: revised
2018-09-06: received
See all versions
Short URL
https://ia.cr/2018/813
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/813,
      author = {Danping Shi and Siwei Sun and Patrick Derbez and Yosuke Todo and Bing Sun and Lei Hu},
      title = {Programming the Demirci-Sel{ç}uk Meet-in-the-Middle Attack with Constraints},
      howpublished = {Cryptology ePrint Archive, Paper 2018/813},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/813}},
      url = {https://eprint.iacr.org/2018/813}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.