# Yuval's birthday attack

The following attack is outlined on page 9:

Input
-----
Two types of messages - legitimate message 𝑥1 ; fraudulent message 𝑥2 ; m bit
length; one -way hash function H

Output:
-------
𝑥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).