Subject: Re: The Birthday Defense

From: [email-masked]
Date: Tue, 2 Sep 2008 10:16:17 +0000

> (1) When sending a query to Root and 1st level (TLD) servers, a 
> random label is prepended to the questions. Since these servers 
> have no knowledge of the subdomain structure of lower levels*, 
> the response will be the unaffected. An effectively unlimited amount of 
> entropy can be had in this case.
> 
> * This assumption seems reasonable, however it is conceivable that it is not valid.

Many TLDs have non-delegated subdomains; that breaks the assumption. How do you handle a query for com. or . (the root)? A hack would be to just not cache the result.

arpa is not delegated anywhere; dig NS ARPA should return NODATA, but if your algorithim is used it would return NXDOMAIN (nonce.arpa doesn't exist). arpa could be special cased, though, but I dislike that - it's likely that at some point there will be another (indeed, there may already be) non-delegated domain in the root; let's not require a resolver upgrade to let it work.

> (3) If the entropy is still not sufficient, the query is repeated.
> Some DNS servers however are not deterministic - they do not always
> give the same reply to a given question, therefore the program needs
> to be able to analyze multiple responses to extract useable secure data.
> In some cases this might in principle be very difficult or time consuming,
> however in practice this goal does appear to be achievable, and at a
> moderate cost in terms of additional network traffic.
> 
> Other techniques
> ================
> (1) Taking observed Bad IDs into account.
> When a response is received from a DNS server, the ID field is checked.
> By reducing the calculated entropy based on the number of Bad IDs observed, 
> attacks can be slowed to a controlled level, while not incurring a performance 
> penalty under normal operation.

Sounds good.

> Analyzing multiple responses
> ============================
> The approach is as follows:
> 
> (1) For each distinct DNS record, we keep a counter that accumulates the entropy
> each time it is observed in a response. When the counter reaches 50 bits ( or 
> whatever value is configured ), we conclude the record is valid.
> 
> For example:
> 
> Question is MX records for www.example.com.
> Entropy of each packet received is 16 + 12 = 28 bits ( assuming no Bad IDs are observed ).
> We receive 3 packets.
> 
> 1:
> example.com MX mail1.example.com
> example.com MX mail2.example.com
> 
> 2:
> example.com MX mail1.example.com
> example.com MX mail3.example.com
> 
> 3:
> example.com MX mail2.example.com
> 
> Entropy totals are
> example.com MX mail1.example.com : 56 ( valid )
> example.com MX mail2.example.com : 56 ( valid )
> example.com MX mail3.example.com : 28 ( not yet valid )
> 
> (2) Various integer quantities are checked by accumulating entropy.
> An example is the RCODE value. For each RCODE value, we maintain an 
> accumulator that totals the entropy for that value. When the accumulator
> reaches 50 bits ( or whatever value is configured ), the value is assumed
> to be valid.
> 
> For example:
> 
> Question is A records for www.example.com.
> Entropy of each packet received is 16 + 12 = 28 bits ( assuming no Bad IDs are observed ).
> Therefore after receiving an RCODE of 3 twice, we conclude that the output RCODE should be 3.

Why do this? If one can spoof the RCODE, one can spoof records, surely, which is more damaging.

> (4) After 20 iterations ( or whatever value is configured ), the process is terminated regardless,
> and valid records are cached. Security will be marginally (5 bits) weaker in cases where a (relatively)

How do you determine which records are valid?

> comparing DNS records for equality. The approach adopted is to take TTL values to be equal provided
> they differ by no more than 60 seconds ( or whatever value is configured ). This allows the multiple
> response analysis to terminate where TTL values are changing as the process continues - for example
> where a server is controlling the TTL for a server is scheduled to be off-line at a particular time.

I think I've never seen an instance where the TTL changes by <=60 seconds in an authorative name server; usually, there's either a much higher TTL (when one expects the records will not change soon) or a very low one (when one is preparing to switch servers or wishes to load banace).

--
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, 2 Sep 2008 12:48:46 +0100

----- Original Message ----- 
From: <[email-masked]>
To: <[email-masked]>
Sent: Tuesday, September 02, 2008 11:16 AM
Subject: Re: The Birthday Defense

> Many TLDs have non-delegated subdomains; that breaks the assumption.

Can you give an example? I haven't yet come across one ( apart from arpa 
which you mention ).

> How do you handle a query for com. or . (the root)? A hack would be to 
> just not cache the result.

I may have failed to mention some special cases, but it certainly works for 
normal operation.

> arpa is not delegated anywhere; dig NS ARPA should return NODATA, but if 
> your algorithim is used it would return NXDOMAIN (nonce.arpa doesn't 
> exist). arpa could be special cased, though, but I dislike that - it's 
> likely that at some point there will be another (indeed, there may already 
> be) non-delegated domain in the root; let's not require a resolver upgrade 
> to let it work.

Interestingly, the root servers appear to not behave uniformly for arpa 
queries.
j.root-servers.net returns a referral for <nonce>.arpa but 
a.root-servers.net returns NXDOMAIN.
Whatever, arpa is apparently (and maybe not suprisingly) a special case.
I'm tempted to suggest that NXDOMAIN is the best answer! (only joking)

I don't see any advantage to having non-delegated domains in the root - 
indeed treating arpa as non-delegated seems quite perverse to me, creating 
special cases is not usually a good idea.

