## 7/21/2016

### cryptography16

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.