Hash Functions
Introduction
A hash is simply an encoded value H(m) representing the integrity of another value m. A hashing algorithm takes a string (of bits) as input and converts it into a usually smaller string (of bits) called the hash value. Since the input space is greater than the output space, there exists the possibility that 2 or more elements of the input space maps to 1 element of the output space. The idea is to minimize these collisions by having a uniform distribution for each partition. In the other words, the number of collisions or corresponding m's for each hash value H(m) should be equal. One unique characteristic of hashing is one-way computation. The security relies on the premise that the original or input string (of bits) m can't be feasibly obtained via the hash value or output string H(m). The following are the properties of secure hash functions:
Properties
1. One-way or Pre-image Resistance: For a given hash code h it is impossible to find m where H(m) = h.
2. Weak Collision or Second Pre-image Resistance: given m1 it is computationally infeasible to find m2 such that H(m1) = H(m2).
3. Strong Collision Resistance: It is infeasible to find a pair (m1, m2) such that H(m1) = H(m2).
Authentication
Message Authentication Code (MAC) is one form of keyed hashing. Alice and Bob who wish to communicate with each other share a secret key. Alice, wanting to send a message to Bob, computes the MAC value of a plaintext message. Alice then sends that plaintext message along with the appended MAC value to Bob. Bob then computes a MAC with the same shared secret key in conjunction with the received message and compares that MAC with Alice's MAC. If they match then the message isn't altered and Bob can be assured that it is from Alice. Keep in mind, MAC is not a digital signature process because Alice and Bob share the same secret key. MAC's make it very difficult for an opponent to crack. As an application, a hashing function can provide a fingerprint for a file. Let's say that you want to keep track of file changes throughout a period of time. You can, for instance, compute the hash value of the file in the morning before the work day starts and then recompute it right after the work day ended and then compare the results.
Hash Functions
There are 3 prevalent hash functions MD5, SHA-1 and RIPEMD-160:
|
|
MD5 |
SHA-1 |
RIPEMD-160 |
|
Digest Length |
128 bits |
160 bits |
160 bits |
|
Basic Processing Unit |
512 bits |
512 bits |
512 bits |
|
Number of Steps |
4 x 16 rounds |
4 x 20 rounds |
5 x 2 x 16 rounds |
|
Max. Message Size |
° |
264 - 1 bits |
264 - 1 bits |
|
Primitive Logical Func. |
4 |
4 |
5 |
|
Additive Constants Used |
64 |
4 |
9 |
|
Endianness |
Little |
Big |
Little |
*Chart based off [7b]
Links
http://www.alw.nih.gov/Security/prog-auth.html
http://www.usenix.org/publications/library/proceedings/lisa98/invited_talks/avolio_html/
http://www.linktionary.com/h/hash_function.html
http://www.signatur.rtr.at/en/providers/properties/hash-certificate.html