Paper 2017/162

Analysis of AES, SKINNY, and Others with Constraint Programming

Siwei Sun, David Gerault, Pascal Lafourcade, Qianqian Yang, Yosuke Todo, Kexin Qiao, and Lei Hu

Abstract

Search for different types of distinguishers are common tasks in symmetric-key cryptanalysis. In this work, we employ the constraint programming (CP) technique to tackle such problems. First, we show that a simple application of the CP approach proposed by Gerault \Dengdeng~leads to the solution of the open problem of determining the exact lower bound of the number of active S-boxes for 6-round AES-128 in the related-key model. Subsequently, we show that the same approach can be applied in searching for integral distinguishers, impossible differentials, zero-correlation linear approximations, in both the single-key and related-(twea)key model. We implement the method using the open source constraint solver Choco and apply it to the block ciphers PRESENT, SKINNY, and HIGHT (ARX construction). As a result, we find 16 related-tweakey impossible differentials for 12-round SKINNY-64-128 based on which we construct an 18-round attack on SKINNY-64-128 (one target version for the crypto competition \url{https://sites.google.com/site/skinnycipher} announced at ASK 2016). Moreover, we show that in some cases, when equipped with proper strategies (ordering heuristic, restart and dynamic branching strategy), the CP approach can be very efficient. Therefore, we suggest that the constraint programming technique should become a convenient tool at hand of the symmetric-key cryptanalysts

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in FSE 2017
Keywords
Differential CryptanalysisIntegral CryptanalysisConstraint ProgrammingAESSKINNY
Contact author(s)
sunsiwei @ iie ac cn
History
2017-02-24: revised
2017-02-23: received
See all versions
Short URL
https://ia.cr/2017/162
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/162,
      author = {Siwei Sun and David Gerault and Pascal Lafourcade and Qianqian Yang and Yosuke Todo and Kexin Qiao and Lei Hu},
      title = {Analysis of AES, SKINNY, and Others with Constraint Programming},
      howpublished = {Cryptology ePrint Archive, Paper 2017/162},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/162}},
      url = {https://eprint.iacr.org/2017/162}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.