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 l=z1 is 1-n, the probability that z3 is distinct from z, and z is 1-2/n, etc we estimate the probability of no collisions to be k-1 k-1
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 Ifx is a small real number then 1-xye-x k-1 k-1 ≈ t=1 -klk So we estimate the probability of at least one collision to be -kk 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 ≈ k(k-1) ≈In(1-e) k≈1/nln k2-k≈n1n E 13
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 takes =,5 then our estimate is k≈1.17Vn 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, 1m>10, 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) ety=yy21|..‖y 1<=i<=Fy|=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