Computer Science CSC/ECE 574 Dr. Peng Ning 1 CSC/ECE 574 Computer and Network Security Topic 4. Cryptographic Hash Functions Computer Science CSC/ECE 574 Dr. Peng Ning 2 Outline • Hash function lengths • Hash function applications • MD5 standard • SHA-1 standard • Hashed Message Authentication Code (HMAC) Computer Science CSC/ECE 574 Dr. Peng Ning 3 Hash Function Properties Computer Science CSC/ECE 574 Dr. Peng Ning 4 Hash Function • Also known as – Message digest – One-way transformation – One-way function – Hash • Length of H(m) much shorter then length of m • Usually fixed lengths: 128 or 160 bits Message of arbitrary length Hash A fixed-length short message Computer Science CSC/ECE 574 Dr. Peng Ning 5 Desirable Properties of Hash Functions • Consider a hash function H – Performance: Easy to compute H(m) – One-way property: Given H(m) but not m, it’s computationally infeasible to find m – Weak collision resistance (free): Given H(m), it’s computationally infeasible to find m’ such that H(m’) = H(m). – Strong collision resistance (free): Computationally infeasible to find m1, m2 such that H(m1) = H(m2) Computer Science CSC/ECE 574 Dr. Peng Ning 6 Length of Hash Image • Question – Why do we have 128 bits or 160 bits in the output of a hash function? – If it is too long • Unnecessary overhead – If it is too short • Birthday paradox • Loss of strong collision propertyComputer Science CSC/ECE 574 Dr. Peng Ning 7 Birthday Paradox • Question: – What is the smallest group size k such that • The probability that at least two people in the group have the same birthday is greater than 0.5? • Assume 365 days a year, and all birthdays are equally likely – P(k people having k different birthdays): Q(365,k) = 365!/(365-k)!365k – P(at least two people have the same birthday): P(365,k) = 1-Q(365,k) ≥ 0.5 – k is about 23 Computer Science CSC/ECE 574 Dr. Peng Ning 8 Birthday Paradox (Cont’d) • Generalization of birthday paradox – Given • a random integer with uniform distribution between 1 and n, and • a selection of k instances of the random variables, – What is the least value of k such that • There will be at least one duplicate • with probability P(n,k) > 0.5, ? Computer Science CSC/ECE 574 Dr. Peng Ning 9 Birthday Paradox (Cont’d) • Generalization of birthday paradox – P(n,k) ≈ 1 – e-k*(k-1)/2n – For large n and k, to have P(n,k) > 0.5 with the smallest k, we have – Example • 1.18*(365)1/2 = 22.54 € k = 2(ln2)n = 1.18 n ≈ nComputer Science CSC/ECE 574 Dr. Peng Ning 10 Birthday Paradox (Cont’d) • Implication for hash function H of length m – With probability at least 0.5 – If we hash about 2m/2 random inputs, – Two messages will have the same hash image – Birthday attack • Conclusion – Choose m ≥ 128 Computer Science CSC/ECE 574 Dr. Peng Ning 11 Hash Function Applications Computer Science CSC/ECE 574 Dr. Peng Ning 12 Application: File Authentication • Want to detect if a file has been changed by someone after it was stored • Method – Compute a hash H(F) of file F – Store H(F) separately from F – Can tell at any later time if F has been changed by computing H(F’) and comparing to stored H(F) • Why not just store a duplicate copy of F???Computer Science CSC/ECE 574 Dr. Peng Ning 13 Application: User Authentication • Alice wants to authenticate herself to Bob – assuming they already share a secret key K • Protocol: Alice Bob time “I’m Alice” picks random number R R computes Y=H(R|K) Y verifies that Y=H(R|K) Computer Science CSC/ECE 574 Dr. Peng Ning 14 User Authentication… (cont’d) • Why not just send… – …K, in plaintext? – …H(K)? , i.e., what’s the purpose of R? Computer Science CSC/ECE 574 Dr. Peng Ning 15 Application: Commitment Protocols • Ex.: A and B wish to play the game of “odd or even” over the network 1. A picks a number X 2. B picks another number Y 3. A and B “simultaneously” exchange X and Y 4. A wins if X+Y is odd, otherwise B wins • If A gets Y before deciding X, A can easily cheat (and vice versa for B) – How to prevent this? Computer Science CSC/ECE 574 Dr. Peng Ning 16 Commitment… (Cont’d) • Can either A or B successfully cheat now? AB Z = H(X) Picks Y Y X verifies that H(X) = Z A picks X and computes Z=H(X) • Proposal: A must commit to X before B will send Y • Protocol: Computer Science CSC/ECE 574 Dr. Peng Ning 17 Commitment… (Cont’d) • Why is sending H(X) better than sending X? • Why is sending H(X) good enough to prevent A from cheating? • Why is it not necessary for B to send H(Y) (instead of Y)? • What problems are there if: 1. The set of possible values for X is small? 2. B can predict the next value X that A will pick? Computer Science CSC/ECE 574 Dr. Peng Ning 18 Application: Message Encryption • Assume A and B share a secret key K – but don’t want to just use encryption of the message with K • A sends B the (encrypted) random number R1, B sends A the (encrypted) random number R2 • And then…Computer Science CSC/ECE 574 Dr. Peng Ning 19 one-time pad E C1 C2 C3 C4 M1 M2 M3 M4 Initialization Vector E E E Key 64 64 64 64 64 64 64 46 + padding 64 one-time pad C1 C2 C3 C4 M1 M2 M3 M4 R1 | R2 Key 64 64 64 64 64 64 64 46 + padding 64 = Concatenate, then Hash C+H C+H C+H C+H C+H • R1 | R2 is used like the IV of OFB mode, but C+H replaces encryption; as good as encryption? Computer Science CSC/ECE 574 Dr. Peng Ning 20 Application: Message Authentication • A wishes to authenticate (but not encrypt) a message M (and A, B share secret key K) A B M, R, Y verifies that Y = H(M|K|R) 1. picks random number R 2. computes Y = H(M|K|R) • Why is R needed? Why is K needed? Computer Science CSC/ECE 574 Dr. Peng Ning 21 Application: Digital Signatures Message m Hash H(m) Sign Bob’s Private key Signature (encrypted hash) Generating a signature Message m Hash H(m) Verify Bob’s Public key Signature Valid / Not Valid Verifying a signature • Only one party (Bob) knows the private key Computer Science CSC/ECE 574 Dr.
View Full Document