CSC 474/574 Dr. Peng Ning 1Computer ScienceCSC 474/574Information Systems SecurityTopic 2.5 Hash FunctionsCSC 474/574 Dr. Peng Ning 2Computer ScienceHash 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 bitsMessage of arbitrary lengthHashA fixed-length short messageCSC 474/574 Dr. Peng Ning 3Computer ScienceRequirements for a Hash Function• Consider a hash function H– Flexibility: Can be applied to a block of data of any size– Convenience (for check): produce a fixed-length shortoutput.– Performance: Easy to compute H(m)– One-way property: Given H(m) but not m, it’s difficult tofind m– Weak collision resistance (free): Given H(m), it’s difficultto find m’ such that H(m’) = H(m).– Strong collision resistance (free): Computationallyinfeasible to find m1, m2 such that H(m1) = H(m2)CSC 474/574 Dr. Peng Ning 4Computer ScienceBirthday Paradox• Question:– What is the minimum value of k such that the probability isgreater than 0.5 that at least two people in a group of kpeople have the same birthday?• Ignore February 29 and assume each birthday is equally likely.– Probability of k people having k different birthdays:Q(365,k)=365!/(365-k)!365k– Probability that at least two people have the same birthday:P(365,k)=1-Q(365,k)– K is about 23.CSC 474/574 Dr. Peng Ning 5Computer ScienceGeneralization of Birthday Paradox• Given a random variable that is an integer with uniformdistribution between 1 and n and a selection of k instances ofthe random variables, what is the least value of k such that theprobability P(n,k) is greater than 0.5 that there is at least oneduplicate?– P(n,k) > 1 – e-k*(k-1)/2n– For large n and k, we have• Implication– For a hash function H with 2m possible outputs, if we apply H tok=(2m)1/2=2m/2 random inputs, the probability that there is at least oneduplicate is greater than 0.5.nnnk ª== 18.1)2(ln2CSC 474/574 Dr. Peng Ning 6Computer ScienceBirthday Attack• The source, A, is prepared to sign a message• The opponent generates 2m/2 variations on the message, andprepares 2m/2 variations on the fraudulent message.• The opponent compares the two sets of messages to find a pairof messages that produces the same hash value. Theprobability of success is greater than 0.5. The opponent repeatsgenerating variations until a match is found.• The opponent offers the valid variation to A for signature, butattaches the signature to the fraudulent variation.CSC 474/574 Dr. Peng Ning 7Computer ScienceHow Many Bits for Hash?• m bits, takes 2m/2 to find two with the same hash• 64 bits, takes 232 messages to search duplicate• Need at least 128 bitsCSC 474/574 Dr. Peng Ning 8Computer ScienceBuilding Hash Using Block ChainingTechniques• Divide M into fixed-size blocks M1, M2, …, Mn• Compute the hash as follows– H0=Initial value– Hi=EMi(Hi-1)– Hash value G=Hn• Weakness– Birthday attack (reason: hash value is too short)– Meet-in-the-middle attackCSC 474/574 Dr. Peng Ning 9Computer ScienceBuilding Hash Using Block Chaining Techniques(Cont’d)• Meet-in-the-middle attack– Get the correct hash value G– Construct any message in the form Q1, Q2, …, Qn-2– Compute Hi=EQi(Hi-1) for 1 ≤i ≤(n-2).– Generate 2m/2 random blocks; for each block X, computeEX(Hn-2).– Generate 2m/2 random blocks; for each block Y, computeDY(G).– With high probability there will be an X and Y such thatEX(Hn-2)= DY(G).– Form the message Q1, Q2, …, Qn-2, X, Y. It has the hashvalue G.CSC 474/574 Dr. Peng Ning 10Computer ScienceModern Hash Functions• MD5– Previous versions (i.e., MD2, MD4) haveweaknesses.• SHA (Secure Hash Algorithm)• SHA-1• RIPEMD-160CSC 474/574 Dr. Peng Ning 11Computer ScienceMD5: Message Digest Version 5input MessageOutput 128 bits DigestCSC 474/574 Dr. Peng Ning 12Computer ScienceMD5: A High-Level ViewMessage 100…0 K bitsMessage Length(K mod 264)Padding(1 to 512 bits)Y0512 bitsY1512 bits…YL-1512 bitsMD5 MD5IV128 bitsCV1MD5CVL-1128-bitdigestCSC 474/574 Dr. Peng Ning 13Computer SciencePadding• Given original message M, add padding bits“10*” such that resulting length is 64 bits lessthan a multiple of 512 bits.• Append (original length in bits mod 264),represented in 64 bits to the padded message• Final message is chopped 512 bits a block• Exercise:– How to add padding bits to a message that isalready a multiple of 512 bits?CSC 474/574 Dr. Peng Ning 14Computer ScienceMD5 (Intermediate) Buffer• Used to hold intermediate and final result of MD5.• 128 bits• Represented as four 32-bit words– (A,B,C,D)– Initially, A=0x67452301, B=0xEFCDAB89,C=0x98BADCFE, D=0x10325476– Stored in little-endian format, A=0x01234567,B=0x89ABCDEF, C=0xFEDCBA98, D=0x76543210.CSC 474/574 Dr. Peng Ning 15Computer ScienceProcessing of A Single Block128-bit vector(Initial or fromthe previous block)512-bit message block (16 words)128-bit resultF(x,y,z)= (xŸy)⁄(~x Ÿ z)G(x,y,z)=(x Ÿ z) ⁄(y Ÿ~ z)H(x,y,z)=x⊕y⊕ zI(x,y,z)= y⊕(x Ÿ ~z)+: addition mod 232xøy: x left rotate y bitsMD5Primitive operationsused in MD5:CSC 474/574 Dr. Peng Ning 16Computer ScienceProcessing of A Single Block (Cont’d)• Every message block contains 16 32-bit words:– X[0] X[1] X[2] … X[15]• Every stage consists of 4 passes over the message block, eachmodifying the MD5 buffer (A,B,C,D).– The four passes use functions F, G, H, I, respectively.• Each round uses one-fourth of a 64-element table T[1…64].– T[i] = 232*abs(sin(i)) represented in 32 bits.• The output of the fourth round is added to the input to the firstround.CSC 474/574 Dr. Peng Ning 17Computer ScienceProcessing of Block mi - 4 RoundsF, T[1..16], X[i]G, T[17..32], X[r2i]H, T[33..48], X[r3i]I, T[49..64], X[r4i]X[i]+ + + +ABC DMDiMD i+1ABC DABC DABC DCSC 474/574 Dr. Peng Ning 18Computer ScienceLogic of Each Round• Each round consists of 16 steps• Each step is of the form– A¨B+((A+g(B,C,D)+X[k]+T[i])<<<s)• Function g is one of F, G, H, I• X[k] is the word in the input• T[i] is the ith word in T• <<<s: circular left shift by s bits.– Followed by a word level circular right shift of oneword.CSC 474/574 Dr. Peng Ning 19Computer ScienceLogic of Each StepA B C DA B C Dg++++<<<sX[k]T[i]CSC 474/574 Dr. Peng Ning 20Computer ScienceLogic of Each Step• Within a round, each of the 16 words of X[i] is