Cryptography: Hashing and Message Digests

    

•A hash function maps a variable-length message into a fixed-length hash value, or message digest.

•All cryptographic hash functions involve the iterative use of a compression function.

•

§A hash algorithm is a one way function that converts a data string into a numeric string output of fixed length. The output string is generally much smaller than the original data. Therefore it is also called message digest or message compression algorithm.

§Hash algorithms are designed to be collision-resistant, meaning that there is a very low probability that the same string would be created for different data.

§Two of the most common hash algorithms are the MD5 (Message-Digest algorithm 5) and the SHA-1 (Secure Hash Algorithm). MD5 Message Digest checksums are commonly used to validate data integrity when digital files are transferred or stored.

•A hash function H accepts a variable-length block of data M as input and produces a fixed-size hash value h = H(M).

•In general terms, the principal object of a hash function is data integrity.

•A change to any bit or bits in M results, with high probability, in a change to the hash code. 


•The kind of hash function needed for security applications is referred to as a cryptographic hash function.

•A cryptographic hash function is an algorithm for which it is computationally infeasible (because no attack is significantly more efficient than brute force) to find either

–a data object that maps to a pre-specified hash result (the one-way property) or

–two data objects that map to the same hash result (the collision-free property).

 
 
Cryptographically Secure Hashing 

•For a hash value h = H(x), we say that x is the preimage of h.

–That is, x is a data block whose hash function, using the function H, is h.

•Because H is a many-to-one mapping, for any given hash value h, there will in general be multiple preimages.

•A collision occurs if we have x ≠ y and H(x) = H(y). Because we are using hash functions for data integrity, collisions are clearly undesirable.

  One-way Hash Function 

Many functions can take an arbitrary-length input and return an output of fixed length, but one-way hash functions have additional characteristics that make them one-way:

1.It is relatively easy to compute, but significantly harder to reverse. That is, given M it is easy to compute H(M), but given H(M) it is hard to compute x.

2.Moreover it is also very hard to find another message M’ such that H(M’)=H(M). In other words it is collision resistant.

In this context, "hard" is defined as something like: It would take millions of years to compute M from H(M), even if all the computers in the world were assigned to the problem.

§

§When applying digital signature to a document, we no longer need to encrypt the entire document with a sender's private key, it can be extremely slow. It is sufficient to encrypt the document's hash value instead. Therefor hash algorithm is used to digest the message before applying DSA.

§Although a one-way hash function is used mostly for generating digital signatures, it can have other practical applications as well, such as message integrity, password verification, generation of pseudorandom bits, file identification and message authentication code (MAC.)

§The Microsoft cryptographic providers support these hash algorithms: MD4, MD5, SHA-1 and SHA256.

§

Collision Resistance 

§A slight change in an input string should cause the hash value of the function to change drastically. Even if 1 bit is flipped in the input string, at least half of the bits in the hash value will flip as a result. This is called an avalanche effect.

§Since it is computationally infeasible to produce a document that would hash to a given value or find two documents with the same hash value.

§As there is almost no chance to have the same hash value of two different messages, so it is called collision free or collision resistant.

§A document's hash can serve as a cryptographic equivalent of the document. This makes a one-way hash function a central notion in public-key cryptography.

Application of Cryptographic Hash Functions 

•Message Integrity Verification: Determining whether 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).

•Password Verification: Passwords are usually not stored in cleartext, 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. This is sometimes referred to as one-way encryption.

•Digital Signatures: while generating digital signatures, the message digest is created and it is encrypted with the private key so that the signing process becomes faster.