In the context of secure systems, what is a hash function? In what way does a hash function differ from an encryption function?

Hash Function

Used to provide integrity of a message

Purpose is to produce a fixed-size hash-value where:

h is the hash value

H is the hash function

M is the message

Any change in M, however small, should produce a different h-value

M >> H >> h

Note message can be any size. H is the Hash Function and h is the Hash Value which is a fixed size (e.g. 160 bits)

Note that a hash function is a many-to-one function. Potentially many messages can have the same hash, but finding these should be very difficult

M can be of any size (i.e. arbitrary msg)
H(M) produces a fixed-length output (e.g. 160 bits)
H(M) easy to compute for any message M
One-way property: Given hash value h, computationally infeasible to find M such that H(M) = h (can’t go backwards)
Weak collision resistance
Given M1, infeasible to find M2 such that H(M2) = H(M1)
Clearly necessary to prevent forgery using M2
No matter how alike/unalike the Ms are the Hash Function should not give the same h
Strong collision resistance
Infeasible to find any pair (M1, M2) such that H(M1) = H(M2)
Also necessary to prevent forgery using so-called “Birthday Attack”
No two messages have the same h no matter how big the example, to do this the Hash key must be large enough