Subject: Some observations on dns-0x20

From: "George Barwood" <[email-masked]>
Date: Mon, 18 Aug 2008 21:06:25 +0100

I have been experimenting with the technique described ( Google for GbDns if interested ), and have a few observations.

(1) A simple way of dealing with case sensitivity when parsing a string in a DNS requests is to preserve case if and only if the section is the Question section.

For other sections I believe that simply reducing to lower case will not cause any problems, at least in a recursive context, and is the simplest and best solution.

(2)  When checking a response, a good model is to estimate the number of bits of entropy (random bits) that have been retained from the original request ( I will refer to this as the Confidence value ).

The port number entropy should be discounted if the program may be behind a NAT device, unless it is known that the device preserves port randomization. I think this might be mentioned somewhere in the standard.

If unusual responses are detected ( for example incorrect IP, Question not copied, Question case not preserved ), the response need not be entirely ignored, rather a suitable discount can be applied in the entropy computation.

(3) A possible implementation technique is to maintain a Confidence field for each cache entry.
When processing a response, the Confidence value computed in (2) can be added in when an exactly matching cache element ( normally with expired TTL ) is found.

A valid cache entry is thus one which has valid TTL and valid Confidence value ( say 50 bits ).

The resolver loop can iterate until either a cache entry is found, or an iteration occurs in which the cache is not updated ( this includes updates to TTL or Confidence values ).

Non-existence and error conditions can also be cached, with confidence values.

Lastly, I would like to say that I strongly support dns-0x20, and have communicated a couple of suggested changes privately to Paul, which he has graciously agreed to make, viz.

(a) In section 7.4, to drop the words "by a factor of "several".
(b) In section 5.2 to change "MUST" to "SHOULD".

George Barwood

---

From: Nicholas Weaver <[email-masked]>
Date: Thu, 21 Aug 2008 09:59:28 -0700

(note, these are taken from some thought I've been writing down in our  
group blog, http://blog.icir.org/2008/08/entropy-blind-attacks-and-dns.html 
, comments greatly appreciated).

On Aug 18, 2008, at 1:06 PM, George Barwood wrote:
> (2)  When checking a response, a good model is to estimate the  
> number of bits of entropy (random bits) that have been retained from  
> the original request ( I will refer to this as the Confidence value ).
>
> The port number entropy should be discounted if the program may be  
> behind a NAT device, unless it is known that the device preserves  
> port randomization. I think this might be mentioned somewhere in the  
> standard.

The question is, how to KNOW this.

We have a test server for a bunch of tests, at a temporary location as  
part of a larger project.

One of the tests, port.{anything}.nettest.icir.org

will return the port number in the lower 16 bits of the IP address.

My belief is that there should be an official server with this  
property.  Thus resolvers can query the server a few times on startup  
to know if the port number is preserved.  [1]

Yes, its a software "phone home", but given how much evil stuff you  
can hide in code, you have to trust the code for your DNS resolver  
anyway, so whats so bad about having to trust its phone-home to check  
for network properties?

> When processing a response, the Confidence value computed in (2) can  
> be added in when an exactly matching cache element ( normally with  
> expired TTL ) is found.

Here is my thought on entropy based defenses against blind attacks.   
Pardon if all of this has been hashed out already, but even in that  
case its probably worth remembering:

There are two classes (when viewed from one perspective) of DNS  
attacks: transactional attacks (where the attacker "wins" if the  
transaction is corrupted) or cache attacks (where the attacker "wins"  
if the cache is corrupted.)

There are very few blind attack scenarios which are transactional [2],  
but they do exist, and defenses can vary on how much they protect  
transactions vs the cache.

I don't like the idea of individual confidence, however.  I prefer a  
simpler model of a global entropy budget and a global paranoia level,  
its far simpler and easier to manage.

And for such an entropy budget, 40b is probably sufficient to protect  
the cache.  Here's why.

The probability of success, for attacking a resolver with K bits of  
entropy in the request with N tries is:

P = 1 - (1-2^-k)^N    (Namely, the probability of ALL failing is  
(1-2^k)^N, which means the probability of at least one success P = 1- 
(1-2^k)^N)

