Ideal hash functions it is a simple matter to compute the probability that k random elements z1,..., ZK E Z are distinct The first choice Z, is arbitrary; the probability that Z2 =Z1 is 1-In; the probability that z3 is distinct from Z, and z2 is 1-2/n, etc we estimate the probability of no collisions to be k-1 )(-)-(-)2=I(-
11 Ideal hash functions • it is a simple matter to compute the probability that k random elements z1 , . . . , zk Z are distinct. • The first choice z1 is arbitrary; the probability that z2 != z1 is 1 - l/n; the probability that z3 is distinct from z1 and z2 is 1 - 2/n, etc. • we estimate the probability of no collisions to be
Ideal hash functions ·| fx is a small real number,then1-X≈ex k k-1 ≈ 一k(k So we estimate the probability of at least one collision to be k(k e 12
12 Ideal hash functions • If x is a small real number, then 1 - x e -x . • So we estimate the probability of at least one collision to be
Ideal hash functions If we denote this probability by s, then we can solve for k as a function of n and e If we ignore the term -k, then we estimate k -) e ≈ E k(k-1) ≈ln(1-) k≈1/h、 k2-k≈nln
13 Ideal hash functions • If we denote this probability by , then we can solve for k as a function of n and • If we ignore the term -k, then we estimate
Ideal hash functions If we takee = 5 then our estimate is k≈1.17Vm Taking n= 365 in our estimate, we get k x 22.3 It is usually suggested that the minimum acceptable size of a message digest is 128 bits(the birthday attack will require over 264 hashes in this case
14 Ideal hash functions • If we take = .5, then our estimate is • Taking n = 365 in our estimate, we get k 22.3. • It is usually suggested that the minimum acceptable size of a message digest is 128 bits (the birthday attack will require over 2 64 hashes in this case)
Iterated hash function Suppose that compress: 0, 1 m>0, 1mis a compression function Preprocessing Given input x, x>=m+t+l, construct y using a public algorithm such that ly is a multiple of t For example: y=x pad(x) Lety=y1‖y21….yx 1<==;v|=t 15
15 Iterated hash function Suppose that compress: {0,1}m+t → {0,1}m is a compression function. Preprocessing Given input x, |x| >= m+t+1, construct y using a public algorithm such that |y| is a multiple of t. For example: y = x || pad(x) Let y = y1 || y2 || … || yr, 1<=i<=r, |yi |=t