Hash Functions

•Condenses arbitrary message to fixed size
•Usually assume that the hash function is public and not keyed
– MAC which is keyed (will discuss soon)
•Hash used to detect changes to message
•Can use in various ways with message
– most often to create a password, digital signature etc.

Hash Function

Message

Hash Function Properties

A Hash Function produces a fingerprint of some file/message/data h = H(M)

•condenses a variable-length message M to a fixed sized fingerprint

Requirements for Hash Functions

•Can be applied to any sized message M

•Produces fixed-length output h

•Easy to compute h = H(M) for any message M

•Given h, it is infeasible to find x s.t. H(x) = h one-way property

•Given x, it is infeasible to find y s.t. H(y) = H(x) weak collision resistance

•It is infeasible to find any x,y s.t. H(y) = H(x) strong collision resistance

MD5

•Designed by Ronald Rivest (the R in RSA)

•Latest in a series of MD2, MD4

•Produces a 128-bit hash value

•Until recently was the most widely used hash algorithm in recent times have both brute-force & cryptanalytic concerns

•Specified as Internet standard RFC1321

MD5 Overview

Strength of MD5

•MD5 hash is dependent on all message bits •Rivest claims security is good as can be

•Known attacks are:

Berson (92) attacked any 1 round using differential cryptanalysis (but can’t extend)
Boer & Bosselaers (93) found a pseudo collision (again unable to extend)
Dobbertin (96) created collisions on MD compression function (but initial constants prevent exploit)
Crypto 2004 attacks on SHA-0 and MD5

•Conclusion is that MD5 has been shown to be vulnerable

•MD5 Collision Demo: http://www.mscs.dal.ca/~selinger/md5collision/

Secure HASH Functions

Purpose of the HASH function is to produce a ”fngerprint.
Properties of a HASH function H :
- H can be applied to a block of data at any size
- H produces a fied length output
- H(i) is easy to compute for any given i.
- For any given block i, it is computationally infeasible to fnd i such that H(i) = h
- For any given block i, it is computationally infeasible to fnd with H(y) = H(i).
- It is computationally infeasible to fnd any pair (i,

y) such that H(i) = H(y)

Message Digest Generation Using SHA-1

Comparision-Secure HASH functions

	SHA-1	MD5	RIPEMD-160
Digest length	160 bits	128 bits	160 bits
Basic unit of processing	512 bits	512 bits	512 bits
Number of steps	80 (4 rounds of 20)	64 (4 rounds of 16)	160 (5 paired rounds of 16)
Maximum message size	2⁶⁴-1 bits		