Research On Key Technologies Of Chosen-prefix Collisions For MD5

Along with the breakthrough of MD4, MD5, SHA-1, and the proceding procedure of selecting SHA-3, the attack and design of Hash functions have becomed the popular theme in cryptography field in last several years. Because the differential attack proposed by Wang xiao yun, inspired by Dobbertin, can attack the MDx family Hash functions efficiently, it's attracted broad attention.However, Wang xiao yun donot give the details of her method and the collision pairs she finds are the random characters. The collision message pairs have no semantics. Based on the result of Wang xiao yun, Marc Stevens proposed the chosen-prefix collsions attack and applied it on creating false certifications.Marc Stevens cost 20 days and utilized 215 CELLs to find the needed collision pairs. In 2009, Marc Stevens improved his algorithms and saved much time, but increased the length of message pairs greatly.This thesis research thoroughly on the key technologies of chosen-prefix collision attack, and obtained the following resuly mainly:In the first part, we study the good difference. To control the disturbing and distribution of difference well, we give the four necessary characters that a good difference must have and the distribution model of every turn.The second part takes use of the good difference to design the heuristic algorithm of finding differential path. At first, the rotate shift differences are analyzed well. Its four result and corresponding probabilities are obtained. The probabilities are compared each other when the differential weight is equal to one especially. We also offer the relationship between the 27 difference output and input, the character of the carry distributions and the theory of tunnels.At last, the heuristic algorithm and its experience result is given.At the third part, we utilize the thought of Pollard's rho to design the serial searching algorithm to find (0,δb ,δc ,δc)-message pairs , the parallel searching algorithm to find (0,δb ,δc ,δc)-message pairs , and the parallel searching algorithm to find (0,δb ,δc ,δc)-message pairs that finds more than one (0,δb ,δc ,δc)-message pairs simultaneously. Their correctness and computational complexity is also analyzed. When designing the serial searching algorithm to find (0,δb ,δc ,δc)-message pairs , we use the thought of Floyd's cycle find to lower the needed ROM. The computational complexity is about . Supposed that there are M machines, the computational complexity is about when used the parallel searching algorithm to find (0,δb ,δc ,δc)-message pairs. However, if the machines run separately , the computational complexity is about. when used the parallel searching algorithm to find n (0,δb ,δc ,δc)-message pairs , the average computational complexity is about . is the searching space range. The computing result shows that the more (0,δb ,δc ,δc)-message pairs are searched, the more stable the complex is and the less the average complexity is.Finally, we complement these three algorithms on CPU, GPU, and FPGA.The experiment results are obtained.