So then, presumably, even with this solution the attacker has birthday attack advantage for:
a) attacking multiple targets all using independent random IPs for their services
b) Users running multiple services, each on a separate random loopback IP
And if I'm correct there, then this would presumably extend to generic DNS rebinding attacks; the greater the number of IPs in a subnet, the greater the birthday attack advantage the attacker gains. (right?)
Your (a) is my example (2), where the dice are the IPs used by the multiple targets and the value 3 is the IP address you test for. It's still not a birthday attack, but it is helpful to the attacker, assuming the goal is "one compromise on any target, I don't care which". (In terms of the formula I gave as the solution to (2), if you make g guesses to attack t targets, your chance of success on at least one target is [1 - ([n-g]/n)^t].) In example (2) itself, there was 1 guess, 3, and 100 targets, the dice.
Your (b) is similar, but even more helpful to the attacker in that the loopback IPs are constrained not to overlap with each other, which makes searching for "any hit, I don't care which" easier.
It's a birthday attack if you generate a lot of values and hope for two of those values -- all of which you generated -- to be equal to each other. If you're generating values and hoping for one of those values to be equal to some externally-defined value, it's not a birthday attack, it's a guessing attack.
1. I roll 1 die. What are the odds of getting a 3? (Assuming the die is evenly distributed 1-n, and n >= 3, the answer is 1/n )
2. I roll 100 dice. What are the odds of getting, among those dice, at least one result of 3? ( 1 - [(n-1)/n]^100 )
3. I roll 2 dice. What are the odds of those dice matching each other? ( 1/n )
4. I roll 100 dice. What are the odds of there being, among those 100 dice, any 2 dice that rolled the same result?
The birthday paradox provides the answer to problems of type (4).