Assume that a one-way Hash function is secure and the best way to attack it is by using the brute force attack. It produces an $m$-bit output. Finding a message that hashes to a given hash value would require hashing $2^m$ random messages. Finding two messages that hash to the same value would only require hashing $2^{\frac{m}{2}}$ random messages.
I know only about birthday paradox involving 23 people. How do I relate the birthday paradox with this attack?
$2^m$ requirement is for the pre-image attack. You have to hash approximately $2^m$ messages to find the message that has the same value you were looking for if the hash function has pre-image resistance.
In a collision attack, you are looking for two messages that have the same hash value.
If you look at Wikipedia Birthday Paradox at section Cast as a collision problem, it is also generalized for the arbitrary number of days not just for 365 days. The approximation is given by
$$n \approx \sqrt{2^m}$$ and we call it generic birthday attack.
Note that: if you find an attack which is faster than generic birthday attack like SHA-1 attack you will be famous.
