Question

(Birthday attack) A birthday attack is a type of cryptographic attack that exploits the mathematics behind the birthday problem in probability theory. It can be used to find collisions in a cryptographic hash function. Suppose that we have a hash function which, when supplied with a random input, returns one of 256 equally likely values. The attack generates n random inputs, supplies them into the hash function, and obtains n returned values (each is chosen from the 256 possible values uniformly at random). Use MATLAB or other programming language, compute and plot the probability of at least two returned values being the same (i.e., collision happens), for n = 1 to 30. (Submit your math formula, the code, and a nice-looking plot.)

Answer 1

The probability values that at least 2 birthdays match (for n = 1:30) are:

   0.00000
   0.00240
   0.01080
   0.02960
   0.03960
   0.06360
   0.07440
   0.10560
   0.12920
   0.14560
   0.18960
   0.23360
   0.27560
   0.30320
   0.33680
   0.37280
   0.42000
   0.45640
   0.49480
   0.55360
   0.57240
   0.61120
   0.64520
   0.67840
   0.68960
   0.71400
   0.75960
   0.78080
   0.79440
   0.83960

Matlab code for above result:

K = 2500;
% Loop K times
for jj = 1:K

% iterations for different n
for n = 1:30
% birthday values array
bd = ceil(256*rand(1,n));
% sort bd values
bd_sorted = sort(bd);
% initialise flag variable (flag = 1 if bd values clash)
flag(jj,n) = 0;
% check if bd values clash
for ii = 1:n-1
if (bd_sorted(ii) == bd_sorted(ii+1))
flag(jj,n) = 1;
end
end
end
end
disp(transpose(mean(flag)));

plot(flag);