Wednesday, December 5, 2012

What is Hashfunction?

A hash function H is a transformation that takes an input m and returns a fixed-size string, which is called the hash value h (that is, h = H(m)). Hash functions with just this property have a variety of general computational uses, but when employed in cryptography, the hash functions are usually chosen to have some additional properties.
The basic requirements for a cryptographic hash function are as follows.
  • The input can be of any length.
  • The output has a fixed length.
  • H(x) is relatively easy to compute for any given x.
  • H(x) is one-way.
  • H(x) is collision-free. 

 
A one-way hash function maps an arbitrary-length input message M to a fixed-length output hash H(M) such that the following properties hold:
  • One-way: Given a hash H(M), it is difficult to find the message M.
     
  • Second preimage resistant: Given a message M1, it is difficult to find another message M2 such that H(M1) = H(M2).
     
  • Collision resistant: It is difficult to find two messages M1 and M2 such that H(M1) = H(M2). 
Hash Algorithm         Output Hash Length (bits)
Message Digest (MD4) -- insecure         128
MD5         128
Secure Hash Algorithm 1 (SHA-1)         160
SHA-256         256
SHA-384         384
SHA-512         512

In detail
"A hash function H is said to be one-way if it is hard to invert, where ``hard to invert'' means that given a hash value h, it is computationally infeasible to find some input x such that H(x) = h. If, given a message x, it is computationally infeasible to find a message y not equal to x such that H(x) = H(y), then H is said to be a weakly collision-free hash function. A strongly collision-free hash function H is one for which it is computationally infeasible to find any two messages x and y such that H(x) = H(y)."

 Perhaps the main role of a cryptographic hash function is in the provision of message integrity checks and digital signatures. Since hash functions are generally faster than encryption or digital signature algorithms, it is typical to compute the digital signature or integrity check to some document by applying cryptographic processing to the document's hash value, which is small compared to the document itself. Additionally, a digest can be made public without revealing the contents of the document from which it is derived. This is important in digital timestamping (see Question 7.11) where, using hash functions, one can get a document timestamped without revealing its contents to the timestamping service.

for more info
http://www.rsa.com/rsalabs/node.asp?id=2176
http://www.cs.rit.edu/~ark/lectures/onewayhash/onewayhash.shtml

3 comments:

  1. I was familiar with the basic meaning of has function but this detail helped me to learn about this concept in detail. After reading the complete article I am curious to know about the applications where hash functions are used.
    digital signatures

    ReplyDelete
    Replies
    1. Natalia, The hash function is used in number of ways like Digital Signature, Message authentication code etc. In java when we are implementing Hashmap, we use the Hashcode. this link may be useful
      http://pathak-manish.blogspot.in/2012/12/java-hashcode.html.

      Delete