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′)?