Cryptography 16

Hash Functions

What is hash function ?!

Hash function maps a variable length message into a fixed length hash value.

Cryptographic hash function is an algorithm for which no attack is more efficient than brute force to find

1- Get the message from the hash value.

2- Find two messages with the same hash value.

Building a simple hash function:

The simplest form of hash function is bit-by-bit XOR but it is not secure at all

h = B1

**⊕**B2**⊕**B3 .....
But this form has a low effectiveness, we can improve this algorithm by perform one-bit circular shift

by the following steps:

1- Set the hash value to zero.

2- Rotate the hash value one bit to the left.

3- XOR the hash value with the data block.

This algorithm added more randomizing to hash value than bit-by-bit XOR.

Requirements for building a hash function:

For a hash function h= H(x)

h is the hash value , H is a hash function or many-to-one mapping algorithm

x is a data block (preimage)

A collision occurs if x != y and H(x) = H(y) , and it is not good when using a hash function in data integrity or in message authentication.

For any given hash value h, there will in general be multiple preimages and this is a measure of the number of potential collision for a given hash value.

Suppose the length of the hash code in n ,and the hash function takes a data block as input of length b such that b>n.

Then the total number of possible messages is \(2^{b}\) and the total number of possible hash values is \(2^{n}\) then the hash value will have close to \(2^{\frac{b}{n}}\) preimages and this is a security risk.

So the requirement for building a hash function

1- H can be applied to a block of data of any size.

2- H produces a fixed length of output h.

3- H(x) is relatively easy to compute for any given x.

4- Preimage Resistance (one-way property): For any given hash value h, it is computationally infeasible to find y such that H(y) = h .

5- Second Preimage Resistance (weak collision resistance) : For any given block x , it is computationally infeasible to find H(y) = H(x) x != y.

6- Collision Resistance (strong collision resistance): It is computationally infeasible to find any pair (x,y) such that H(x)=H(y) .

7- Pseudorandomness : The output of H function meets standard tests for pseudorandomness.

To build a strong hash function, the hash function must satisfies the first 6 requirements, and if the hash function satisfies the first 5 requirements , so this hash function is weak hash function.