Security Analysis And Implementation Of Keccak In SHA-3 Standard

As an important branch of modern cryptography,hash functions have been widely used in Message Integrity Check,Digital Signatures,Authentication Protocol,and so on.Thus,the security of hash functions would directly affect the security of encryption authentication as well as communication network,and become the precondition of cryptosystems and cryptographic protocols.The security properties of Hash functions are mainly reflected by the following three aspects: Collision resistance,Preimage resistance and Second-preimage resistance.In recent years,as a large number of effective cryptanalysis results of Hash functions such as MDx and SHA have been made,in 2007 the American National Institute of Standards and Technology(NIST)launched a competition for a new Hash function standard which is called SHA-3.After three rounds of selection,Keccak finally won and became the SHA-3 standard in October 2012.Keccak adopts the new sponge construction which is different from traditional Merkle-Damgrd iterative structure,it has the proved good safety as well as performance.The attack of round-reduced Keccak is one of the research hotspots at present.And the known practical collision attacks for the Keccak are limited to a small number of rounds.This thesis is divided into two parts: the first part introduces the concept,structure and basic attack methods of cryptography Hash function.Meanwhile,the difference cryptanalysis for the iterative block cipher is also introduced in detail.Then,on the basis of the study on the permutation properties of SHA-3 iterative functions,this thesis presents the security analysis of the algorithm from two aspects,one is the statistical properties of the Keccak and the other is symmetry of the round functions in the sponge structure adopted by the Keccak.The analysis and test results show that the Keccak has excellent avalanche performance and ability to resist statistical attacks.And because of the introduction of step mapping?,the algorithm has good performance against internal differential attacks while the number of rounds is high.Finally the software design of Keccak is carried out,and the analysis of its software implementation performance on the general PC platform is given.The results show that the Keccak has similar performance with SHA-2 and can be used in various applications efficiently.In the second part,on the basis of the research on round-reduced Keccak by Naya-Plasencia et al,this thesis presents an improved attack method on round-reduced Keccak,which starts from the known 2 round as well as 3 round low Hamming weight differential characteristics with high probability,first extends it backward by one round and maintain its high probability,then extend it with another round using Target Difference Algorithm.Next combines differential and algebraic cryptanalysis,and finally realized collision attacks on 4 round Keccak as well as near collision attacks on 5 round Keccak using a single PC.This is a practical collision attack of the round-reduced Keccak.But while trying to attack Keccak the ones have larger number of rounds,due to the bit diffusion of differential paths increases dramatically and it's probability decreases fast,it's hard to find collisions or near collisions.These results show that the core security of Keccak has not been threatened in the condition of higher number of round and is very reliable at present.