Hash FunctionA cryptographic hash function h(x) should provideCompressionoutputlength is small and fixed印One-way given a value y it is infeasible to findan x such that h(x) = y collision resistance infeasible to find x and y,with x ± y such that h(x) = h(y)Note: As h is a compression algorithm, thereshould have a lot of collisions. Collision resistancerequire that it is hard to find any collision6
Hash Function ◼ A cryptographic hash function h(x) should provide ❑ Compression ⎯ output length is small and fixed ❑ One-way ⎯ given a value y it is infeasible to find an x such that h(x) = y ❑ collision resistance ⎯ infeasible to find x and y, with x y such that h(x) = h(y) ◼ Note: As h is a compression algorithm, there should have a lot of collisions. Collision resistance require that it is hard to find any collision 6
Hash Function Security vs.Hash Output LengthIf ahashfunctionis collisionresistant,then itisalsoone-wayThere is a fixed output length for every collision resistanthash function h.To break h against collision resistance using bruteforceattack, the adversary repeatedly chooses random value xcompute h(x) and check if the hash function is equal toany of the hash values of all previously chosen randomvalues.If the output of h is N bits long, what is the expectednumber of times that the adversary needs to try beforefindinga collision?
Hash Function Security vs. Hash Output Length ◼ If a hash function is collision resistant, then it is also one-way. ◼ There is a fixed output length for every collision resistant hash function h. ◼ To break h against collision resistance using bruteforce attack, the adversary repeatedly chooses random value x, compute h(x) and check if the hash function is equal to any of the hash values of all previously chosen random values. ◼ If the output of h is N bits long, what is the expected number of times that the adversary needs to try before finding a collision? 7
Birthday ProblemHow many people must be in a room before probabilityis ≥ 1/2 that two or more have same birthday?1-365/365.364/365.-(365-K+1)/365口Set equal to 1/2 and solve: K = 23口Surprising? A paradox? since we compare all pairs xand yK is about sqrt(365)This problem is related to collision resistance.Question: supposeh's output is 8o bits long, howmany valuesmusttheadversarytrybeforehavingtheprobabilityofcompromising collisionresistancebeatleast 1/2?Implication: secure N bit hash requires 2N/2 work to“break"(withrespecttocollisionresistance)8
Birthday Problem ◼ How many people must be in a room before probability is 1/2 that two or more have same birthday? ❑ 1 − 365/365 364/365 (365−K+1)/365 ❑ Set equal to 1/2 and solve: K = 23 ◼ Surprising? A paradox? since we compare all pairs x and y ◼ K is about sqrt(365) ◼ This problem is related to collision resistance. ❑ Question: suppose h’s output is 80 bits long, how many values must the adversary try before having the probability of compromising collision resistance be at least 1/2? ◼ Implication: secure N bit hash requires 2N/2 work to “break” (with respect to collision resistance). 8