On Yoyo Attack And Its Applications

In the cryptanalysis of block ciphers,yoyo is a crucial attack which can be used for both structure analysis and key recovery.The most prominent feature of yoyo attack is its lower data and computational complexity compared with other attacks,so it has attracted a lot of scholars'interests in recent years.So far,yoyo attack has been applied to analyze the security of cipher structure and been employed as key recovery attack in specific ciphers.The main research results of this paper are shown as follows:We proposed an improved yoyo attack for the second type of generalized Feistel structure(Type-II):In this paper,the 7-round Type-II structure with secret internal function is recovered.By analyzing the probability and the number of fixed points in the yoyo cycle,we determined the mathematical expectation of the cycle length and proved that the average number of equations provided by each correct yoyo cycle is 2ⁿ,which is difficult to provide full rank equations.Therefore,the use of a single yoyo cycle can only provide partial data for the recovery of internal functions.In this paper,the judging short cycles technique is proposed,which performs multiple yoyo cycles on the correct lookup table to jointly recover internal functions.Our experiments showed that when the internal function is 7 bits,the original yoyo takes 9 times longer to recover the Type-II internal function than the yoyo attack combined with this technology.With the increase of the internal function size,the efficiency will be more obvious.We proposed the optimal practical key recovery attack for the reduced-round 3D and Saturnin with practical complexity by yoyo attack:The method in this paper is the first practical key recovery attack for 7-round 3D and 5-round Saturnin.For 7-round 3D,we first used super S-boxes and mega S-boxes to build a 6-round yoyo distinguisher,which only needs 1 chosen plaintext pair and adaptively chosen ciphertext pair by 1 encryption and decryption.Based on this distinguisher,this paper proposed a key recovery attack combined with the meet-in-the-middle technique.The attack needs 2¹⁶ plaintext pairs and adaptively chosen ciphertext pairs,2⁹ storage space and 2^18.9 encryptions and decryptions.For 5-round Saturnin,we found a 4-round distinguisher and a 5-round key recovery attack in a similar way.The data complexity is 2³¹plaintext pairs and ciphertext pairs and 2³⁷ super-round encryptions.We proposed a new technique called the Key Sets Reduction:In the design report of Saturnin,comparing the description of the cipher with its pseudocode,we found that its program implementation part(Algorithm 1 in reference[42])omitted the S-layer of even rounds,which made the cipher only contain a single S-layer in a super round.We call it the single S-layer version.A Key Sets Reduction technology is proposed to reduce the complexities of yoyo attack for such weakened version of Saturnin.By selecting the returned plaintext pairs with more zero-difference nibbles and using multi-data filtering,this technique can reduce the candidate key sets step by step.Directly applying the key sets reduction technique on recovering the key in 5-super-round Saturnin needs 2^39.1 plaintext pairs and ciphertext pairs and 2⁴⁶-super-round encryptions.Combined with the meet-in-the-middle technique,the data complexity can be reduced to 2^28.17 plaintext pairs and ciphertext pairs,and the time complexity is consistent with the attack for the double-S-layer version.This also demonstrates the necessity of designing one super round containing double S-layers.It is worth noting that the Key Set Reduction technique does not use the properties of super S-boxes and is not limited to yoyo attacks.Therefore,it can effectively reduce the complexities when analyzing ciphers with strong diffusion.