Créer une présentation
Télécharger la présentation

Télécharger la présentation
## David Evans cs.virginia/evans

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Lecture 8:**Hashing David Evans http://www.cs.virginia.edu/evans Note: only 3 people (out of 4) have voted that notes are useful. I won’t make notes (regularly) until at least 10 people do. CS588: Security and Privacy University of Virginia Computer Science**Remote Coin Flipping (Ch 1)**Picks random x Bob Alice f (x) Picks “odd” or “even” Alice wins if x does not match Bob’s pick “odd” or “even” Checks f (x) matches value received in step 1 x University of Virginia CS 588**Magic Function f**• One Way: • For every integer x, easy to compute f(x) • Given f (x), hard to find any information about x • Collision Resistant: • “Impossible” to find pair (x, y) where x y and f (x)=f (y) University of Virginia CS 588**Normal CS Hashing**“dog” “neanderthal” “horse” H (char s[]) = (s[0] – ‘a’) mod 10 University of Virginia CS 588**Regular Hash Functions**• Many-to-one: maps a large number of values to a small number of hash values • Even distribution: for typical data sets, P(H(x) = n) = 1/N where N is the number of hash values and n = 0 .. N – 1. • Efficient: H(x) is easy to compute. How well does H (char s[]) = (s[0] – ‘a’) mod 10 satisfy these properties? University of Virginia CS 588**Cryptographic Hash Functions**• One-way: for given h, it is hard to find x such that H(x) = h. • Collision resistance: Weak collision resistance: given x, it is hard to find y x such that H(y) = H(x). Strong collision resistance: it is hard to find any x and y x such that H(y) = H(x). University of Virginia CS 588**Fair Remote Coin Flipping?**What goes wrong if f is not one-way? What goes wrong if f is not weak collision resistant? What goes wrong if f is not strong collision resistant? Picks random x Bob Alice f (x) Picks “odd” or “even” Alice wins if x does not match Bob’s pick “odd” or “even” Checks f (x) matches value received in step 1 x University of Virginia CS 588**Using Hashes**• Alice wants to send Bob and “I owe you” message. • Bob should be able to show the message to a judge to compel Alice to pay up. • Bob should not be able to make his own “I owe you” from Alice, or change the contents of the one she sent him. University of Virginia CS 588**IOU Protocol (Attempt 1)**M H(M) Bob Alice M H(M) Hmmm...Bob can just make up M and H(M)! Judge University of Virginia CS 588**IOU Protocol (Attempt 2)**M EKA[H(M)] Bob Alice secret key KA M EKA[H(M)] Can Bob cheat? Shared secret KA Can Alice cheat? Yes, send Bob: M, junk. Judge will think Bob cheated! Judge knows KA University of Virginia CS 588**IOU Protocol (Attempt 3)**M EKRA[H(M)] Bob Alice knows KUA {KUA, KRA} M EKRA[H(M)] Why not just use EKRA[M]? Bob can verify H(M) by decrypting, but cannot forge M, EKRA[H(M)] pair without knowing KRA. Known public-key encyrption algorithms are slow Judge knows KUA University of Virginia CS 588**No Collision Resistance**• Suppose we use: H (char s[]) = (s[0] – ‘a’) mod 10 • Alice sends Bob: “I, Alice, owe Bob $2.”, EKRA[H (M)] • Bob sends Judge: “I, Alice, owe Bob $2000000.”, EKRA[H (M)] • Judge validates EKUA[EKRA[H (M)]] = H(“I, Alice, owe Bob $2000000.”) and makes Alice pay. University of Virginia CS 588**Weak Collision Resistance**• Given x, it should be hard to find y x such that H(y) = H(x). • Similar to a block cipher except no need for secret key: • Changing any bit of x should change most of H(x). • The mapping between x and H(x) should be confusing (complex and non-linear). University of Virginia CS 588**A Better Hash Function?**• H(x) = DES (x, 0) • Weak collision resistance? • Given x, it should be hard to find y x such that H(y) = H(x). • Yes – DES is one-to-one. (These is no such y.) • A good hash function? • No, its output is as big as the message! University of Virginia CS 588**What we need:**• Produce small number of bits (say 64) that depend on the whole message in a confusing, non-linear way. • Have we seen anything like this? University of Virginia CS 588**Cipher Block Chaining**Pn P2 P1 IV ... DES K DES DES K K Cn C2 C1 Use last ciphertext block as hash. Depends on all plaintext blocks. University of Virginia CS 588**Actual Hashing Algorithms**• Based on cipher block chaining • No need for secret key or IV (just use 0) • Don’t use DES • Performance • Better to use bigger blocks • MD5 [Rivest92] – 512 bit blocks, produces 128-bit hash • SHA [NIST95] – 512 bit blocks, 160-bit hash University of Virginia CS 588**Why big hashes?**• 3DES is (probably) secure with 64-bit blocks, why do secure hash functions need at least 128 bit digests? • 64 bits is fine for weak collision resistance, but we need strong collision resistance too. University of Virginia CS 588**Strong Collision Resistance**• It is hard to find any x and y x such that H(y) = H(x). • Difference from weak: • Attacker gets to choose both x and y, not just y. • Scenario: • Suppose Bob gets to write IOU message, send it to Alice, and she signs it. University of Virginia CS 588**Cryptographic Hash Functions**• Many-to-one: compresses • Even distribution: P(H(x) = n) = 1/N • Efficient: H(x) is easy to compute. • One-way: given H(x), hard to find x • Collision resistance: Weak collision resistance: given x, it is hard to find y x such that H(y) = H(x). Strong collision resistance: it is hard to find any x and y x such that H(y) = H(x). University of Virginia CS 588**IOU Request Protocol**x EKRA[H(x)] Bob Alice knows KUA {KUA, KRA} y EKRA[H(x)] Bob picks x and y such that H(x) = H(y). Judge knows KUA University of Virginia CS 588**Finding x and y**Bob generates 210 different agreeable (to Alice) xi messages: I, { Alice | Alice Hacker | Alice P. Hacker | Ms. A. Hacker }, { owe | agree to pay } Bob { the sum of | the amount of } { $2 | $2.00 | 2 dollars | two dollars } { by | before } { January 1st | 1 Jan | 1/1 | 1-1 } { 2006 | 2006 AD}. University of Virginia CS 588**Finding x and y**Bob generates 210 different agreeable (to Bob) yi messages: I, { Alice | Alice Hacker | Alice P. Hacker | Ms. A. Hacker }, { owe | agree to pay } Bob { the sum of | the amount of } { $2 quadrillion | $2000000000000000 | 2 quadrillion dollars | two quadrillion dollars } { by | before } { January 1st | 1 Jan | 1/1 | 1-1 } { 2006 | 2006 AD}. University of Virginia CS 588**Bob the Quadrillionaire!?**• For each message xi and yi, Bob computes hxi = H(xi) and hyi = H(yi). • If hxi = hyjfor some i and j, Bob sends Alice xi, gets EKRA[H(x)]back. • Bob sends the judge yjand EKRA[H(xi)]. • Is this different from when Alice chooses x? University of Virginia CS 588**Chances of Success**• Hash function generate 64-bit digest (n = 264) • Hash function is good (randomly distributed and diffuse) • Chance a randomly chosen message maps to a given hash value: 1 in n = 2-64 • By hashing m good messages, chance that a randomly chosen bad message maps to one of the m different hash values: m * 2-64 • By hashing m good messages and m bad messages: m * m * 2-64 (approximation) University of Virginia CS 588**Is Bob a Quadrillionaire?**• m = 210 • 210 * 210 * 2-64 = 2-44 (still a pauper) • Try m= 232 • 232 * 232 * 2-64 = 20 = 1 (yippee!) • Flaw: some of the messages might hash to the same value, might need more than 232 to find match. University of Virginia CS 588**Birthday “Paradox”**What is the probability that two people in this room have the same birthday? Text, Chapter 3.6 University of Virginia CS 588**Birthday Paradox**Ways to assign k different birthdays without duplicates: N = 365 * 364 * ... * (365 – k + 1) = 365! / (365 – k)! Ways to assign k different birthdays with possible duplicates: D = 365 * 365 * ... * 365 = 365k University of Virginia CS 588**Birthday “Paradox”**Assuming real birthdays assigned randomly: N/D = probability there are no duplicates 1 - N/D = probability there is a duplicate = 1 – 365! / ((365 – k)!(365)k) University of Virginia CS 588**Generalizing Birthdays**n! (n – k)! nk P(n, k) = 1 – Given k random selections from n possible values, P(n, k) gives the probability that there is at least 1 duplicate. University of Virginia CS 588**Birthday Probabilities**P(no two match) = 1 – P(all are different) P(2 chosen from N are different) = 1 – 1/N P(3 are all different) = (1 – 1/N)(1 – 2/N) P(n trials are all different) = (1 – 1/N)(1 – 2/N) ... (1 – (n – 1)/N) ln (P) = ln (1 – 1/N) + ln (1 – 2/N) + ... ln (1 – (k – 1)/N) University of Virginia CS 588**Happy Birthday Bob!**ln (P) = ln (1 – 1/N) + ... + ln (1 – (k – 1)/N) For 0 < x < 1: ln (1 – x) x ln (P) – (1/N + 2/N + ... + (n – 1)/N) Gauss says: 1 + 2 + 3 + 4 + ... + (n – 1) + n = ½ n (n + 1) So, ln (P) ½ (k-1) k/N Pe½ (k-1)k / N Probability of match 1 –e½ (k-1)k / N University of Virginia CS 588**Applying Birthdays**P(n, k) > 1 – e-k*(k-1)/2n • For n = 365, k = 20: P(365, 20) > 1 – e-20*(19)/2*365 P(365, 20) > .4058 • For n = 264, k = 232: P (264, 232) > .39 • For n = 264, k = 233: P (264, 233) > .86 • For n = 264, k = 234: P (264, 234) > .9996 University of Virginia CS 588**Is 128 bits enough?**• For n = 2128, k = 240: P (2128, 240) > 10-15 • If your guesses are random, need to try 240 inputs to have a 10-15 chance of finding a collision • Assumes you hash function is perfect University of Virginia CS 588**A Most Disturbing Program!**From http://www.freedom-to-tinker.com/archives/000664.html #!/usr/bin/perl -w use strict; use Digest::MD5 qw(md5_hex); # Create a stream of bytes from hex. my @bytes1 = map {chr(hex($_))} qw(d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c 2f ca b5 87 12 46 7e ab 40 04 58 3e b8 fb 7f 89 55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 71 41 5a 08 51 25 e8 f7 cd c9 9f d9 1d bd f2 80 37 3c 5b d8 82 3e 31 56 34 8f 5b ae 6d ac d4 36 c9 19 c6 dd 53 e2 b4 87 da 03 fd 02 39 63 06 d2 48 cd a0 e9 9f 33 42 0f 57 7e e8 ce 54 b6 70 80 a8 0d 1e c6 98 21 bc b6 a8 83 93 96 f9 65 2b 6f f7 2a 70); my @bytes2 = map {chr(hex($_))} qw(d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c 2f ca b5 07 12 46 7e ab 40 04 58 3e b8 fb 7f 89 55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 f1 41 5a 08 51 25 e8 f7 cd c9 9f d9 1d bd 72 80 37 3c 5b d8 82 3e 31 56 34 8f 5b ae 6d ac d4 36 c9 19 c6 dd 53 e2 34 87 da 03 fd 02 39 63 06 d2 48 cd a0 e9 9f 33 42 0f 57 7e e8 ce 54 b6 70 80 28 0d 1e c6 98 21 bc b6 a8 83 93 96 f9 65 ab 6f f7 2a 70); # Print MD5 hashes print md5_hex(@bytes1), "\n", md5_hex(@bytes2), "\n"; 79054025255fb1a26e4bc422aef54eb4 79054025255fb1a26e4bc422aef54eb4 University of Virginia CS 588**Hash Collisions**• Collisions announced in SHA-0 at Crypto 2004 • No collisions yet found in SHA-1 (which replaced SHA-0 as a standard in 1994) • NIST is nervous http://csrc.nist.gov/hash_standards_comments.pdf University of Virginia CS 588**NIST Comments**• “At the recent Crypto2004 conference, researchers announced that they had discovered a way to "break" a number of hash algorithms, including MD4, MD5, HAVAL-128, RIPEMD and the long superseded Federal Standard SHA-0 algorithm. The current Federal Information Processing Standard SHA-1 algorithm, which has been in effect since it replaced SHA-0 in 1994, was also analyzed, and a weakened variant was broken, but the full SHA-1 function was not broken and no collisions were found in SHA-1. The results presented so far on SHA-1 do not call its security into question. However, due to advances in technology, NIST plans to phase out of SHA-1 in favor of the larger and stronger hash functions (SHA-224, SHA-256, SHA-384 and SHA-512) by 2010.” University of Virginia CS 588**Charge**We’ll cover SSL after Spring Break… but, this should make you nervous… Wednesday 3:30 Chenxi Wang Seminar “Defending against Large Scale Attacks on the Internet” Thursday 9:30 (please arrive on time for class, not like usual!) Chenxi Wang guest lecture Using hashes to provide censorship-resistant publishing University of Virginia CS 588