Cryptographic hash function
From Academic Kids

In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. A hash function takes a long string (or message) of any length as input and produces a fixed length string as output, sometimes termed a message digest or a digital fingerprint.
In various standards and applications, the two mostcommonly used hash functions are MD5 and SHA1; however, security flaws have been identified in both algorithms.
Contents 
Overview
Broadly speaking, a cryptographic hash function should behave as much as possible like a random function while still being deterministic and efficiently computable.
A cryptographic hash function is considered insecure if either of the following is computationally feasible:
 finding a (previously unseen) message that matches a given digest
 finding "collisions", wherein two different messages have the same message digest.
An attacker who can do either of these things might, for example, use them to substitute an unauthorized message for an authorized one.
It should not even be feasible to find two messages whose digests are substantially similar; nor should an attacker learn anything useful about a message given only its digest besides the digest itself.
Related algorithms
Checksums and Cyclic redundancy checks (CRCs) are quite distinct from cryptographic hash functions, and are used for different applications. If used for security, they are vulnerable to attack; for example, a CRC was used for message integrity in the WEP encryption standard, but an attack was readily discovered which exploited the linearity of the checksum specified.
A message authentication code or MAC takes a message and a secret key and generates a "MAC tag", such that it is difficult for an attacker to generate a valid (message, tag) pair that doesn't match one they've already seen; they are used to prevent attackers forging messages, among other uses. Though it is sometimes referred to as a "keyed hash function", a MAC serves a very different purpose and has very different security properties than a cryptographic hash function; for example, it is not considered a flaw if it is easy for someone who knows the MAC key to generate two messages that have the same MAC. Hash functions can be used to create MAC functions; see for example HMAC.
Cryptographic properties
There is no formal definition which captures all of the properties considered desirable for a cryptographic hash function. These properties below are generally considered prerequisites:
 Preimage resistant (See one way for a related but slightly different property): given h it should be hard to find m such that h = hash(m).
 Second preimage resistant: given an input m_{1}, it should be hard to find another input, m_{2} (not equal to m_{1}) such that hash(m_{1}) = hash(m_{2}).
 Collisionresistant: it should be hard to find two different messages m_{1} and m_{2} such that hash(m_{1}) = hash(m_{2}). Because of the birthday paradox this means the hash function must have a larger image than is required for preimageresistance.
