# 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.

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.

For a hash function h= H(x) which 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 a weak hash function.