To put in some concrete numbers: assume an attempt is 100B of data,  
and the attacker is happy with a roughly 1.5% chance of success.

With k = 16 and N = 1000, P = .015 and it took 10 KB of data.  Owch.

With k = 32 and N = 7e7, P = .016 and it took 7 GB of data.  Not bad.

With k = 40 and N = 2e10, P = .018 and it took 2 TB of data.  HA!

And remember, this is a "bear race": The resolver doesn't have to be  
100% bulletproof, it just has to be strong enough that it is not  
economically viable to attack.  A botnet which can spew 2 TB of  
spoofed data is a pretty valuable resource, who wants to waste it for  
a <2% chance of success?

Failed attempts, however, are easily detectible, as many have pointed  
out:  Any response which mismatches on the entropy (EG, to a different  
port, with a different transaction ID, which doesn't just all-lower or  
all-upper an 0x20 response, but uses a different captialization) is an  
unsolicited response, caused by either a buggy server (they exist but  
are reasonably rare) or an attack.

More importantly, it appears plausible to use this property to set a  
"Maximum P of the cache having a corrupt entry" in practice, and  
RESPOND to it.

Choose a good P, say .0001 (or, put it this way, a .01% chance that  
there exists one or more bad cache entries), plus your minimum entropy  
budget for transaction, and maintain a single global count of  
unsolicited responses.

Now if the number of unsolicited responses is enough that P is over  
your threshold of paranoia, just flush the ENTIRE cache, accept the  
latency hit and extra traffic until you repopulate, and be happy.

For low K (eg 16b), you fail.  Don't bother.  If k is 16b, you are  
dead anyway.

And for a moderate k, this isn't that good.  EG, with P being approx . 
0001 (moderately paranoid),

With k = 32, N would be roughly 5e5, or 50 MB of data.  If your cache  
has 1M entries, this would require refetching, say, 500 MB of data.   
So this, when used as a DOS, would be a roughly 10x amplification, not  
great, but not horrible.  How paranoid are you?

But with a high k, say 40 bits, it IS good.  Lets set P to be approx . 
00001 (or a .001% chance of a single bad cache entry, high paranoia).

With k = 40, N would be roughly 1e7, or 1 GB of data.  So if this is a  
"DOS", it isn't: there's negative amplification. If an attacker needs  
to send 1 GB of data at my resolver, to cause it to flush its cache  
and refetch 500 MB of data, or to have a .001% chance of inserting a  
bad cache entry, he's welcome to it!  Bots are valuable, and the ROI  
for such an attack can only be described as pathetic.

But at the same time, this says "Don't bother trying to get the  
entropy above 40 bits".  40 bits can leave you such a comfortable  
margin that you don't need to get above it, even if you are paranoid  
about flushing the cache when you think you might have been attacked.

And 40 bits is easily achiveable without duplication for most queries  
when not NATed.

Random TXID: 			16b
Random port: 			13b
Random selection of resolver:	 2b
Random caps (www.foo.com):	 9b
-----------------------------------
				40b

And you can know when you are generating the query if you meet your  
entropy budget or not (assuming fallback of rerequest on 0x20 failure  
as "all lower" or "all upper", and checking for NAT), so you can just  
look at your entropy budget and decide if you need to do something more.

And "something more" being duplication has an interesting property,  
depending on your behavior, that needs to be remembered.

If your policy is "send two queries (same query, different entropy  
values), return first, cache only on agreement":

Ups cache entry by nearly double: the attacker must match both from  
the same query to succeed in poisoning the cache.  So if your initial  
entropy is K bits, it should make it 2K-1 bits of entropy.  Cool  
beans.  For protecting the cache, NATs don't matter if you know you  
are behind one.

REDUCES transactional entropy by 1 bit: the attacker gains a minor  
birthday advantage, so if your initial entropy is K bits, it makes  
transactional entropy K-1 bits.  Uhhh, how serious do you consider  
transaction attacks vs cache attacks? It gets down into the question  
on the footnote 2.

