Analysis of AES, SKINNY, and Others with Constraint Programming

Authors

  • Siwei Sun State Key Laboratory of Information Security (SKLOIS), Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, Beijing, China;School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
  • David Gerault The Laboratory of Informatics, Modelling and Optimization of the Systems (LIMOS), University Clermon Auvergne, Clermont-Ferrand, France
  • Pascal Lafourcade The Laboratory of Informatics, Modelling and Optimization of the Systems (LIMOS), University Clermon Auvergne, Clermont-Ferrand, France
  • Qianqian Yang State Key Laboratory of Information Security (SKLOIS), Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China;Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, Beijing, China
  • Yosuke Todo NTT Secure Platform Laboratories, Tokyo, Japan
  • Kexin Qiao State Key Laboratory of Information Security (SKLOIS), Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, Beijing, China
  • Lei Hu State Key Laboratory of Information Security (SKLOIS), Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, Beijing, China

DOI:

https://doi.org/10.13154/tosc.v2017.i1.281-306

Keywords:

Differential Cryptanalysis, Integral Cryptanalysis, Constraint Programming, AES, SKINNY

Abstract

Search for different types of distinguishers are common tasks in symmetrickey 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 et al. 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 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.

Downloads

Published

2017-03-08

How to Cite

Sun, S., Gerault, D., Lafourcade, P., Yang, Q., Todo, Y., Qiao, K., & Hu, L. (2017). Analysis of AES, SKINNY, and Others with Constraint Programming. IACR Transactions on Symmetric Cryptology, 2017(1), 281–306. https://doi.org/10.13154/tosc.v2017.i1.281-306

Issue

Section

Articles