Known-Key Distinguishers For Feistel-SP Structure

At ASIACRYPT 2013,Isobe and Shibutani divided Feistel into three types,called Feistel-1/2/3.In this paper,we study the Feistel-3,which uses the round function of the SPN,that is,the round function contains an XOR of a subkey,the nonlinear S-box layer and the linear diffusion layer.We represent Feistel-3 as Feistel-SP in this paper.It usually uses 128-bit or 64-bit blocks,and 8-bit or 4-bit S-boxes.There are many cryptanalysis results for Feistel-SP under the open-key model recently.At FSE 2011,Sasaki and Yasuda found 11-round known key distin-guisher for the Feistel-SP.Then,Sasaki et al.improved the cryptanalysis result in 2012,but the round number of the known key distinguisher for Feistel-SP was still 11.The time complexity of 11-round known-key distinguishing attacks was 219 and memory complexity was also 219 for Feistel-SP with 128-bit blocks and 8-bit S-boxes.At FSE 2017,Dong et al.proposed a 12-round chosen-key distin-guisher.The time complexity of 12-round chosen-key distinguishing attacks was 240 and memory complexity was 235 for Feistel-SP on the case of 128-bit blocks and 8-bit S-boxes.The results of the Feistel-SP above are all based on rebound attack,and the essence of the construction of the distinguishers is the idea of differential crypt-analysis.In 2014,Dong et al.constructed known-key high-order differential dis-tinguishers for Feistel-SP by using the idea of algebraic degree,which improved the number of rounds of Feistel-SP on the case of 4-bit S-boxes,the rounds reached 15 and 17 respectively for Feistel-SP with 64-bit and 128-bit blocks.The idea of zero correlation linear cryptanalysis and integral cryptanalysis are also effective techniques to construct distinguishers for block cipher.The definition of known-key distinguisher was prpposed by Gilbert again at ASIACRYPT 2014,and 10 rounds of known-key integral distinguisher for AES was carried out under this definition.Inspired by this,we use the idea of integral cryptanalysis to improve the known key distinguishing attacks of Feistel-SP.Firstly,we present a 9-round zero-correlation distinguisher under the known key scenario by using a five-round zero-correlation linear hull and a four-round zero-correlation linear hull of the Feistel-SP.Then we make use of the transforma-tion relationship between zero correlation distinguishers and integral distinguish-ers given by Sun et al.at CRYPTO 2015 and transform 9-round zero correlation distinguisher into 9-round integral distinguisher.Based on the idea of known key model proposed by Gilbert,we extend both one round before and behind of 9-round integral distinguisher with known key for Feistel-SP,and the 11-round known key distinguisher is constructed.For Feistel-SP with 128-bit blocks and 8-bit S-boxes,the time complexity of 11-round known-key distinguisher is 2120 and memory complexity is 220.7.Furthermore,we extend both one round before and behind of the 11-round known key distinguisher to construct a 13-round known key distinguisher for the Feistel-SP.The time complexity of known key distin-guisher is 2120 and the memory complexity is 275.58 for Feistel-SP with 128-bit blocks and 8-bit S-boxes.Our results are the best one for Feistel-SP with the 8-bit S-boxes under known-key model so far.