But there are some anomalous servers, which for the same repeated  
query will return different values.  With this policy an anomalous  
server which returns different values for the same query will not be  
cached yet will be resolved by the client.  Cool beans: You punish  
them with more load, but their results still work.

If your policy is "send two queries, return and cache only on  
agreement":

You still get the great increase in cache entropy, you increase  
transactional entropy (yay), but the anomalous servers don't work  
anymore at all (boo?).

So with duplication to increase entropy, although it works great to  
protect the cache, you have to decide how you want to protect  
transactions:  Do you want to decrease the transactional entropy  
slightly, or do you want to not resolve these anomalous servers?

(Acknowledgements:  This discussion was shaped by a lot of discussions  
with many individuals, including David Dagon, Robin Sommer, Wouter  
Wijngaards, Mattias Valintin, Dan Kaminski, and I'm sure I'm  
forgetting a few others).

[1] Although many people consider nat "Malicious", there is no reason  
for a nat or firewall to special case such a query, so the value can  
be trusted.  Because if a NAT or firewall DID special case such a  
query, it should be considered an agressive Man-in-the-Middle attacker  
anyway, and nothing short of DNSSEC works for that.

[2] The only scenario I can determine where a blind TRANSACTIONAL  
attack is useful (vs a blind cache attack) is cookie/authentication  
credential stealing from a site with insecure cookie handling.

Eg, login.yahoo.com holds Yahoo's global session cookie, which is  
needed to log into yahoo mail.

1)  Notify the attacker (by doing a DNS lookup by opening an iframe on  
a sub-domain of the attacker's control)

2)  Open an iFrame to login.yahoo.com, while the attacker  
simultaneously launches a traditional blind poisoning attack for  
login.yahoo.akadns.net.

3)  Observe that cookie policy is "specific": cookies for  
login.yahoo.com are returned for 1.login.yahoo.com, 2.login.yahoo.com,  
etc, so you can open up a gazillion iframes, each for different  
variants, getting the "run N races and win one" property but for a  
transactional attack.

However, notice that for a blind transactional attack to work against  
an HTTP site, the site is also trivially vulnerable to Mike Perry's  
attack using TCP packet injection, so how much protection is really  
necessary to build into the DNS transaction (vs the cache) for  
software thats already b0rken?

--
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: "George Barwood" <[email-masked]>
Date: Tue, 26 Aug 2008 14:50:36 +0100

> My belief is that there should be an official server with this  property. 
> Thus resolvers can query the server a few times on startup  to know if the 
> port number is preserved.  [1]

My laptop computer can be be connected via different firewalls during the 
course of the day.
The cache can be left running for weeks on end ( I reboot maybe once a 
month ).
I don't know if it is possible for the software to reliably detect that the 
nature of the connection has changed.

> But there are some anomalous servers, which for the same repeated  query 
> will return different values.  With this policy an anomalous  server which 
> returns different values for the same query will not be  cached yet will 
> be resolved by the client.  Cool beans: You punish  them with more load, 
> but their results still work.

Even though different values may be returned, assuming the number of valid 
results is finite (and not too large) [1], suitable confidence will be 
obtained. As an example, suppose there are 50 valid IP addresses, and the 
server returns a random subset of 8 of these on each query. After 7 queries 
at least one will have been returned twice, after 13 queries at least one 
will have been returned 3 times etc.

There is a problem though : deciding when the process has "converged". The 
simplest approach is to stop as soon as any result is available with 
required confidence value. This could result in the client being given just 
1 IP address, leading to an unexpected loss of resilience [2].

As an end user, I'm happy to live with this. I am doubtful that these 
anamolous servers are significant, and the example given seems quite 
artificial. If anyone knows differently, that would be interesting.

For such servers, an alternative would be to divide the 50 servers into 
groups ( 6 groups of 7 and one of 8 ), and then return a randomly selected 
group on each query. That ensures that a full set of at least 7 servers will 
be returned to the clients using a repeated query strategy.

 I'm also thinking about whether a more robust method of testing for 
