International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

New Yoyo Tricks with AES-based Permutations

Authors:
Dhiman Saha , Department of Electrical Engineering & Computer Science, Indian Institute of Technology, Bhilai 492015
Mostafizar Rahman , Cryptology and Security Research Unit (CSRU), R. C. Bose Centre for Cryptology and Security, Indian Statistical Institute, Kolkata 700108
Goutam Paul , Cryptology and Security Research Unit (CSRU), R. C. Bose Centre for Cryptology and bSecurity, Indian Statistical Institute, Kolkata 700108
Download:
DOI: 10.13154/tosc.v2018.i4.102-127
URL: https://tosc.iacr.org/index.php/ToSC/article/view/7363
Search ePrint
Search Google
Presentation: Slides
Abstract: In Asiacrypt 2017, Rønjom et al. reported some interesting generic properties of SPNs, leading to what they call the Yoyo trick, and applied it to find the most efficient distinguishers on AES. In this work, we explore the Yoyo idea in distinguishing public permutations for the first time. We introduce the notion of nested zero difference pattern which extends the Yoyo idea and helps to compose it using improbable and impossible differential strategies to penetrate higher number of rounds. We devise a novel inside-out application of Yoyo which enables us to start the Yoyo game from an internal round. As an application, we investigate the AES-based public permutation AESQ used inside the authenticated cipher PAEQ. We achieve the first deterministic distinguisher of AESQ up to 8 rounds and the first 9-round distinguisher of AESQ that start from the first round with a practical complexity of around 226. We manage to augment Yoyo with improbable and impossible differentials leading to distinguishers on 9, 10, 12 rounds with complexities of about 22, 228, 2126 respectively. Further, with impossible differentials and a bi-directional Yoyo strategy, we obtain a 16-round impossible differential distinguisher with a complexity of 2126. Our results outperform all previous records on AESQ by a substantial margin. As another application, we apply the proposed strategies on AES in the known-key setting leading to one of the best 8-round known-key distinguisher with a complexity of 230. Finally, this work amplifies the scope of the Yoyo technique as a generic cryptanalysis tool.
Video from TOSC 2018
BibTeX
@article{tosc-2018-29248,
  title={New Yoyo Tricks with AES-based Permutations},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2018, Issue 4},
  pages={102-127},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/7363},
  doi={10.13154/tosc.v2018.i4.102-127},
  author={Dhiman Saha and Mostafizar Rahman and Goutam Paul},
  year=2018
}