@article{Saha_Rahman_Paul_2018, title={New Yoyo Tricks with AES-based Permutations}, volume={2018}, url={https://tosc.iacr.org/index.php/ToSC/article/view/7363}, DOI={10.13154/tosc.v2018.i4.102-127}, abstractNote={<p>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 <strong>AES</strong>. 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 <strong>AES</strong>-based public permutation <strong>AESQ</strong> used inside the authenticated cipher <strong>PAEQ</strong>. We achieve the first deterministic distinguisher of <strong>AESQ</strong> up to 8 rounds and the first 9-round distinguisher of <strong>AESQ</strong> that start from the first round with a practical complexity of around 2<sup>26</sup>. We manage to augment Yoyo with improbable and impossible differentials leading to distinguishers on 9, 10, 12 rounds with complexities of about 2<sup>2</sup>, 2<sup>28</sup>, 2<sup>126</sup> respectively. Further, with impossible differentials and a bi-directional Yoyo strategy, we obtain a 16-round impossible differential distinguisher with a complexity of 2<sup>126</sup>. Our results outperform all previous records on <strong>AESQ</strong> by a substantial margin. As another application, we apply the proposed strategies on <strong>AES</strong> in the <em>known-key</em> setting leading to one of the best 8-round known-key distinguisher with a complexity of 2<sup>30</sup>. Finally, this work amplifies the scope of the Yoyo technique as a generic cryptanalysis tool.</p>}, number={4}, journal={IACR Transactions on Symmetric Cryptology}, author={Saha, Dhiman and Rahman, Mostafizar and Paul, Goutam}, year={2018}, month={Dec.}, pages={102–127} }