Hash functions 曹天杰 Tianjie Cao ticao@cumt.edu.cn College of Computer Science and Technology, China University of Mining and Technology, Xuzhou China 中国矿业大学计算机科学与技术学院 2003.5,26
1 曹天杰 Tianjie Cao tjcao@cumt.edu.cn College of Computer Science and Technology, China University of Mining and Technology, Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.5.26 Hash Functions
Hash Functions: Introduction Cryptographic hash functions put -any lengt Output- fixed length H(x)-easy H(x)-one way hard to invert H(x)collision free
2 Hash Functions: Introduction • Cryptographic hash functions – Input – any length – Output – fixed length – H(x) – easy – H(x) – one way • “hard to invert” – H(x) collision free
Purposes for hash functions Data Integrity Ex: Tripwire Message digest y=h(x). y is called the message digest 160 bits in size -"birthday attack Message source Digital Signatures Message Authentication CodeS(MAC)
3 Purposes for hash functions • Data Integrity – Ex: Tripwire – Message digest • y = h(x). y is called the message digest. • 160 bits in size – “birthday attack” • Message Source • Digital Signatures • Message Authentication Codes (MAC)
Digital Signatures and Message Authentication Code(mac)overview Suppose alice and bob share a secret key k which determines hash function hk Alice sends(x, y) to Bob where y =h, (x) Bob receives(x, y) and verifies with y hk(x) If condition holds, neither x nor y was modified in transit
4 Digital Signatures and Message Authentication Code (MAC) overview • Suppose Alice and Bob share a secret key k which determines hash function hk • Alice sends (x, y) to Bob where y = hk (x) • Bob receives (x,y) and verifies with y = hk (x). If condition holds, neither x nor y was modified in transit
Keyed hash functions (X, Y,K, H)is a keyed hash family, where X is a set of possible messages y is the set of possible message digests, or authentication tags K is the keyspace h is a set of hash functions For each key K there is a hash function hx: X,Y H Assume x>=Y(even better, 2X>=YD
5 Keyed hash functions (X,Y,K,H) is a keyed hash family, where • X is a set of possible messages • Y is the set of possible message digests, or authentication tags • K is the keyspace • H is a set of hash functions • For each key K there is a hash function hK: X → Y in H • Assume |X| >= |Y| (even better, 2|X| >= |Y|)
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 e Unkeyed hash function 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!=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:Ⅹ→ 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 Alice h(x) Oracle
9 The random Oracle model Alice Oracle x h(x)
Ideal hash functions Theorem Let Fx, be an"ideal"family of hash functions If h is a random function in Fx, Y and Xo is the subset of queried messages then Prl h(x)=y]=1/M for all x in Xo 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