Subject: Repeat queries to non-deterministic servers

From: "George Barwood" <[email-masked]>
Date: Sun, 31 Aug 2008 08:35:58 +0100

When sending a repeat request ( to increase entropy ), some name servers give different replies on each request.

Has anyone considered the best way to handle this? 

My current heuristic is to count

Total = Total number of distinct records seen.
ConfTotal = Total number of distinct records confirmed ( total entropy above threshold of 50 bits ).

and to stop when

Total > 0 and Total = ConfTotal // the normal case for deterministic servers
or ConfTotal > 30
or in any case after 20 queries.

An example is found when resolving the host E120.G.AKAMAIEDGE.NET

Using the heuristic above, this stops with Total=68, ConfTotal=31 after 9 queries ( typically - results vary ).

So this seems to work well enough in practice, however it seems somewhat arbitrary, and thus not entirely satisfactory, leaving open potential inter-operability problems.

The standards aspect is that implementors of authoritative DNS servers could be warned that non-deterministic responses may cause some resolvers to make multiple repeat requests, leading to either loss of performance and increased traffic, or reduced security, if resolvers decide to accept data below a safe entropy level.

It's not entirely clear to me what such servers are trying to achieve, but I suspect it could be achieved by changing the served data on a slightly less frequent basis ( for example once a minute rather than on every request ). An alternative would be to use long names, which allows extra entropy to be encoded via the 0x20 channel, eliminating the need for repeat queries, or to implement other proposals for increasing entropy ( e.g. AL record ).

I don't believe such servers are common, so "fixing" them may be possible. It could be that akamai is the only significant example - although I certainly don't know this, Has anyone researched this? It is impossible to update ALL authoritative servers, however updating most of the significant non-deterministic ones may be feasible in a reasonable time frame, and that is should be good enough.

---

From: Nicholas Weaver <[email-masked]>
Date: Sun, 31 Aug 2008 08:05:13 -0700

On Aug 31, 2008, at 12:35 AM, George Barwood wrote:
> When sending a repeat request ( to increase entropy ), some name  
> servers give different replies on each request.
>

This is why I advocate treating cache and transaction separately.  EG,  
assume you are behind a NAT, so you only have 0x20, and you're looking  
for a typical 8 character name.  Thus you only have 24 bits of  
entropy, which is uncomfortably low.

If you send two requests and, if they disagree, don't cache the result  
but do return (a random) result with a TTL of 1 second, the name will  
have resolved with 23b of entropy, but the cache will be protected  
with 47b of entropy.

This is because blind transaction attacks are really limited:  you  
need to trick the victim into issuing a request and acting on it  
immediately at the application layer, which is a much smaller window  
than a cache attack.

Thus the consequence:  As long as the authority always sends  
disagreeing results, each result is individually protected by a 23b  
race.  But such races are transactional attacks, which are far less  
useful than cache attacks.

As soon as it returns an agreeing results, it gets cached with 47b of  
entropy, which means its infeasible for a blind cache attack.

> It's not entirely clear to me what such servers are trying to  
> achieve, but I suspect it could be achieved by changing the served  
> data on a slightly less frequent basis ( for example once a minute  
> rather than on every request ). An alternative would be to use long  
> names, which allows extra entropy to be encoded via the 0x20  
> channel, eliminating the need for repeat queries, or to implement  
> other proposals for increasing entropy ( e.g. AL record ).

Since a lot of this is for load-balancing purposes, expect that this  
volatility will remain.

You won't get them to change, but I argue it is SAFE to accept them  
for transactions as opposed to caching.

--
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: Paul Vixie <[email-masked]>
Date: Sun, 31 Aug 2008 16:04:47 +0000

> ...
> have resolved with 23b of entropy, but the cache will be protected with
> 47b of entropy.
> ...

as also noted privately, a TTL of 0 on the RDNS response is useful in this
case since if the response goes to a forwarder rather than to a stub we
would not want it reused even for the remainder of that 1 second period.

> ...
> Thus the consequence: As long as the authority always sends disagreeing
> results, each result is individually protected by a 23b race.  But such
> races are transactional attacks, which are far less useful than cache
> attacks.
> ...

i note with amusement that servers who send disagreeing results usually have
very short TTLs (five seconds) and would probably enjoy it if we shortened
them still further.  these are mostly load balancers who do not benefit from
caching in the ramparts.  they don't use TTL 0 because it's considered rude
when an ADNS does that.  but if an RDNS does it, hey, who are they to argue?

> entropy, which means its infeasible for a blind cache attack.

this is a very neat solution to the problem i couldn't find a solution for
in my "minimum entropy" proposal a month or so ago.

> ... I argue it is SAFE to accept them for transactions as opposed to
> caching.

safety is in the eye of the beholder.  if someone is behind a NAT
derandomizer and they have 24 bits of entropy then they have a lot less
than ten hours between successful keyhole attacks and they ought to worry.
in that sense, your proposal makes them safer, and that's worth noting.
(of course, stopping the derandomization of source-port would also make
them safer.)

---

From: "George Barwood" <[email-masked]>
Date: Sun, 31 Aug 2008 17:52:33 +0100

> races are transactional attacks, which are far less  useful than cache 

If I can have it, I prefer to have 50 bits everywhere, and a simple design 
where everything gets cached.

> Since a lot of this is for load-balancing purposes, expect that this 

For load balancing, it's not necessary to have complete non-determinism ( 
albeit this may be the easy option ).

> You won't get them to change....

I probably wrongly gave the impression that I NEED them to change. In this 
case the records involved are NS records with a relatively long TTL ( 30 
minutes ), and once established in the cache, can be refreshed with a single 
query.

It all works absolutely fine in practice, and the extra traffic is 
completely insignificant, so the inefficiency is very theoretical.
The A records (which are deterministic) have a TTL of 20 seconds, so these 
can be expected to dominate the load.

If I understand your proposal correctly, each time one of these 20 second 
TTL A records expire, 2 requests would be needed instead of 1, as the 
non-deterministic NS record will not have been cached. That would produce a 
far higher extra load.

Another consideration : any genuine operational problems (with the 
convergence algorithm given) will I think only occur in the context of huge 
server farms. So if there are problems, I think they will come to light very 
rapidly. There cannot be too many organisations with networks of 
hundres/thousands of nameservers, so if Akamai are the largest, I think any 
problem is likely to be theoretical. Must do some more surfing :)