convergence makes sense - for example sending extra queries if the result 
set shows unusual convergence - normally all confidence values will be 
equal. It seems to be hard however to distinguish between poor convergence 
and a possible attack with certainty.

[1] This assumption seems entirely reasonable to me.

[2] Many applications don't properly use multiple results, so the loss may 
be not be significant in any case.

---

From: Nicholas Weaver <[email-masked]>
Date: Tue, 26 Aug 2008 08:12:56 -0700

On Aug 26, 2008, at 6:50 AM, George Barwood wrote:

>> property. Thus resolvers can query the server a few times on  
>> startup  to know if the port number is preserved.  [1]
>
> My laptop computer can be be connected via different firewalls  
> during the course of the day.
> The cache can be left running for weeks on end ( I reboot maybe once  
> a month ).
> I don't know if it is possible for the software to reliably detect  
> that the nature of the connection has changed.

When it connects to a new firewall, you have an event where the  
network connectivity went down and up.  I imagine that on most systems  
this is a detectable event for your stub resolver.  (And how fixed are  
the stub resolvers anyway, vs the caching resolvers, in upping entropy  
at all?)

There are also other heuristics (eg, has the MAC for the gateway  
changed) which could also be used.

Additionally, although the resolving cache on your notebook is  
moderately important, where the NAT behavior is critical is on the  
centralized cache:  Far too many businesses with many systems put them  
all behind a NAT to save money and reduce exposure, as a NAT  
effectively acts as a one-way firewall.

It is these resolvers that need to be protected against NATs.

>> server which returns different values for the same query will not  
>> be  cached yet will be resolved by the client.  Cool beans: You  
>> punish  them with more load, but their results still work.
>
> Even though different values may be returned, assuming the number of  
> valid results is finite (and not too large) [1], suitable confidence  
> will be obtained. As an example, suppose there are 50 valid IP  
> addresses, and the server returns a random subset of 8 of these on  
> each query. After 7 queries at least one will have been returned  
> twice, after 13 queries at least one will have been returned 3 times  
> etc.

I'd still rather "don't bother":  Converging is going to be very long  
and a lot of traffic, probably far more than "just don't cache" at all  
for most cases.

And this is exactly why I believe in treating transactions vs caches  
separately: How many cases are there where you have "Race until win"  
on a transaction attack (vs getting something into the cache.   
Kaminski attacks are cache attacks)?

The only case I can come up with is cookie-hunting for insecure (non  
SSL-marked) cookies by generating a bunch of subdomains in iframes  
(bad1.login.yahoo.com, bad2.login.yahoo.com, etc) where the first one  
which succeeds will return the cookies to the attacker's server.

Can someone come up with other cases of blind transaction attacks?

---

From: "George Barwood" <[email-masked]>
Date: Tue, 26 Aug 2008 17:19:49 +0100

> There are also other heuristics (eg, has the MAC for the gateway  changed) 
> which could also be used.

