In recent years, there has been considerable effort, and some successes, in developing cryptanalytic attacks on hash functions. To understand these, we need to look at the overall structure of a typical secure hash function, and is the structure of most hash functions in use today, including SHA and Whirlpool.
The hash function takes an input message and partitions it into L fixed-sized blocks of b bits each. If necessary, the final block is padded to b bits. The final block also includes the value of the total length of the input to the hash function. The inclusion of the length makes the job of the opponent more difficult. Either the opponent must find two messages of equal length that hash to the same value or two messages of differing lengths that, together with their length values, hash to the samevalue.
The hash algorithm involves repeated use of a compression function, f, that takes two inputs (an n-bit input from the previous step, called the chaining variable, and a b-bit block) and produces an n-bit output. At the start of hashing, the chaining variable has an initial value that is specified as part of the algorithm. The final value of the chaining variable is the hash value. Often, b > n; hence the term compression. The hash function can be summarized as follows:
where the input to the hash function is a message M consisting of the blocks Yo, Y1,..., YL-1. The structure can be used to produce a secure hash function to operate on a message of any length.
Message Authentication Codes
There is much more variety in the structure of MACs than in hash functions, so it is difficult to generalize about the cryptanalysis of MACs. Further, far less work has been done on developing such attacks.
SECURE HASH ALGORITHM
o SHA originally designed by NIST & NSA in 1993 was revised in 1995 as SHA-1
o US standard for use with DSA signature scheme
§ standard is FIPS 180-1 1995, also Internet RFC3174
§ nb. the algorithm is SHA, the standard is SHS
o based on design of MD4 with key differences
o produces 160-bit hash values
o recent 2005 results on security of SHA-1 have raised concerns on its use in future applications
1. SHA-512 Overview
2. SHA-512 Compression Function
heart of the algorithm
processing message in 1024-bit blocks
consists of 80 rounds
updating a 512-bit buffer
using a 64-bit value Wt derived from the current message block
and a round constant based on cube root of first 80 prime numbers
3. SHA-512 Round Function
4. SHA-512 –Individual Round Function