A hash function meeting these criteria may still have undesirable properties. For instance, most popular hash functions are vulnerable to lengthextension attacks: given h(m) and len(m) but not m, by choosing a suitable m' an attacker can calculate h(m  m'), where  denotes concatenation. This property can be used to break naive authentication schemes based on hash functions. The HMAC construction works around these problems.
An ideal hash function would be maximally "boring": it would have no interesting properties such as length extension, and the only interesting way it would differ from a random function would be in that it was deterministic and efficiently computable. This criterion is of course deeply resistant to formal expression; the closest thing to formal expression is the random oracle model, which is an idealization no real hash function can satisfy.
Applications of hash functions
A typical use of a cryptographic hash would be as follows: Alice poses to Bob a tough math problem and claims she has solved it. Bob would like to try it himself, but would yet like to be sure that Alice is not bluffing. Therefore, Alice writes down her solution, appends a random nonce, computes its hash and tells Bob the hash value (whilst keeping the solution secret). This way, when Bob comes up with the solution himself a few days later, Alice can verify his solution but still be able to prove that she had the solution earlier.
In actual practice, Alice and Bob will often be computer programs, and the secret would be something less easily spoofed than a claimed puzzle solution. The above application is called a commitment scheme. Another important application of secure hashes is verification of message integrity. Determination of whether or not any changes have been made to a message (or a file), for example, can be accomplished by comparing message digests calculated before, and after, transmission (or any other event) (see Tripwire, a system using this property as a defense against malware and malfeasance). A message digest can also serve as a means of reliably identifying a file. A related application is password verification. Passwords are usually not stored in clear text, for obvious reasons, but instead in digest form. To authenticate a user, the password presented by the user is hashed and compared with the stored hash.
For both security and performance reasons, most digital signature algorithms specify that only the digest of the message be "signed", not the entire message. Hash functions can also be used in the generation of pseudorandom bits.
SHA1, MD5, and RIPEMD160 are among the most commonlyused message digest algorithms as of 2005. In August 2004, researchers found weaknesses in a number of hash functions, including MD5, SHA0 and RIPEMD. This has called into question the longterm security of later algorithms which are derived from these hash functions — in particular, SHA1 (a strengthened version of SHA0), RIPEMD128, and RIPEMD160 (both strengthened versions of RIPEMD). Neither SHA0 nor RIPEMD are widely used since they were replaced by their strengthened versions. In February 2005, an attack on SHA1 was reported, finding collisions in about 2^{69} hashing operations, rather than the 2^{80} expected for a 160bit hash function.
Hashes are used to identify files on peertopeer filesharing networks. For example, in a ed2k link the hash is combined with the filename and the file size, providing sufficient information for locating file sources, downloading the file and verifying its contents.
MerkleDamgård hash functions
A hash function must be able to process an arbitrarylength message into a fixedlength output. This can be achieved by breaking the input up into a series of equalsize blocks, and operating on them in sequence using a compression function. The last block processed will also contain the length of the entire message; this is crucial to the security of this construction, which is known as the MerkleDamgård structure. Most widelyused hash functions, including SHA1 and MD5, take this form.
Merkledamgard.png
MerkleDamgård
In the diagram, the compression function is denoted by f, and transforms a fixedlength input to an output of the same size. The algorithm starts with an initial value, the initialization vector (IV). For each message block, the compression (or compacting) function f takes the result so far, combines it with the block, and produces an intermediate result. Bits representing the length of the entire message are appended to the message and padded suitably as part of the last block. The value after the last block is taken to be the hash value for the entire message.
The popularity of this construction is due to the fact, proven by Merkle and Damgård, that if the compression function f is collisionresistant, then so is the hash function constructed using it. Unfortunately, this construction also has several undesirable properties:
 lengthextension attacks are always possible
 secondpreimage attacks against long messages are always much more efficient than brute force
 multicollisions (lots of messages with the same hash) can be found with only a little more work than collisions
List of cryptographic hash functions
Some of the following algorithms are known to be insecure; consult the relevant articles for more information on the status of the algorithm.
 HAVAL
 MD2
 MD4
 MD5
 NHash
 RIPEMD160
 The SHA hash functions are a series of functions developed by the NSA: SHA, also known as SHA0, SHA1 and four flavours of a function known as SHA2.
 Snefru
 Tiger
 Whirlpool
See also
 Avalanche effect
 MD5CRK
 Message authentication code
 Keyedhash message authentication code
 CRYPTREC and NESSIE (projects which recommend hash functions)
External links
 The Hash function lounge (http://planeta.terra.com.br/informatica/paulobarreto/hflounge.html) — a list of hash functions and known attacks
 Helger Lipmaa's links on hash functions (http://www.cs.ut.ee/~helger/crypto/link/hash/)
 Diagrams explaining cryptographic hash functions (http://www.cs.rit.edu/~ark/lectures/onewayhash/onewayhash.shtml)
 An Illustrated Guide to Cryptographic Hashes (http://www.unixwiz.net/techtips/iguidecryptohashes.html) by Steve Friedl
 Cryptanalysis of MD5 and SHA: Time for a New Standard (http://schneier.com/essay074.html) by Bruce Schneier
 Hash collision Q&A (http://www.cryptography.com/cnews/hash.html)
 Attacking hash functions by poisoned messages (construction of multiple sensible Postscript messages with the same hash function) (http://www.cits.rub.de/MD5Collisions/)