It all gets rather complex really, and complexity is enemy of security.
I might be connected via a mobile phone that keeps changing networks.
Or an intermediate local computer that uses multiple NAT connections.
Or all sorts of stuff that I have no idea about, or might happen in future.
[ Please understand I'm no expert in networking ]

> It is these resolvers that need to be protected against NATs.

Well there are more than a billion Windows computers, all wide open AFAIK.
No port randomization, no checking code, no repeat queries, nothing.
I'm not exactly sure how vulnerable they are in practice, but it doesn't 
feel good to me.

> I'd still rather "don't bother":  Converging is going to be very long  and 
> a lot of traffic, probably far more than "just don't cache" at all  for 
> most cases.

It's no bother really. It's a situation I don't expect in practice, but 
having something that will work (albeit with a second or two delay) if it 
ever does happen seems sensible.

> separately: How many cases are there where you have "Race until win"  on a 
> transaction attack (vs getting something into the cache.   Kaminski 
> attacks are cache attacks)?

I haven't understood this concept. From my point of view being spoofed just 
once is unacceptable, if it can be defended. Besides, won't not caching 
opens up attacks?
But as I don't understand, maybe it's unwise to comment.

---

From: Nicholas Weaver <[email-masked]>
Date: Tue, 26 Aug 2008 10:09:29 -0700

> [ Please understand I'm no expert in networking ]

There are really two cases:  Either you're NATed (between you and the  
remote resolver/authority) or you aren't.

If you are NATed, port number offers NO entropy and NO protection,  
thus if you need entropy protection, and your default behavior is  
gaining it through port number, you MUST know if that protection is  
being stripped away.

Fortunately, not only is this easy to check, but (see below) easy to  
determine if its changed with very VERY high probability.

> I'm not exactly sure how vulnerable they are in practice, but it  
> doesn't feel good to me.

Well, the stub resolvers can be trivially fixed with regard to cache  
attacks by simply removing the local cache from the stub resolver (or  
just setting the max TTL to a minute).

But that's cheating, and may have some bad properties.  (Note that it  
loads the recursive resolvers far more than it loads the rest of the  
infrastructure, as the union of the recursive resolvers' caches is a  
superset of the stub resolver's cache.).

More importantly: if your IP changes, your NAT state may have  
changed.  But if your IP doesn't change, the probability of the NAT  
state changing is very, VERY low.

Thus it is easy for a resolver to both determine if it is behind a NAT  
and if the status has changed.

The only case where this fails is if you move between two NATs that  
assign you the same IP address, but where the first NAT doesn't  
rewrite port numbers but the second NAT does, but a secondary  
heuristic of "If in the private address space, ASSUME I'm natted" is  
probably safe to trap these few cases.

So "Private IP?  Assume I'm natted.  Otherwise, IP changed?  Recheck  
for NAT" is a heuristic that should work very well for protecting the  
stub resolvers, and works great for the NATed recursive resolvers  
(which don't have the mobility issues, so you only need to check for  
NAT on startup).

>> I'd still rather "don't bother":  Converging is going to be very  
>> long  and a lot of traffic, probably far more than "just don't  
>> cache" at all  for most cases.
>
> It's no bother really. It's a situation I don't expect in practice,  
> but having something that will work (albeit with a second or two  
> delay) if it ever does happen seems sensible.

Unfortunately, it is "common enough"  from what I understand, but no  
evidence for myself.  :(

>> And this is exactly why I believe in treating transactions vs  
>> caches separately: How many cases are there where you have "Race  
>> until win"  on a transaction attack (vs getting something into the  
>> cache.   Kaminski attacks are cache attacks)?
>
> I haven't understood this concept. From my point of view being  
> spoofed just once is unacceptable, if it can be defended. Besides,  
> won't not caching opens up attacks?

Some observations:

1) In the blind attack, the attacker is the one generating the  
requests (through some mechanism) as well as the responses.

2) In ALL kaminski variants, and in MOST cases for traditional blind  
cache poisoning, the attacker really doesn't care about the result  
being returned, only that the result is CACHED for subsequent lookups,  
because the attacker generated the lookup in the first place!

In fact, it is the process of CACHING that opens up to all the glue  
poisoning/cache poisoning attacks.  If you don't have a cache at all,  
you can't have cache poisoning!

This is why I believe it is critical to separate out the notion of  
"Transaction" attacks from "cache" attacks.

In a blind transaction attack, the attacker ONLY needs to get you to  
accept the spoofed result for the current transaction.

But such cases are rare, because the attacker must trick the victim  
into making the request AND acting on the request in a way which harms  
the victim: the only case I can come up with is cookie-stealing from  
badly secured web-apps, but such webapps are weak to CookieMonster,  
Sidejacking, and other attacks.

In a blind cache attack, the attacker MUST get you to accept the  
spoofed result into the cache, but in return, the attacker only needs  
to trick the resolver into making the requests.

Thus although I agree that we need to protect both, if, due to  
circumstances (eg, NAT) where we can only protect one at the cost to  
the other, it may be a worthwhile tradeoff.

> But as I don't understand, maybe it's unwise to comment.

a)  I never let MY IGNORANCE stop me from commenting.  Why should  
anybody else?

