Collision resistance Should be hard to find x, x such that h(x =h(x') Brute-force collision search is o(2n/2), not o(2n) n= number of bits in the output of hash function For SHA-1, this means o(280)VS 0(2b) Reason: birthday paradox slide 26
slide 26 Collision Resistance Should be hard to find x, x’ such that h(x)=h(x’) Brute-force collision search is O(2n/2), not O(2n ) n = number of bits in the output of hash function For SHA-1, this means O(280) vs. O(2160) Reason: birthday paradox
One-Way vs Collision Resistance One-wayness does not imply collision resistance Suppose g is one-way Define h(x as g(X' )where xis x except the last bit h is one-way(to invert h, must invert g Collisions for h are easy to find: for anyx, h(XO)=h(x1 Collision resistance does not imply one-wayness Suppose g is collision-resistant Define h(x to be ox if x is n-bit long, 1g(x)otherwise Collisions for h are hard to find: if y starts with o, then there are no collisions, ify starts with 1, then must find collisions n g h is not one way half of all y's (those whose first bit is O)are easy to invert (how?); random y is invertible with probab. 1/2 slide 27
slide 27 One-Way vs. Collision Resistance One-wayness does not imply collision resistance Suppose g is one-way Define h(x) as g(x’) where x’ is x except the last bit h is one-way (to invert h, must invert g) Collisions for h are easy to find: for any x, h(x0)=h(x1) Collision resistance does not imply one-wayness Suppose g is collision-resistant Define h(x) to be 0x if x is n-bit long, 1g(x) otherwise Collisions for h are hard to find: if y starts with 0, then there are no collisions, if y starts with 1, then must find collisions in g h is not one way: half of all y’s (those whose first bit is 0) are easy to invert (how?); random y is invertible with probab. 1/2
Weak collision resistance Given randomly chosen x, hard to find x such that h(x)=h(X') Attacker must find collision for a specific X. By contrast, to break collision resistance, enough to find any collision Brute- force attack requires o(2n) time lide 28
slide 28 Weak Collision Resistance Given randomly chosen x, hard to find x’ such that h(x)=h(x’) Attacker must find collision for a specific x. By contrast, to break collision resistance, enough to find any collision. Brute-force attack requires O(2n ) time
Which Property Do We Need? UNIX passwords stored as hash(password) k One-wayness: hard to recover password Integrity of software distribution k Weak collision resistance But software images are not really random. maybe need full collision resistance Auction bidding Alice wants to bid B, sends H(B), later reveals B k One-wayness: rival bidders should not recover b k Collision resistance: Alice should not be able to change her mind to bid B such that H(BEH(B) slide 29
slide 29 Which Property Do We Need? UNIX passwords stored as hash(password) One-wayness: hard to recover password Integrity of software distribution Weak collision resistance But software images are not really random… maybe need full collision resistance Auction bidding Alice wants to bid B, sends H(B), later reveals B One-wayness: rival bidders should not recover B Collision resistance: Alice should not be able to change her mind to bid B’ such that H(B)=H(B’)
Common hash Functions MD5 128-bit output still used very widely Completely broken by now RIPEMD-160 k 160-bit variant of md-5 SHA-1(Secure Hash Algorithm 160-bit output US government(NIST) standard as of 1993-95 Also the hash algorithm for Digital Signature Standard (DSS) slide 30
slide 30 Common Hash Functions MD5 128-bit output Still used very widely Completely broken by now RIPEMD-160 160-bit variant of MD-5 SHA-1 (Secure Hash Algorithm) 160-bit output US government (NIST) standard as of 1993-95 Also the hash algorithm for Digital Signature Standard (DSS)