Regarding hash collisions, an attacker only has to do half of the work to find a collision when they can control both messages compared to when they are trying to find a weak collision. This can be explained with the birthday paradox.
I understand the birthday paradox, but can't quite see how it relates fully to strong collisions and why it shows they only take half the work of weak collisions. With the birthday paradox, each person already knows their own birthday in advance, so when the first person 'says' their birthday, everyone else can compare that with their own, and so on and so on.
If an attacker is trying to find two message that hash to the same value, the hashes of the newly modified messages aren't already known (unlike people's birthdays), so wouldn't an attacker have to create a load of hashes for one of the messages, store them, and then do the same for the other message and start comparing, how is this quicker than finding a weak collision?
My question is, how would an attacker try and find two messages that hash to the same value, so that it only takes half the work as if they were trying to find a weak collision?