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β€²)?


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, privacy policy and cookie policy

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