Research And Application Of Incomplete Diffusion Of AES-like Key Schedule

AES algorithm plays an indispensable role in cryptography and information security,so the security analysis of AES is of profound importance.This thesis mainly focuses on the incomplete diffusion of AES-128/192/256 key schedules and the restriction relationship of key bytes.According to the restriction relationship,we improve impossible differential attacks of 7-round AES-128 and 8-round Kiasu-BC and the meet-in-the-middle attack of 10-round AES-256.Because the Feistel-SP structure is similar to AES key schedule,we also study the incomplete diffusion of Feistel-SP structure with block shift.Our work mainly contains the following three aspects:1.In this thesis,the incomplete diffusion of AES-128/192/256 key schedules is proved for the first time and the restriction relationship of key bytes is given.Using the truncated differential analysis,we study the diffusion of the key schedule difference propagation when the master key difference has only one active byte.It is found that AES key schedule can't achieve complete diffusion when the active byte is 0 to 11 for arbitrary rounds,which proves the incomplete diffusion of AES key schedule.Using the same method,this thesis also analyzes the AES-192/256 key schedule and its inverse algorithm,and obtains similar results.In addition,with the help of the incomplete diffusion,restriction relationship between any two rounds of key bytes,which can be described by the definition of AES Subkey-byte Connectivity Table,can be obtained.2.Based on the AES subkey-byte connectivity table,an algorithm to recover master key faster than brute force is proposed.Using this algorithm,this thesis improves the key-sieving phase of the impossible differential attacks of 7-round AES-128 and 8-round Kiasu-BC,and the time complexity of this stage is greatly reduced.Thus,without increasing the overall attack complexity,more candidate keys can be left.As a result,the overall attack's complexities of time,memory and data are reduced.In addition,using the restriction relationship of key bytes,we reduce the memory complexity of the meet-in-the-middle attack of 10-round AES-256.3.The Feistel structure of round function with Substitution Permutation(SP)structure is called Feistel-SP structure.Because Feistel-SP structure is very similar to the structure of AES key schedule,this thesis studies the incomplete diffusion of Feistel-SP structure when the linear layer P in SP structure is block shift.Using the truncated differential analysis,it is proved that if the linear layer P in SP structure is block shift and the number of blocks is even,Feistel-SP structure can't achieve complete diffusion for arbitrary rounds.For Type-1,Type-2 and Type-3 generalized Feistel-SP structures with block shift,if the block number of linear layers and the grouping number of generalized Feistel structures are not prime,these three kinds of structures can't achieve complete diffusion.In addition,by the similar method,it is proved that if the transformation R in the AES key schedule is replaced by any byte block shift transformation,the AES key schedule can't achieve complete diffusion.