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