| Hash algorithm is one of the basic algorithms of modern cryptography,and it is of great significance to study hash algorithm.The modular differential cryptanalysis proposed by Chinese cryptographer Professor Wang Xiaoyun et al.has cracked hash algorithms such as MD5 and SHA-1,in which the construction of differential paths is a key part of the method.However,the current tools for automatically constructing differential paths of MD(Merkle–Damg?rd)structure hash algorithm are independent of each other,and require a lot of modification before constructing differential paths of other hash algorithm.At the same time,existing tools based on guess-and-determine use differential diffusion techniques to accelerate the construction of differential paths of SHA-256,but the details are not publicly disclosed.In order to resist collision attacks,academic circles have proposed collision detection methods.Existing MD5 collision detection method utilize unavoidable sufficient conditions to reduce detection time,but only utilize sufficient conditions in the last round of the differential path.In response to the above issues,this thesis investigates methods of the automatic construction of differential paths and the improvement of MD5 collision detection.The main work is as follows:(1)A unified automatic construction of differential paths construction method based on meet-in-the-middle is proposed.Compression function analysis,recursion and advance-search techniques are added to the existing method to eliminate the differences between MD5,SHA-1and SHA-256.The proposed method constructs MD5,SHA-1 and 23-step SHA-256 differential paths while only changing the parameter configuration.However,there are still limitations in this method,and it is currently impossible to construct differential paths for hash algorithms such as SM3.(2)A method for automatically constructing differential paths of SHA-256 based on automata is proposed.This thesis optimizes SHA-256 encoding and introduces automata in the Maple SAT solver to diffuse differential information and enable the solver to learn the information after diffusion.Compared with the original Maple SAT,the modified Maple SAT reduces the time complexity of SHA-256’s 21-step collision,23-step semi-free start collision,24-step collision and 27-step collision search by 34%,43%,8.7% and 26.6%,respectively.(3)A MD5 collision detection method combined with the second round of sufficient conditions is proposed.Firstly,according to the nature of the Boolean function in the second round of MD5,it is found that the sufficient conditions in the second round of the differential path are also suitable as unavoidable conditions,which are called additional sufficient conditions.Then,according to the additional sufficient conditions,3 sets of differential paths are subdivided,and7 types of differential paths are identified.Finally,the inevitability of the additional sufficient condition is verified using Hash Clash.Compared with the existing collision detection methods,the proposed method reduces the time complexity of MD5 collision detection by 8.18%. |
