International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On the Usage of Deterministic (Related-Key) Truncated Differentials and Multidimensional Linear Approximations for SPN Ciphers

Authors:
Ling Sun , Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, China
David Gerault , Nanyang Technological University, Singapore, Singapore
Wei Wang , Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, China
Meiqin Wang , Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, China
Download:
DOI: 10.13154/tosc.v2020.i3.262-287
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8702
Search ePrint
Search Google
Abstract: Among the few works realising the search of truncated differentials (TD) and multidimensional linear approximations (MDLA) holding for sure, the optimality of the distinguisher should be confirmed via an exhaustive search over all possible input differences/masks, which cannot be afforded when the internal state of the primitive has a considerable number of words. The incomplete search is also a long-term problem in the search of optimal impossible differential (ID) and zerocorrelation linear approximation (ZCLA) since all available automatic tools operate under fixed input and output differences/masks, and testing all possible combinations of differences/masks is impracticable for now. In this paper, we start by introducing an automatic approach based on the constraint satisfaction problem for the exploration of deterministic TDs and MDLAs. Since we transform the exhaustive search into an inherent feature of the searching model, the issue of incomplete search is settled. This tool is applied to search for related-key (RK) TDs of AES-192, and a new related-key differential-linear (DL) distinguisher is identified with a TD with certainty. Due to the novel property of the distinguisher, the previous RK DL attack on AES-192 is improved. Also, the new distinguisher is explained from the viewpoint of differentiallinear connectivity table (DLCT) and thus can be regarded as the first application of DLCT in the related-key attack scenario. As the second application of the tool, we propose a method to construct (RK) IDs and ZCLAs automatically. Benefiting from the control of the nonzero fixed differential pattern and the inherent feature of exhaustive search, the new searching scheme can discover longer distinguishers and hence possesses some superiorities over the previous methods. This technique is implemented with several primitives, and the provable security bounds of SKINNY and Midori64 against impossible differential distinguishing attack are generalised.
Video from TOSC 2020
BibTeX
@article{tosc-2020-30570,
  title={On the Usage of Deterministic (Related-Key) Truncated Differentials and Multidimensional Linear Approximations for SPN Ciphers},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2020, Issue 3},
  pages={262-287},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8702},
  doi={10.13154/tosc.v2020.i3.262-287},
  author={Ling Sun and David Gerault and Wei Wang and Meiqin Wang},
  year=2020
}