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

I'm going to try again.

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.

If you say so.

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

You are mixing apples and oranges. The first scenario, unmodified
DNScache, requires a birthday attack which we can analyze. The second
scenario Kaminksy/Day/King DNScache changes, depends on changes
suggested by a blackhat hacker and lowers the randomness of the port
usage.  Imagine a popcorn popper that runs a lot slower. Slow enough to
follow.

Also, Kaminsky (and presumably Day) are reasonably skilled programmers,
and the changes aren't very big; and DNScache isn't very complicated.
Getting King to implement the changes and dropping Kaminsky and Day's
involvement is also kind of like laundering the blackhat taint using
Jeff King's non-blackhat reputation.

My solution keeps the randomness high (keeps the popcorn popper going
full steam), and avoids the poison altogether by falling back to TCP
when an attack is detected. Falling back to TCP when an attack is
detected isn't nearly as much DNS TCP traffic as using TCP all the time.  
Are you opposed to this solution? If so, why?


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

I see a lot of net people talking with this term. I see no scientific
papers that use it.  It seems to be a big, scientific-sounding word
meaning 'a chain is no stronger than its weakest link'. So, yes, I guess
I know about that.

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

No, the above isn't true in any non-trivial sense.  One can obviously
attempt any attack at any time (the trivial sense).  But the chance of
success of any given attack depends on the changes made to DNScache.  
For example, if you change it so to bind the port to 53, the chances of
a brute force attack change to 1 in 65536. Doh.

So we need to consider out three cases. In the unmodified case, the
easiest attack is the birthday attack.  The math is well understood.  
In the Kaminsky/Day/King modified case, there might be an easier attack
based on the lowered randomness of port numbers.

In the case of my proposal, the easiest attack should still be the
birthday attack; I don't alter anything that might affect entropy.  And
the Birthday attack is made harder to carry out in practice by detecting
it and falling back to invulnerable TCP, without the burden of using TCP
all the time. Best of all possible worlds.


BTW, I don't pretend to be a real crypto expert. Some elaboration is
needed here. Previously, when I've said I'm not an expert on a subject,
idiots and the ignorant get very excited.  When someone says they aren't
a professional expert in a subject, it doesn't mean they aren't
knowledgeable. It means that I'm not on the same league as say DJB, or
probably any of the authors of the crypto papers I read. But I do know a
fair amount of math, and I do read as widely as I can, and I have a
nearly photographic memory. Today, for example, I remembered the UPS
tracking number from the slip, after I left the slip home. I've usually
been right when reporting what I read, and I try always to give sources
of important facts.  I also apply what I read. For example, some years
ago I discovered that Information Theory shows that spam cannot be
stopped by any technical means, but is always a whackamole operation
(I'll spare you the details). Usually these abilities are regarded as an
asset, but sometimes they have been the great chagrin of, e.g the BIND
Cartel, particularly those who are trying to pull something that can be
spotted as BS if one merely remembers some facts.

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