Birthday effect - clarification needed plz.
- by Mark
Please help interpret the Birthday effect as described in Wikipedia:
A birthday attack works as follows:
1) Pick any message m and compute h(m).
2) Update list L. Check if h(m) is in the list L.
3) if (h(m),m) is already in L, a colliding message pair has been found.
else save the pair (h(m),m) in the list L and go back to step 1.
From the birthday paradox we know that we can expect to find a matching entry,
after performing about 2^(n/2) hash evaluations.
Does the above mean 2^(n/2) iterations through the above entire loop (i.e. 2^(n/2) returns to step 1), OR does it mean 2^(n/2) comparisons to individual items already in L.
