Cryptanalysis Of The Reduced SHA-2 Algorithm

Hash Function, is also called hash codes, which takes in messages of arbitrary length and output result of fixed length, the output is the so-called hash codes. Hash function is a kind of compression function which means the input space is much larger than the output space. Different inputs can have the same output, while it is not possible to decide the input from output.Hash function is of great importance to digital fingerprints. It can be used to ensure data integrity and to perform personal authentication. There are several advantages to using hash function for digital schemes: improving the speed of digital schemes; ignoring the message corresponding to signature; separating the signature and encryption.In addition to the two basic properties of compression and ease of computation, cryptographic hash functions need to satisfy the following three security properties:(1) Preimage resistance: for any pre-specified output y, it is computationally infeasible to find a x such that h(x)=y.(2) Second preimage resistance: for any input x, it is computationally infeasible to find another input x1, such that h(x)=h(x1).(3) Collision resistance: it is computationally infeasible to find any two distinct inputs x and x1, such that h(x)=h(x1).Differential cryptanalysis introduced by Biham and Shamir in 1990, is one of the most powerful chosen plaintext attacks in cryptology. The attack is a method which analyzes the effect of differences in plaintext pairs on the differences of resultant ciphertext pairs. These differences can be used to assign probabilities to the possible keys and to locate the most probable key. It has already been use to the cryptanalysis of MD4[6,7], MD5[9,10,11],SHA-0[16,187,18] and SHA-1[19,20].SHA-2 has caused much attention of the research community. Mendel etc.[24] find the first 18-step SHA-256 collision and 19-step SHA-256 near collision using linear differential path. Nikolic and Biryukov[26] were the first to use non-linear differential path to cryptanalyse SHA-2, they reported 20-step and 21-step SHA-256 collision. Indesteege etc.[31] extended their method and found 23-step and 24-step SHA-256 collisions. Sanadhya and Sarkar[28,29,30,32,33] generalized Nikolic and Biryukov's local collision and gave deterministic method to find 22-step SHA-256 and SHA-512 collisions. They also gave collisions for 23-step and 24-step SHA-256 and 23-step SHA-512, which have improved time complexities compared to Indesteege's result. Sanadhya and Sarkar were the first to find 24-step SHA-512 collisions.In this thesis, we use a third local collision to find collisions for 23-step reduced SHA-256 and SHA-512, we gave theoretical method and analyzed their time complexities. Our cryptanalysis improves current conclusions of SHA-2, but does not cause any threat to the SHA-2 family.