Cryptographic Hash Functions

What it is?

A hash function is any function that can be used to map digital data of arbitrary size to digital data of fixed size, with slight differences in input data producing very big differences in output data.

             A cryptographic hash function is a hash function which is considered practically impossible to invert, that is, to recreate the input data from its hash value alone.

Application of Cryptographic Hash Functions:-

• Message Authentication

 This mechanism/service is used to verify the integrity of a message. This can be accomplished by comparing message digests calculated before, and after, transmission.
(The Hash Function value is referred to as message digest in Message Authentication)

We use Digital Signature verify the authenticity of the received Message Digest.

Various Ways to achieve that:

1.  Confidentiality+ Authentication (done in PGP)
2. Authentication only(done in PGP)
3. Assuming both parties possess a secret key "S". Compute the Hash value of (M||S) and append it to M. (The receiver knows S so he can generate the hash. The attacker would not be able to generate the hash.)
4. Confidentiality can be added to method (3) by encryption  (message||hash code)

• Digital Signatures

 Now if the Hashed value is sent as it is(without encryption), the adversary may tamper both the message and the hashed value. He may replace the original hashed value with the hash value of the new replaced message. For this reason, verifying the authenticity of a hashed digest is equally important.
      A digital signature is a mathematical scheme for demonstrating the authenticity of a digital message or document.

Ways to achieve it:-

1. Encrypt Hash using RSA with Sender's Private key
2. Encrypt Message With Symmetric Key Encryption. Calculate Hash of (Ciphertext||Secret Key) and encrypt it using RSA with Sender's Private Key.

• Other Applications 

1. One-Way Passwords
2. Intrusion Detection/ Virus Detection
3. Construct a Pseudo Random Function (PRF)

Two Simple Hash Functions

1. One of the simplest Hash Function is bit-by-bit XOR of every block.
   C[i]=b[i][1]+b[i][2]+....b[i][n]
   
   This works well with random data, but with predictably formatted data, this function is less effective.
   
2. To improve the previous method , we can perform a 1-bit circular shift,or rotation, on the hash value after after each block is processed.  

• Initially set hash value to 0
• Process each successive block of data as :-

                      -Rotate current hash value  to the left by 1-bit

-XOR the block into hash value.

Though it is a good way to check data integrity , but it is useless for security.

Requirement and Security

Generally, the basic security of cryptographic hash functions can be seen from three different angles:

• Pre-image resistance: given a hash h it should be hard to find any message m such that h = hash(m). This concept is related to that of one way function. Functions that lack this property are vulnerable to pre-image attacks.
• Second pre-image resistance: given an input m1, it should be hard to find another input, m2 (not equal to m1) such that hash(m1) = hash(m2).  Functions that lack this property are vulnerable to second pre-image attacks.
• Collision resistance: it should be hard to find two different messages m1 and m2 such that hash(m1) = hash(m2). Such a pair is called a (cryptographic) hash collision. It requires a hash value at least twice as long as what is required for pre-image resistance, otherwise collisions may be found by a birthday attack.

What Things we require from a good Cryptographic Hash Function?

1. Variable Input Size
2. Fixed Output Size
3. Good Efficiency
4. Preimage Resistant (One-Way Property)
5. Second Preimage Resistant (Weak Collision Resistant)
6. Collision Resistant(Strong Collision Resistant)
7. Pseudo-Randomness

Various Possible Attacks:-

1) Brute Force Attacks:

• Preimage and Second Preimage Attacks
• Collision Resistant Attacks

2) Cryptanalysis:

Some Examples:-

• Based on CIPHER-BLOCK CHAINING

 Divide a message into fixed-size blocks and use a symmetric encryption system such as DES to compute the hash code as

H0 = initial value
Hi = E(Mi, Hi-1)

G = HN

This is similar to the CBC technique, but in this case, there is no secret key.

As with any hash code, this scheme is subject to the birthday attack, and if the encryption algorithm
is DES and only a 64-bit hash code is produced, then the system is vulnerable.

Furthermore, another version of the birthday attack can be used even if the
opponent has access to only one message and its valid signature and cannot
obtain multiple signings. Here is the scenario: We assume that the opponent
intercepts a message with a signature in the form of an encrypted hash code and
that the unencrypted hash code is bits long.
1. Use the algorithm defined at the beginning of this subsection to calculate the
unencrypted hash code .
2. Construct any desired message in the form .
3. Compute for .
4. Generate random blocks; for each block , compute . Generate
an additional random blocks; for each block , compute D( , ), where D is
the decryption function corresponding to E.
5. Based on the birthday paradox, with high probability there will be an and
such that .
6. Form the message , , . This message has the hash code
and therefore can be used with the intercepted encrypted signature.
This form of attack is known as a meet-in-the-middle-attack. A number
of researchers have proposed refinements intended to strengthen the basic
block chaining approach. For example, Davies and Price [DAVI89] describe the
variation:
Another variation, proposed in [MEYE88], is
However, both of these schemes have been shown to be vulnerable to a variety
of attacks [MIYA90]. More generally, it can be shown that some form of birthday
attack will succeed against any hash scheme involving the use of cipher block chaining
without a secret key, provided that either the resulting hash code is small enough
(e.g., 64 bits or less) or that a larger hash code can be decomposed into independent
subcodes [JUEN87].
Thus, attention has been directed at finding other approaches to hashing.
Many of these have also been shown to have weaknesses [MITC92].

• SHA (Secure Hash Algorithm)