Subject: Why *can* cached DNS replies be overwritten?

From: "Jay R. Ashworth" <[email-masked]>
Date: Mon, 11 Aug 2008 15:04:27 -0400

[ cross-posted from NANOG, cause vix told me to :-)

On Mon, Aug 11, 2008 at 11:20:07AM -0400, Leo Bicknell wrote:
> If your vendor told you that you are not at risk they are wrong,
> and need to go re-read the Kaminski paper.  EVERYONE is vunerable,
> the only question is if the attack takes 1 second, 1 minute, 1 hour
> or 1 day.  While possibly interesting for short term problem
> management none of those are long term fixes.  I'm not sure your
> customers care when .COM is poisoned if it took the attacker 1
> second or 1 day.

Correct me if I'm wrong, Leo, but your assertion turns on the fact that
the server will accept an overwriting cache entry for something it
already has cacheed, does it not?

Do djb and Power in fact do that?

If they don't, the window of opportunity to poison something like .com
is limited to the period between when that entry expires from the local
server's cache and the next time it hears a reply -- which will be the
time after that expiry when someone next requests a .com name; IE
almost immediately, no?

Everyone seems to continue asking "why can poisoning overwrite already
cached answer" and no one seems to be answering, and, unless I'm a
moron (which is not impossible), that's the crux of this issue.

Cheers,
-- jra
-- 
Jay R. Ashworth                   Baylink                      [email-masked]
Designer                     The Things I Think                       RFC 2100
Ashworth & Associates     http://baylink.pitas.com                     '87 e24
St Petersburg FL USA      http://photo.imageinc.us             +1 727 647 1274

	     Those who cast the vote decide nothing.
	     Those who count the vote decide everything.
	       -- (Josef Stalin)

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: bert hubert <[email-masked]>
Date: Mon, 11 Aug 2008 22:09:50 +0200

> Do djb and Power in fact do that?

Yes - PowerDNS does that because of reasons which used to be persuasive. It
is in fact probably possible to ignore such updates.

Costs are that (nameserver) changes get picked up later. 

I'll try this in PowerDNS on the several billion test queries and answers we
have to see if this breaks things.

> moron (which is not impossible), that's the crux of this issue.

It feels odd to deviate from 25 years of DNS practice. This may be one
reason why people find it hard to try such things.

Thanks for persistenly asking about this.

It may be something that is not theoretically allowed, but that practically
helps us out of the woods.

Will report results of the tests here.

	Bert

-- 
http://www.PowerDNS.com      Open source, database driven DNS Software 
http://netherlabs.nl              Open and Closed source services

---

From: Olafur Gudmundsson <[email-masked]>
Date: Mon, 11 Aug 2008 20:32:48 -0400

>moron (which is not impossible), that's the crux of this issue.

<no-hat>
The cynical answer is "optimization" the real answer is
"trying to be helpful".

What most/all implementations are doing is assuming that "newer" data
is better if it has the same criticality [RFC2181], this takes two forms:
if the data is identical to the existing one, the TTL on the set is extended.
If the data is different the old data is replaced.

Personally I think we need to sit down and analyze this carefully if
we are better of by outlawing/discouraging this behavior and have all
RRsets expire after the original TTL expires or do something else.

One proposal is to use the "Authority Section data for the question 
being asked" and then ask a direct query to fetch the data inserted into the
Authority section data and overwrite that with the data from Answer
section which should have higher criticality than the stuff from Authority
Section and this should prevent overwrites. (This is strictly/almost
a protocol change)

