Unformatted text preview:

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

NCSU CSC (ECE) 574 - Cryptographic Hash Functions

Download Cryptographic Hash Functions
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Cryptographic Hash Functions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Cryptographic Hash Functions 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?