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).