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

Yes, sorry for not mentioning that. I had about 10 minutes to type all of that before I had to leave, so I was being a bit vague. If you really want to nitpick, it should be (65536*64512) not (65536*65536) since dnscache doesn't use the bottom 1024 ports. I also wasn't taking into account there failures of guessing how long the window stays open, etc. If you want the "real math" look at the paper, I just didn't want to have the longer formulas distract from the "simple" explanation of the technique and the approximate timeframes.

-- Kevin

On Mar 11, 2010, at 12:08 PM, Simon Casady wrote:

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