Unkeyed hash functions An unkeyed hash function is a mapping h: X>Y where X is a set of possible messages Y is the set of possible message digests Unkeyed hash function K|=1 Ex SHA-1(successor of MD4)
6 Unkeyed hash functions An unkeyed hash function is a mapping h: X → Y, where • X is a set of possible messages • Y is the set of possible message digests •Unkeyed hash function –|K| = 1 –Ex. SHA-1 (successor of MD4)
Conditions of a secure hash function Preimage Find x such that h(x)=y, given y and the function fO one-way(preimage resistant) Second Preimage Find x'!=x, such that h(x)=h(x'), given x and the function ho weak collision resistance( Second preimage resistant) Collision Find h(x)=h(x')such that !=x, given function ho strong collision resistance( Collision resistant)
7 Conditions of a secure hash function • Preimage – Find x such that h(x) = y, given y and the function f(). – one-way(preimage resistant) • Second Preimage – Find x’ != x, such that h(x) = h(x’), given x and the function h(). – weak collision resistance(Second preimage resistant) • Collision – Find h(x) = h(x’) such that x != x’, given function h() – strong collision resistance(Collision resistant)
The random oracle model This is an idealized model in which captures the concept of a hash function in an ideal fashion · ahash function h:X→ Y is chosen at random from the set Fx,y of all functions from X to y Given x, its hash y can only be obtained from an oracle
8 The random oracle model This is an idealized model in which captures the concept of a hash function in an ideal fashion. • A hash function h: X → Y is chosen at random from the set F X,Y of all functions from X to Y. Given x, its hash y can only be obtained from an oracle
The random Oracle model h(x) Oracle
9 The random Oracle model Alice Oracle x h(x)
Ideal hash functions Theorem Let Fx, r be an ideal family of hash functions If h is a random function in ek, r and yo is the subset of queried messages then Pr[ h(x)=y]=1/M for all x in X and all y in y, where M is the cardinality of y
10 Ideal hash functions Theorem Let FX,Y be an “ideal” family of hash functions. If h is a random function in FX,Y and X0 is the subset of queried messages then Pr[ h(x)=y ] = 1/M for all x in X\X0 and all y in Y, where M is the cardinality of Y