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

On Thu, 12 Feb 2009, Jeff King wrote:

> On Thu, Feb 12, 2009 at 01:02:42AM -0500, Dean Anderson wrote:
> 
> > Actually, one of the first problems I see is that your patch
> > discards repeated queries from multiple hosts that ask the same
> > question.  You
> 
> No, it doesn't. Each incoming query still gets a slot in udplient (or
> tcpclient). When an outgoing query is made on behalf of a slot, we
> avoid sending out a packet if there is already an identical query
> outstanding; When the answer comes back, _all_ slots get the answer
> and proceed with their resolution.

Ok. I see that.

> > What I'm also concerned about, is that your change may fix a problem
> > that an attacker may have. Day describes the oldest queries being
> > dropped. The effect this has is to restart the birthday attack
> > before the required packets have been received, or rather reduce the
> > number of urns, mid-attack. That makes it harder for the single
> > birthday attack to succeed. Reducing the number of ports in MAXUDP
> > increases the number of packets necessary to spoof dnscache.  If
> > queries come in, and knock out attacker's queries, this is the same
> > (very nearly) as reducing the size of MAXUDP. Kind of like
> > accidentally hitting the reset button...
> 
> One, my understanding is that the attacker in Kevin's test setup can
> actually do the timing to keep MAXUDP filled properly, and this was
> done experimentally. So while such a change might make it easier for
> an attacker, it is already something an attacker can deal with. But I
> don't know the details, so maybe he can comment more.

I'd like to see the exploit code. Working on an unloaded server for an
experiment and working on a loaded server are far different tasks.


> There is one difference: a query we sent on behalf of an older client
> that has been expired will still be "valid" to receive an answer, if
> and only if there is still another client interested in that answer.

Under no load, that's true. But there is no change to u_new, so the
oldest query will still get removed as new queries come in and there are
more than 200 outstanding queries.

> So now a stupid attacker who is overflowing MAXUDP won't accidentally
> push out that window of opportunity (instead, it will close when the
> actual response comes from the server and is cached). But balance that
> against the fact that there is only _one_ window of opportunity,
> instead of MAXUDP windows.

One window could indeed mean that it takes a smaller number of packets
to spoof. BIND previously had just one window.

This appears to increase the vulnerability, particularly if the UDP
ports can be predicted because they don't change as often. In that case,
the attack is reduced to number of probable UDP ports * 64k packets to
run though the QIDs.

Allowing multiple queries with unique QIDs means one _must_ conduct a
birthday attack, and also means that the udp ports change more
frequently, making them harder to predict.  We know that 28 million
packets are required under the birthday attack against the current code.

I think your patch weakens DNScache to attacks based UDP port
prediction.  Your work is good, and your code is respectable, but it
just isn't based on cryptographically sound analysis.  There is no
question that all of us were duped.

I am still quite concerned that the so-called 'vulnerabilities' didn't
exist. This after 8 months of pretending that they did exist, and
pretending the exploit was SO IMPORTANT and SO DEVASTATING that they
_couldn't_ share details their discovery with developers of DJBDNS
publicly.  We know now that was just BS.

There is no exploit other than the Birthday attack, which we know about,
and have known about for months, if DJB didn't already know about this
beforehand.


> > At 200 MAXUDP, it takes 28 million packets to spoof dnscache. You'd
> > notice that, so changing DNScache doesn't appear to be necessary.
> 
> I think Kevin's number was 16 million, but the same order of
> magnitude.

An important point was that Kevin's formula for Birthday attack was
wrong, as was their whole mathematical analysis.  But is it also the
case that they never forwarded to anything explaining the combination
birthday attacks?  That seems passing strange, as the basic structures
you created are necessary for the reuse of QIDs that results in the
combined birthday attack. I don't feel very comfortable with blackhat
hackers who are keeping things 'close to the chest', so to speak.  
Whitehat hackers post an exploit, and explain what they did; Whitehats
don't ask for dubious, unexplained changes using incorrect mathematical
models.

> > So far, I haven't seen anything in any of these changes that makes
> > DNScache stronger, nor anything that fixes a weakness.
> 
> That's because you have already written off the weakness as "you would
> notice that [many packets coming in]." Maybe some installations would.
> If yours does, then using these patches probably doesn't make sense,
> since you have other defenses for the same attacks.

Everyone can detect 28 million packets with same DNS response.  IDS
systems can detect far, far smaller attacks, and automatically take
action.

What it has come down to is whether your patches cause more harm, not
whether they fix an exploit.  There was no exploit on DJBDNS. We were
all misled and boondoggled. Me, too.


		--Dean

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