I found this paper: https://www.researchgate.net/profile/Ganesh-Gupta-7/publication/271704029_What_is_Birthday_attack/links/54cfbdcc0cf24601c0958a1e/What-is-Birthday-attack.pdf

The following attack is outlined on page 9:

Two types of messages - legitimate message π‘₯1 ; fraudulent message π‘₯2 ; m bit
length; one -way hash function H

π‘₯1β€², π‘₯2β€² Is a minor modification of π‘₯1, π‘₯2 with 𝐻(π‘₯1β€²) = 𝐻(π‘₯2β€²).

1) Generate 𝑑 = 2^(π‘š/2) minor modifications of π‘₯1β€²of π‘₯1.
2) Hash each such modified message, and store the hash-values such that they
can be subsequently searched on hash -values. This can be done in 𝑂(𝑑) total
time using conventional hashing.
3) Generate minor modifications π‘₯2β€² π‘œπ‘“ π‘₯2 , computing 𝐻(π‘₯2β€²) for each and checking 
for any matches with any π‘₯1β€² above; continue until a match is found.

I'm confused about step 3. How would 𝐻(π‘₯1β€²) = 𝐻(π‘₯2β€²)? I thought the birthday problem meant finding collisions such that 𝐻(π‘₯1) = 𝐻(π‘₯1β€²), and 𝐻(π‘₯2) = 𝐻(π‘₯2β€²)?


1 Answer 1


Yuval's attack is slightly different from the standard birthday attack where we look for a repeated output in a single family of inputs. Instead we look for a repeated output across two families of inputs with at least one member of each family producing the repeated ouput. The probabilities are slightly different, but in a complexity sense are both $O(\sqrt H)$ for output ranges of size $H$ (or $O(2^{m/2})$ for $m$-bit output values) where in the worst case outputs are approximately uniformly distributed.

One can see this in an approximate sense as generating $n$-outputs in each family creates $n^2$ pairs of values with one half of each pair coming from each family. Each pair has a $1/H$ chance of matching the two halves. We can approximate the chance of finding a repeat as $$1-\left(1-\frac1H\right)^{n^2}$$ and for $n\sim\sqrt H$ this will be about $(1-1/e)$. Note however that this is not a rigorous estimate as the probabilities are not independent. More rigorous derivations are possible (see Girault et al., Eurocrypt '88).


Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.