---

From: "George Barwood" <[email-masked]>
Date: Tue, 2 Sep 2008 14:18:21 +0100

> Many TLDs have non-delegated subdomains; that breaks the assumption.

After a bit more thought, I think I'm beginning to understand what is going 
on here.

The DNS protocol does not make the Bailiwick explicit when sending a 
request.

So I may believe I'm sending a query to a "root" server, but in fact I'm 
just sending a query to an IP address. If that IP address happens to be 
hosting other zones, there is no way it can tell what I had in mind.

Now maybe in an ideal world, I would like the IP addresses used to host root 
and TLD zones ONLY to be used for that purpose, because it allows me to 
proceed efficiently. However in the real world, it's actually messy.

However, all may not be lost. If a NXDOMAIN reply is received, an additional 
query can be sent without the nonce. This should only occur rather 
infrequently, for the special cases such as ARPA and other sub-domains that 
happen to hosted on the same server as their TLD. For the vast majority of 
domains that's not the case.

It does seem to mean that detecting non-existent second level domains cannot 
be done efficiently.
That's a slight shame. Maybe a list of TLDs which promise to only serve 
referrals could be compiled.
If it could include the main domains ( COM, UK, NET, ORG ) etc. that would 
be useful.

---

From: [email-masked]
Date: Tue, 2 Sep 2008 17:50:30 +0000

> Can you give an example? I haven't yet come across one ( apart from arpa 

Borrowing from the recent dns-operations discussion, ns1.dynserv.com for instance.

> hosting other zones, there is no way it can tell what I had in mind.

It can be hosting only a TLD zone, but still not have a delegation.

> proceed efficiently. However in the real world, it's actually messy.

With the exception of a few things like nic.tld, I think they very rarely do host sub-zones of the relevant TLD. I think all root servers host only the root zone. 

> domains that's not the case.

Sounds ok, but you should do that for all succesful, non-referral queries IMO; it would be perverse (but will probably happen someday) that the queried domain (the one including the nonce) exists, probably due to wildcard records.

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Wed, 3 Sep 2008 10:01:03 +0200

On Tue, Sep 02, 2008 at 12:48:46PM +0100,
 George Barwood <[email-masked]> wrote 
 a message of 53 lines which said:

> Can you give an example? I haven't yet come across one

Several have already been mentioned on that list.

gov.fr
a-dns.pl
_nicname._tcp.de

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Wed, 3 Sep 2008 10:05:54 +0200

On Tue, Sep 02, 2008 at 02:18:21PM +0100,
 George Barwood <[email-masked]> wrote 
 a message of 35 lines which said:

> So I may believe I'm sending a query to a "root" server, but in fact
> I'm just sending a query to an IP address.

I cannot parse this sentence. If you send a query to a root name
server, you receive a reply from a root name server (unless you're
being attacked).

> If that IP address happens to be hosting other zones,

You mean "I may believe I'm sending a query to a PURE root name
server but, actually, it can host other zones". Correct?

> Now maybe in an ideal world, I would like the IP addresses used to
> host root and TLD zones ONLY to be used for that purpose, because it
> allows me to proceed efficiently. However in the real world, it's
> actually messy.

It is not messy, it is the way the DNS works and the way it always
worked.

I believe it was even used in U...S advertisments ("we host TLD and
some delegated domains, so it saves some round-trips").

> Maybe a list of TLDs which promise to only serve referrals could be
> compiled.

Ask Mozilla :-) Seriously, relying on published TLD policies is very
brittle.

---

From: Olaf Kolkman <[email-masked]>
Date: Wed, 3 Sep 2008 14:51:42 +0200

Hello [email-masked],

My name is Olaf Kolkman, what name do you go by in day to day life?

You wrote:
>
> arpa is not delegated anywhere; dig NS ARPA should return NODATA,

Allow me to correct that:  .arpa is an independent zone and currently  
all of the root servers except for J.root-servers.net are  
authoritative for .arpa.

> but if your algorithim is used it would return NXDOMAIN (nonce.arpa  
> doesn't exist). arpa could be special cased, though, but I dislike  
> that - it's likely that at some point there will be another (indeed,  
> there may already be) non-delegated domain in the root; let's not  
> require a resolver upgrade to let it work.

George wrote:
> Interestingly, the root servers appear to not behave uniformly for  
> arpa queries.
> j.root-servers.net returns a referral for <nonce>.arpa but a.root- 
> servers.net returns NXDOMAIN.

This is not unexpected, given that the all-but-J root-servers are  
authoritative they can authoritatively provide you with an NXDOMAIN  
while J gives a referal.

> I don't see any advantage to having non-delegated domains in the  
> root - indeed treating arpa as non-delegated seems quite perverse to  
> me, creating special cases is not usually a good idea.

 From a protocol perspective the fact that an authoritative server  
serves more than one zone is not a special case. From a protocol  
perspective the servers that serve the root, or TLD zones, are not  
special cases.

If the protocol design starts to make special considerations for root  
or TLD servers we should treat that as an indication that we should do  
a better job.

Oh, by the way from an operational point of view the fact that the  
root servers serve .arpa is somewhat special (see RFC2870 section 1.2  
and 2.5), but that is outside the scope of this group, me thinks.

--Olaf