Re: Dishonest Forks? | Was - Re: [Namedroppers-honest] Brian Smith asks: Who is Dean Anderson?

Kevin <[email protected]> wrote:
> What you are describing is the scenario where you wait for someone
> to happen to look up the name you want to try to poison. This isn't
> at all what we're discussing.

This is definitely a critical point.

> The attacker has a 100ms window, which allows him to send 1000 spoofed
> packets. He has 3 possible combinations of port number and query ID to
> try to collide with.  The odds of any packet successfully colliding
> is: 3/(65536*65536) or 0.000000000698492.

Good so far...

> He has 100ms to send 1000 packets though, so his probability of
> exploitation is 0.000000698491931.

Numerically, that's very close, but you're using the wrong
calculation.

With 1000 forged answers, the probability of at least one of those
1000 being successful against one outgoing query is not
1000*(probability of 1 forged answer succeeding).  Using ** for
exponentiation, it should be:
  1-(probability of all 1000 failing)
= 1-(probability of 1 forged answer failing)**1000
= 1-(1-probability of 1 forged answer succeeding)**1000
= 1-(1-3*2**-32)**1000
= 6.98491687260119776e-07
1 in ~1,431,656.

Even that probably still isn't right, because it assumes that the 1000
forgeries are generated independently, with possible duplicates among
them.  If the attacker ensures that each forgery is distinct, then the
probability of success is somewhat larger.  The calculation also gets
quite a bit more complicated at that point, as Dean said.

> Or roughly 1 in 1,431,655 for any of his packets to
> collide with the 3 open queries before the real result gets there.

Like I said, very close. :)  The difference between the two
calculations would grow with a larger number of outgoing queries, or a
larger number of forged answers.

If the attacker needs to hit all three, then again the calculation
gets complicated, but obviously the chance of success is much smaller.

> Assuming at least a 6 hour TTL between tries, it will take 490 years
> to have a 50% chance of success at poisoning any one of the records
> once.

Here again I think you've got the wrong calculation.  Now the correct
answer is significantly different, but still on the same order of
magnitude.  For N independent attempts, the probability of any one of
them succeeding is:
  1-(probability of all N attempts failing)
= 1-(probability of 1 attempt failing)**N
= 1-((1-3*2**-32)**1000)**N
If that's 0.5, then:
    1-((1-3*2**-32)**1000)**N  =     0.5
     -((1-3*2**-32)**1000)**N  =    -0.5
      ((1-3*2**-32)**1000)**N  =     0.5
  log(((1-3*2**-32)**1000)**N) = log(0.5)
N*log(((1-3*2**-32)**1000)   ) = log(0.5)
N = log(0.5)/log(((1-3*2**-32)**1000))
N = ~992348 attempts to get a 50% probability of success.
N * 6(hours) / (24(hours/day) * 365.2425 (days/year)) = 679 years.

> The odds of any packet successfully colliding
> is: 1/(65536*65536) or 0.000000000232831. He has 100ms to send 1000
> packets though, so his probability of exploitation is
> 0.000000232830644. Or roughly 1 in 4,294,967 for any of his packets to
> collide with the open query before the real result gets there.

Again, the correct calculation gives nearly the same answer (####):
  1-(probability of all 1000 failing)
= 1-(probability of 1 forged answer failing)**1000
= 1-(1-probability of 1 forged answer succeeding)**1000
= 1-(1-2**-32)**1000
= 2.3283061656442783e-07
1 in ~4,294,968.

> Assuming at least a 6 hour TTL between tries, it will take 1470 years
> to have a 50% chance of success at poisoning any one of the records
> once.

log(0.5)/log((1-2**-32)**1000)*6/(24*365.2425) = 2038 years

> If the attacker does succeed, all three of the services will have
> received the wrong answer, but the odds of doing so are 3x less
> likely.

Just about.
log((1-3*2**-32)**1000)/log((1-2**-32)**1000) = 3.00000000069850857

> Each spoofed packet has a 200/(65536*65536) chance of colliding with
> any of the open queries, or 1 in 21474836.
> After 100ms, the real replies to 00001.facebook.com arrives at the
> victim, closing those queries. During the 100ms, the attacker got off
> 1000 packets, so his odds of poisoning were 1000 in 21474836 or 1 in
> 21474.

  1-(probability of all 1000 failing)
= 1-(probability of 1 failing)**1000
= 1-(1-probability of 1 succeeding)**1000
= 1-(1-200*2**-32)**1000
= 4.65650456295816414e-05
1 in ~21475.

This is a much higher probability of success, which is why this is the
attack that attackers actually use.  The number of attempts required
for a 50% chance of success:
1-((1-200*2**-32)**1000)**N = 0.5
N = log(0.5)/log(((1-200*2**-32)**1000)) = ~14885

> 10000 attempts per second

~1.4885 seconds for 50% chance of success.  But that's with 10,000
attempts per second, where each attempt uses 1,000 forged answers, so
10,000,000 forged answers per second--is that realistic?  Anyway, the
math is easy at this point--the number of attempts is fixed, so if the
attack rate is slower, then the amount of time just grows linearly.

> After 100ms, the real replies to 00001.facebook.com arrives at the
> victim, closing those queries. During the 100ms, the attacker got off
> 1000 packets, so his odds of poisoning were 1000 in 4294967296 or 1 in
> 4294967.

See above (####).

> 10000 attempts per second gives him odds of 1:429496 in the first
> second. A 50% chance of success requires 59 hours of attacking.

1-((1-2**-32)**1000)**N = 0.5
N = log(0.5)/log(((1-2**-32)**1000)) = ~2,977,044 attempts
~297.7044 seconds for 50% chance of success.

With the patch, it takes 200.000004633330226 times as many attempts to
succeed.  With more than 1000 forgeries per attempt, the ratio rises.
If we were using the even more complicated calculations, for when the
attacker ensures that all 1000 forgeries are distinct, that would also
make a difference.


paul