Re: 2 forwarded messages...DNSEXT discussion of Day and Kaminsky

On Fri, 13 Feb 2009, Matthew Dempsky wrote:

> On Fri, Feb 13, 2009 at 12:54 AM, Dean Anderson <[email protected]> wrote:
> > You simply didn't follow the math of a birthday attack with 200 ports
> > out of 65k.
> 
> Sorry, I followed the math fine.
> 
> > Each port of 200 used has a unique QID. The attacker has to
> > get BOTH the port AND the QID correct.
> 
> Right.  But in this scenario, a single forged response packet has
> potentially 200 chances of success (because it might match any
> port/qid pair).  With the qmerge patches applied, a single forged
> response packet can never match more than one outstanding query.

No, that's not right.  You didn't follow the math of a birthday attack.

> > With exactly one port, that port might be
> > predictable, or they might be able to find it easilly with a quick scan
> > for open/closed ports.
> 
> You keep alluding to your knowledge of cryptography.  You understand
> security reduction proofs, right?
> 
> So you understand that if an attacker can carry out an attack against
> dnscache with a single outstanding UDP query, then he can apply the
> same technique when dnscache has 200 outstanding UDP queries and have
> the same (or better) chance of success, right?  I.e., you understand
> that any attack that an attacker can carry out with the qmerge patches
> applied, he can still carry out without it applied, right?

Again, you have the math incorrect. The 200 outstanding queries each 
have a unique QID.  Therefore, the attacker must conduct a birthday 
attack, trying to mache a correct port with a correct QID.

The CRC handbook of Applied Cryptography gives the formulas needed in
section 2.1.5, Birthday problems. On a regular unix system, the first
1025 ports usually won't be assigned to a socket, leaving 64510 ports
available for use.  The math for the first case:

model B (2 urns, no replacement)
p4(64510, 200, 200)
exact formula: 1 - (perm(m, n1+n2) / (perm(m, n1) * perm(m, n2))
   simplified (n1 = n2): 1 - (perm(m, 2n) / (perm(m,n) ^ 2))
(%i48)  float( 1 - ( 64510! / ( 64510 - 400)! ) / ( ( 64510! / ( 64510 - 
200)! ) ^ 2 ) );
(%o48)                         0.46312147260386
(%i49) % * (1/65536);
(%o49)                       7.066672860776713E-6
(%i50) 1 / %;
(%o50)                         141509.3099258154
(%i51) 200 * %;
(%o51)                       2.830186198516307E+7


So, as is, one must repeat 141509 times before success, expect to send
28,301,862 packets against DJBDNS.  


If you have p4(64510,1,1) more packets are indeed required, but in that
case, one can then carry out a __different__ attack on a single port
with its single QID, and you don't need to conduct a birthday attack.


> Here's a homework assignment for you if you still think the qmerge
> patches are bad: describe an attack that has a better chance of
> success when the qmerge patch is applied than when it is not.
> "Success" means dnscache accepts the forged response packet and
> processes it as though it were legitimate.

I did. If one can find the one port that is being used, or predict it,
or constrain it. I looked at socket_bind, and while it tries to find a
random port as David Nichol points out, it is not guarenteed to _get_ a
random port because the operating system can only have 64510 ports above
1025 and those can be used by other things. Further, randombind tries 10
times to get a random port, after which it picks the OS assigned port.  
It should be kinda sorta pretty random, but it isn't guarenteed to
actually be random.

> In fact, I'll offer $100 to anyone who can describe such an attack.
> (This offer only covers attacks against the idea of the qmerge patch;
> i.e., modifying dnscache to merge duplicate outbound queries.  I
> haven't yet thoroughly read the patch to look for implementation bugs,
> so this offer doesn't cover those; once I've had a chance to, however,
> I may extend the offer.)

Attack described above.  You can send the $100 to 
Dean Anderson
P.O. Box 7286
Nashua, NH 03060


With this new found wealth, I'll offer $300 to anyone who can provide an
working (not-MiTM) exploit of DNScache as is, that works in less than 28
million packets.


My strategy of looking for a poisoning attack by counting similar
queries and quickly falling back to TCP in that case is a much better
strategy than just merging queries and hoping for randomness in the port
number.  My strategy makes a poisoning exploit closer to impossible to
conduct in practice (except by MiTM, of course).  The Kaminsky strategy
can't make the same claim.

I'll give you $300 and a picture of me eating my hat if anyone can
produce an exploit of my detect&fallback-to-TCP strategy, that isn't
MiTM.


		--Dean


-- 
Av8 Internet   Prepared to pay a premium for better service?
www.av8.net         faster, more reliable, better service
617 344 9000