Boomeyong: Embedding Yoyo within Boomerang and its Applications to Key Recovery Attacks on AES and Pholkos 📺
This work investigates a generic way of combining two very effective and well-studied cryptanalytic tools, proposed almost 18 years apart, namely the boomerang attack introduced by Wagner in FSE 1999 and the yoyo attack by Ronjom et al. in Asiacrypt 2017. In doing so, the s-box switch and ladder switch techniques are leveraged to embed a yoyo trail inside a boomerang trail. As an immediate application, a 6-round key recovery attack on AES-128 is mounted with time complexity of 278. A 10-round key recovery attack on recently introduced AES-based tweakable block cipher Pholkos is also furnished to demonstrate the applicability of the new technique on AES-like constructions. The results on AES are experimentally verified by applying and implementing them on a small scale variant of AES. We provide arguments that draw a relation between the proposed strategy with the retracing boomerang attack devised in Eurocrypt 2020. To the best of our knowledge, this is the first attempt to merge the yoyo and boomerang techniques to analyze SPN ciphers and warrants further attention as it has the potential of becoming an important cryptanalysis tool.
New Yoyo Tricks with AES-based Permutations 📺
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.