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

You simply didn't follow the math of a birthday attack with 200 ports
out of 65k. Each port of 200 used has a unique QID. The attacker has to
get BOTH the port AND the QID correct.  The math on Birthday attack is
well documented, and is explained in the messages I sent to DNSEXT,
along with the references (CRC Handbook on Applied Cryptography), that
gives the proper formulas.  It is extremely important to do the math
correctly and not depend on intuition. Your analysis below is wrong.

Once you actually do the math, and consider the two different attacks,
you'll see that I'm right.  With 200 ports and 200 unique QIDs, a
birthday attack the best chance, and we know exactly how hard that is:  
28 million packets. 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. And we know exactly how hard that is (65k
packets)

Jeff: What I suggest is that you reuse some of the qmerge code to detect
an attack in progress and then change the affected queries to TCP
fallback, expiring the UDP queries and removing any results from the
cache.  So, instead of merging, just count the number of identical
queries. Any number over some threshold, say 75, indicates an attack in
progress.  

		--Dean

On Thu, 12 Feb 2009, Matthew Dempsky wrote:

> On Thu, Feb 12, 2009 at 1:27 PM, Dean Anderson <[email protected]> wrote:
> > I think your patch weakens DNScache to attacks based UDP port
> > prediction.
> 
> Sorry, I think you're nuts.
> 
> Stock dnscache from djbdns-1.05 can have 200+ outstanding UDP queries.
>  To forge a response to one of these queries, an attacker has to guess
> the port, qid, type, and name; port and qid are cryptographically
> randomly generated 16-bit numbers and type/name are attacker
> controlled.  With stock dnscache, potentially all of the 200+ queries
> might have the same type/name.  An attacker can then send a forged
> response packet with a given type/name and random port/qid and it
> succeeds if it matches any 1 of the 200+ outstanding UDP queries,
> giving him a 200x improvement in odds to forge a response packet.
> 
> However, if dnscache has been patched with the qmerge patch, then
> every outstanding packet has a unique type/name, so every forged
> packet an attacker sends can match at most one outstanding UDP query.
> 
> I'll weigh in that I'm not a big fan of how the qmerge patch is
> implemented, and I don't think most dnscache deployments are
> vulnerable to this attack (ISPs being the main exception), but as far
> as I can tell it does seem to address this issue, and I don't think
> your arguments about reducing security hold any water.
> 
> 

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