If you set your DNS TTL to a relatively-low 1 minute (as in the POC), that's 31.9 years for an exhaustive search.

The birthday paradox means that you're probably going to spend a lot less time than that, but it's certainly going to buy me a lot longer than 1 minute that I get if I'm using 127.0.0.1. The chances I stay on any random website longer than 15 minutes are pretty slim, and you've got really poor odds of finding the right IP in that time.

I don't see how the birthday paradox applies. If you pick a random IP under 127.0.0.0/8, then on average a website searching will take 1/2 of time required to check every IP sequentially.

cbr is correct; the birthday paradox refers to trying to find two random values that are equal to each other, with no other constraint on their value (so (3,3) and (78,78) are both valid solutions). What we have here is trying to find one value that is constrained (if 3 is a solution, 78 can't be). Assuming you enumerate IP addresses in random order, the expectation will be 16 years to find the one you want.

Ahhh, thank you for explaining that distinction much better than Wikipedia (maybe you ought to add this tidbit :-) ). I'd been assuming it applied to any probability of collision in a fixed space.

I guess I'll elaborate by distinguishing these types of problem:

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

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.

> If you set your DNS TTL to a relatively-low 1 minute (as in the POC), that's 31.9 years for an exhaustive search.

Right, but that assumes a new DNS record is created each time. An attacker might simply have records for the entire 127.0.0.0/8 range and would iterate over them.

It would still take a long time to make an exhaustive search, but it will be faster than waiting for a 1 minute TTL between each try.