The effect of not overwriting/stretching TTL on RRsets is that
an  attacker can only poison the set of their choice once in a
while (depends on the RRset TTL and the cache's memory constraints).

<char-hat=on>
What the overall effect is going to be if caches changed this
behavior is debatable but conducting few experiments would be real
useful. Both in seeing if anything in resolution break as well as
see if this helps prevent acceptance of forgeries.

At the same time the WG should look into other approaches in this and
related spaces.

         Comments
         Olafur

---

From: "Antoin Verschuren" <[email-masked]>
Date: Tue, 12 Aug 2008 10:31:21 +0200

> -----Original Message-----
> From: [email-masked] [mailto:owner-
> Subject: Why *can* cached DNS replies be overwritten?
> 

I did some investigation after my post of http://lists.oarci.net/pipermail/dns-operations/2008-February/002526.html
I did not test this myself, but what people have told me is:

Dnscache, powerdns: Updates the cache by resetting the TTL if a new authoritative answer for the same entry is received.

Bind: Updates the cache, but only replaces the TTL with the min value

Unbound: Never updates, always waits for an entry to expire before accepting a new entry

> moron (which is not impossible), that's the crux of this issue.

I actually like the simple behavior that an authoritative answer can override an already cached answer.
It's efficient, and follows the simple rule that an authorative answer can be cached.
It only goes wrong if people don't maintain their DNS entries operationally, and forget to delete entries they are no longer authoritative for.
So the bad guys get hit.
The benefit for the good guys is that less lookups are needed, and more importantly, parents are hit less.
In the DNS hierarchy, you don't want every query to hit the root.
My concern is that if records always expire, like Unbound does, parent nameservers are hit more.

Now we can start an argument on the fact that traffic has become inexpensive, and root and TLD nameservers should be able to cope with this minimal increase in queries, but I think we should define a protocol to be as efficient as it can be.
I actually don't know how parent traffic will be affected, I'm interested to see measurements on that.
But I stay with the thought that even though we only win some bits in traffic, we should always aim to design a protocol to do so.

I also think we must not create protocol complexity to protect ignorant users from making mistakes when that does not benefit educated users.

And then there's the argument that when cached entries cannot be replaced, an attacker can make use of that.
"fixing" a bad cache entry remotely by sending the correct authoritative answer might reduce the time window a poisoned cache is operational.

Antoin Verschuren

Technical Policy Advisor
SIDN
Utrechtseweg 310
PO Box 5022
6802 EA Arnhem
The Netherlands

T +31 26 3525500
F +31 26 3525505
M +31 6 23368970
E [email-masked]
W http://www.sidn.nl/

---

From: Peter Koch <[email-masked]>
Date: Tue, 12 Aug 2008 14:09:23 +0200

> It's efficient, and follows the simple rule that an authorative answer can be cached.

well, I had read your earlier comments slightly differently, especially
w.r.t. the "name server lock-in" problem.

> It only goes wrong if people don't maintain their DNS entries operationally, and forget to delete entries they are no longer authoritative for.

... or aren't informed or don't cooperate for other reasons. We know how to
gracefully migrate from one NS RRSet do another, even disjoint, one,
but we also know that this migration doesn't really happen that often
in today's mass hosting environments.  But can catch two birds with one
stone here, I believe:

Let's see what different flavors the forged responses can have:

-----------------------------------------------------------------------------
;; QUESTION SECTION:
;345678.example.org.		IN	A

;; ANSWER SECTION:
345678.example.org.        3600	IN	A	192.0.2.1

;; AUTHORITY SECTION:
example.org.               3600	IN	NS      ns1.example.org.
example.org.               3600	IN	NS	ns2.example.net.

;; ADDITIONAL SECTION:
ns1.example.org.           3600	IN	A	10.0.0.42
www.example.org.           3600	IN	A	192.0.2.80
-----------------------------------------------------------------------------

Unsolicited additional information should already be ignored and data
from the additional section shouldn't overwrite a (previous) authoritative
answer as per RFC 2181. 0 points.

-----------------------------------------------------------------------------
;; QUESTION SECTION:
;345678.example.org.		IN	A

;; ANSWER SECTION:
345678.example.org.        3600	IN	A	192.0.2.1

;; AUTHORITY SECTION:
example.org.               3600	IN	NS      www.example.org.
example.org.               3600	IN	NS	ns2.example.net.

;; ADDITIONAL SECTION:
www.example.org.           3600	IN	A	192.0.2.80
-----------------------------------------------------------------------------

The additional section data is logically justified, but RFC 2181 helps.
0 points.

-----------------------------------------------------------------------------
;; QUESTION SECTION:
;345678.example.org.		IN	A

;; ANSWER SECTION:
345678.example.org.        3600	IN	A	192.0.2.1

;; AUTHORITY SECTION:
example.org.               3600	IN	NS      evil1.example.net.
example.org.               3600	IN	NS      evil2.example.net.
-----------------------------------------------------------------------------

Now, to have gotten here, the resolver has already followed a referral.
In theory, the referral and the authoritative data are always in sync,
so there's no need to replace one with the other. In practice, though,
the authoritative NS RRSet is the more credible one.
Distinguish between a referral NS RRSet and an "authoritative" NS RRSet
(quotes because it stems from the authoritative source, but isn't
formally covered by the AA bit):  let the latter _only_ overwrite the
former.  This brings back the window of opportunity whose size is
determined by the TTL of the "authoritative" NS RRSet.

However, there's a remaining risk here at those levels where a positive
authoritative response does not normally occur under normal operations,
most prominently most of the TLDs.

-----------------------------------------------------------------------------
;; QUESTION SECTION:
;345678.example.org.		IN	A

;; ANSWER SECTION:
345678.example.org.        3600	IN	A	192.0.2.1

;; AUTHORITY SECTION:
example.org.               3600	IN	NS      345678.example.org.
-----------------------------------------------------------------------------

Same as above. It's the NS RRSet, not the address data.

> My concern is that if records always expire, like Unbound does, parent nameservers are hit more.

Sure, but this is hard to predict. It depends on the relation of TTLs
between both NS RRSets as well as the TTLs of the authoritative NS RRSet
and the TTL of the data you're actually interested in.

But, isn't the phantom referral the really hard one:
-----------------------------------------------------------------------------
;; QUESTION SECTION:
;345678.www.example.org.		IN	A

;; AUTHORITY SECTION:
www.example.org.           3600	IN	NS      evil1.example.net.
www.example.org.           3600	IN	NS      evil2.example.net.
-----------------------------------------------------------------------------

What are mitigation techniques here?

o let the resolver remember the (potentially invisible) zone cut
o expire all RRSets atthe same owner at once (bad effect on the parent)
o really delegate at every level (have fun with IP6.ARPA and ENUM)
o ...

-Peter

---

From: Tony Finch <[email-masked]>
Date: Tue, 12 Aug 2008 14:38:22 +0100

> Let's see what different flavors the forged responses can have:

Now about

;; QUESTION SECTION:

;; ANSWER SECTION:
345678.example.org.	3600	IN	CNAME	www.example.org.
www.example.org.	3600	IN	A	192.0.2.80	; evil

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
SOUTHEAST ICELAND: NORTHEASTERLY 5 TO 7, OCCASIONALLY GALE 8. ROUGH OR VERY
ROUGH. OCCASIONAL RAIN. MODERATE OR GOOD.

---

From: Florian Weimer <[email-masked]>
Date: Tue, 12 Aug 2008 18:55:02 +0200

>> Let's see what different flavors the forged responses can have:

Thanks for posting this summary.

> www.example.org.	3600	IN	A	192.0.2.80	; evil

IIRC, it has been argued that the AA bit only applies to the top-most
CNAME (or the record whose name matches the QNAME, forgot whih).
Based on that, RFC 2181 rules would prevent a cache override.

There are a few more things.  First, using RCODE=3 to clear the cache:

| ;; ->>HEADER<<- opcode: QUERY, status: NXDOMAIN, id: 39020
| 
| ;; QUESTION SECTION:
| ;www.example.org.		IN	TYPE1337 ; varies
 
followed by:
 
| ;; QUESTION SECTION:
| ;www.example.org.               IN      A
| 
| ;; ANSWER SECTION:
| www.example.org.      3600    IN      A       192.0.2.80      ; evil

>From a statistical point of view, this is less interesting because it
requires spoofing in quick succession.  It doesn't work against all
implementations, either.  I don't think it's covered by RFC 2181.

The other approach is:

| ;; QUESTION SECTION:
| ;www.example.org.               IN      TYPE1337 ; varies
| 
| ;; ANSWER SECTION:
| www.example.org.      3600    IN      CNAME evil.example.net.

Again, the effectiveness of this trick depends heavily on the cache
implementation.  Some might have a RTYPE-specific CNAME cache, some
might throw away the existing A record once they encounter the CNAME,
some may prefer the existing record, until it expires from the cache,
when they start using the CNAME.  (The wording I suggested for the
DNAME draft assumes that the CNAME caching rules are updated to
address this.)

I think the following has already been mentioned?

| ;; QUESTION SECTION:
| ;235223.example.org.               IN      MX
| 
| ;; ANSWER SECTION:
| 235223.example.org.      3600    IN      MX 10   www.example.org.
|
| ;; ADDITIONAL SECTION:
| www.example.org.         3600    IN      A  192.0.2.80 ; evil

Again, RFC 2181 should cover this.  Anything else with additional
section processing is affected in a similar way (and should be treated
similarly).

-- 
Florian Weimer                <[email-masked]>
BFK edv-consulting GmbH       http://www.bfk.de/
Kriegsstraße 100              tel: +49-721-96201-1
D-76133 Karlsruhe             fax: +49-721-96201-99

---

From: Paul Vixie <[email-masked]>
Date: Tue, 12 Aug 2008 17:08:15 +0000

nonreplacement of rrsets is not a general fix.  there are plenty of kaminsky
message patterns that rely only on insertion of new data.  so while i'm having
great fun with just reducing the TTL when a replacement is attempted, 
especially with NS RRsets, it doesn't make me safe.

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

---

From: Peter Koch <[email-masked]>
Date: Tue, 12 Aug 2008 19:10:24 +0200

> Now about

not NS RRSet based, but still ...

> www.example.org.	3600	IN	A	192.0.2.80	; evil

Can be mitigated two ways:

1) do not believe anything after the (first) CNAME RR (DNAME with CNAME
   synthesis needs special consideration)

2) again, do not overwrite anything in the cache, unless the new
   response is _more_ credible (as opposed to "greater or equal")

-Peter

---

From: Tony Finch <[email-masked]>
Date: Wed, 13 Aug 2008 12:02:13 +0100

What if you ask for a subdomain of your target and spoof a referral saying
the target name is a zone cut? This doesn't directly overwrite the cache,
but when the cached record for www.example.org expires the attacker's
nameserver will be asked for an update.

;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 1234
;; flags: qr rd; QUERY: 1, ANSWER: 0, AUTHORITY: 1, ADDITIONAL: 1

;; QUESTION SECTION:

;; AUTHORITY SECTION:
www.example.org.	86400	IN	NS	evil.example.net.

;; ADDITIONAL SECTION:
evil.example.net.	86400	IN	A	192.0.2.53

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
HUMBER THAMES DOVER WIGHT PORTLAND PLYMOUTH: SOUTHWESTERLY 7 TO SEVERE GALE 9,
DECREASING 5 OR 6 IN WIGHT, PORTLAND AND PLYMOUTH. ROUGH OR VERY ROUGH.
SQUALLY SHOWERS. MODERATE OR GOOD.