b)  I believe the position I'm expounding SHOULD be clearly  
explainable.  If it doesn't make sense to you, its not a failure on  
your part, but a failure on my part!

---

From: Mark Andrews <[email-masked]>
Date: Wed, 27 Aug 2008 10:17:05 +1000

> If you are NATed, port number offers NO entropy and NO protection,  

	If you are NAT'd the port number MAY offer you no protection.
	There are NAT's which attempt to preserve port numbers and
	actually do a pretty good job of doing that.

	If you are NAT'd the NAT MAY provide protection for nameservers
	that do not randomize their source ports by randomising the
	source port as a side effect of the NAT process.

	There are also NAT's which serialize the ports and NAT's
	which only emit one port and potentially serialize the qid
	as well.

	The only thing you can say about NATs is because there is
	no standard they can be doing ANYTHING to the queries.  This
	is one of the reasons NAT's are a abomination that people
	should be working to remove as soon as possible.

	Mark

-- 
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]

---

From: [email-masked]
Date: Thu, 28 Aug 2008 22:03:20 +0100

>    which only emit one port and potentially serialize the qid

Mark,

Can we please make a distinction between plain NATs (which only affect 
TCP/UDP and IP headers) and proxies (or ALGs) which manipulate the 
protocol at higher levels?

I've never seen a NAT which affects QIDs.  I've seen plenty of ALGs that 
do, though, many of which did indeed pick serial QIDs :(

Ray

---

From: Mark Andrews <[email-masked]>
Date: Fri, 29 Aug 2008 10:04:44 +1000

> do, though, many of which did indeed pick serial QIDs :(

	I agree with you that there is a difference.   The problem
	of course is that you often don't know that a ALG is also
	installed in the NAT box.

	You generally buy a NAT (router in some markets) and have
	no idea of what's inside as the vendors don't give you
	enough details.  You are also often not in a position to
	see the traffic on both sides as the upstream may be a
	cable/dsl modem and not ethernet.

	Mark

---

From: Nicholas Weaver <[email-masked]>
Date: Thu, 28 Aug 2008 18:06:55 -0700

> 	cable/dsl modem and not ethernet.

However, for purposes of building a DNS resolver, you can probe for  
the detailed behavior, including port, ID, IP, etc, by querying a  
properly constructed authority, so you can be in a position to see  
both sides of the traffic: you just have to ask somebody who will tell  
you the other side.

{port,txid,server}.{anything}.nettest.icir.org is one protoype example.

This works in all cases where the NAT/proxy is not malicious  
(deliberately whitelisting the tests) and who's behavior doesn't  
change (you can always repoll to check for changed behaviors at a  
reasonable interval, however).

For a malicious proxy in path, you are sunk however, but with a  
malicious proxy in path, you are sunk period.

---

From: Mark Andrews <[email-masked]>
Date: Fri, 29 Aug 2008 11:17:10 +1000

> malicious proxy in path, you are sunk period.
 
And one really wants a solution where you don't need to care about
whether the port or txid are being changed or not.  You also want
one where you can detect a malicious proxy / cache.

Mark

---

From: Paul Vixie <[email-masked]>
Date: Fri, 29 Aug 2008 02:26:12 +0000

> one where you can detect a malicious proxy / cache.

agreed.  testing for this and responding to it adds complexity and doesn't
nec'ily buy you anything if the ADNS you're querying is behind their own
local NAT-based derandomizer.

---

From: [email-masked]
Date: Fri, 29 Aug 2008 08:10:03 +0100

>    installed in the NAT box.

If your (DHCP-derived) DNS server settings point at your router, it has an 
ALG in it.

Ray

---

From: [email-masked]
Date: Sat, 30 Aug 2008 17:35:23 +0000

> local NAT-based derandomizer.

The only circumstance I've thought of where that is true is where the attacker is behind that NAT device and is capable of spoofing packets.  This is surely a very rare position. 

MITM attacks are possible in most of those positions; e.g. ARP spoofing the gateway. It's up to the ADNS operator to ensure their network isn't braindead. Furthermore, I think ADNSs are rarely behind NAT devices.