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

Thanks Paul for reviewing the math. I was going to but that was a lot to do.
I think it is also worth saying that a standard approximation for (1 + i) ** n
is 1 + ni  when both n an i are small.
This is in effect what he was using and why some of the numbers are so close.


On 3/11/10, Paul Jarc <[email protected]> wrote:
> 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
>