Yoyo trick on type‐II generalised Feistel networks

Abstract

Abstract This work presents a structural attack against the type‐II generalised Feistel network (GFN) with secret internal functions. First, equivalent structures of the 7‐round type‐II GFN are provided, which helps reduce the first guess of the secret round functions. Then, two yoyo game distinguishers are simultaneously employed for these structures to reduce the data complexity by half. Based on these two distinguishers, it is found that the original yoyo game algorithm, proposed to attack the 5‐round Feistel structure, is not suitable for these structures, owing to the characteristics of the yoyo game cycle. To solve this problem, the partial look‐up table recycling technique is presented, which can utilise collision cycles with insufficient information. This technique performs better as the width of each branch ‘n’ grows. For yoyo game attacks, this study systematically investigates its cycle characteristics to determine the reason for the short collision cycle. For 7‐round type‐II GFNs, this work presents the first decomposition thus far, which can be executed within a time complexity of O(n24n + 3) and a data complexity of O(23n + 2). We believe this work enriches the yoyo game attack and the application of type‐II GFNs.

Keywords

• cryptography
• computational complexity