Paper 2016/689

New Automatic Search Tool for Impossible Differentials and Zero-Correlation Linear Approximations

Tingting Cui, Shiyao Chen, Keting Jia, Kai Fu, and Meiqin Wang

Abstract

Impossible differential and zero-correlation linear cryptanalysis are two of the most powerful cryptanalysis methods in the field of symmetric key cryptography. There are several automatic tools to search such trails for ciphers with S-boxes. These tools focus on the properties of linear layers, and idealize the underlying S-boxes, i.e., assume any input and output difference pairs are possible. In reality, such S-box never exists, and the possible output differences with any fixed input difference can be at most half of the entire space. Hence, some of the possible differential trails under the ideal world become impossible in reality, possibly resulting in impossible differential trails for more rounds. In this paper, we firstly take the differential and linear properties of non-linear components such as S-box into consideration and propose a new automatic tool to search impossible differential trails for ciphers with S-box. We then generalize the tool to modulo addition, and apply it to ARX ciphers. To demonstrate the usefulness of the tool, we apply it to HIGHT, SHACAL-2, LEA, LBlock. As a result, it improves the best existing results of each cipher.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Impossible differential cryptanalysiszero-correlation linear cryptanalysisMILPautomatic tool
Contact author(s)
mqwang @ sdu edu cn
History
2018-11-21: last of 4 revisions
2016-07-12: received
See all versions
Short URL
https://ia.cr/2016/689
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/689,
      author = {Tingting Cui and Shiyao Chen and Keting Jia and Kai Fu and Meiqin Wang},
      title = {New Automatic Search Tool for Impossible Differentials and Zero-Correlation Linear Approximations},
      howpublished = {Cryptology ePrint Archive, Paper 2016/689},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/689}},
      url = {https://eprint.iacr.org/2016/689}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.