Original text published April 22nd 2008:
(proposal now retracted - see above)

Anti DNS spoofing - Extended Query ID (XQID)

ABSTRACT

This document describes a method for preventing so-called "DNS spoofing" attacks against DNS resolvers.
This is achieved by extending the DNS query ID with up to 63 alpha-numeric characters into the query/response question name (QNAME) making the range of possible transactions IDs so extremely large that any brute force "guessing" or birthday attack attempts are futile.

I acknowledge that DNSSEC may eventually solve the DNS spoofing issue for many domain names, but there is probably also going to be a lot of domain names that are never "DNSSEC" signed for various reasons for a very long time. XQID can protect against spoofing while we wait for DNSSEC, and long term for all un-signed domain names.

ADVANTAGES

• Solves the DNS spoofing problem in a fairly simple way.
• The security benefits are immediate between any DNS resolver and authoritative DNS server that both implement XQID.
  No need to wait for root / TLDs to be "signed" or otherwise updated.
• Referral responses are automatically secured even if the DNS server returning the referral response knows nothing about XQID.
• The root and TLD zones are automatically secured without any changes to the root and TLD DNS servers (because referral responses are automatically secured).
• Simple to implement (personally implemented server side code with only 20 lines of code)
• Simple to use - no user configuration needed.

DEFINITIONS

• XQID (extended query ID)
  A domain name label consisting of 24 to 63 random characters (0-9, a-z). Not case sensitive.
  The minimum length is 24 characters both to avoid collisions with existing domain names and to provide at least the equivalent of 128 bits of random data.
  The maximum length of 63 characters is the normal DNS protocol wire-format limitation.
  The use of only 36 different characters (0-9, a-z) is to ensure backwards compatibility.
• XQID-query prefix
  Reserved domain name label "xqid--q". Not case sensitive.
• XQID-response prefix
  Reserved domain name label "xqid--r". Not case sensitive.

HOW IT WORKS

An XQID enabled DNS resolver sending a DNS query to a DNS server will add an XQID-query prefix and an XQID to the QNAME of the query, and will only accept responses with a QNAME containing a matching XQID - as follows:

1. DNS resolver sending query to DNS server
The DNS resolver first generates a new XQID which it must remember for the transaction.
It then assembles a normal DNS query packet - but adds the XQID-query prefix and the generated XQID to the beginning of QNAME.
For example, if the original QNAME is "host.example.com" and the generated XQID is "0123456789abcd0123456789", then the full QNAME in the query sent to the DNS server will be "xqid--q.0123456789abcd0123456789.host.example.com".

2. DNS server receiving the DNS query
If the DNS server supports XQID, it will determine if a query has a XQID by examining the query QNAME as follows:
a) QNAME must have two or more labels.
b) The first label of QNAME must be the reserved XQID-query prefix.
c) The second label of QNAME must be 24 bytes or longer.
If QNAME meets these criteria, the server will store the XQID (the second label), then remove the first two labels from QNAME (the XQID-query prefix and the XQID) and then process the query as normal.

If the DNS server does not support XQID, it will process the XQID-query prefix and XQID as actual labels of the QNAME and respond accordingly.

3. DNS server sending response back the DNS resolver
If the DNS server supports XQID, it will add a XQID-response prefix and the XQID from the query to the beginning of the response QNAME.
For example, if the original query QNAME was "xqid--q.0123456789abcd0123456789.host.example.com", then the full QNAME in the response sent back to the DNS resolver will be "xqid--r.0123456789abcd0123456789.host.example.com".
Notice that the QNAME in the query and the QNAME in the response are different - the last letter of the first label is 'q' in the query and 'r' in the response.

If the DNS server does not support XQID it will send a response with the same QNAME as the query including the XQID-query prefix and XQID.

4. DNS resolver receiving response from DNS server
The DNS resolver can easily distinguish responses from servers that support XQID and servers that do not by examining the first label of the response QNAME.
Responses from servers that support XQID will have a QNAME starting with a XQID-response prefix ("xqid--r").
Responses from servers that do not support XQID will have a QNAME starting with a XQID-query prefix ("xqid--q").
Either way the second label of the response QNAME will always contain the XQID.

The DNS resolver must process responses to XQID queries as follows:
1) If the first label of the response QNAME is not a XQID-query prefix or a XQID-response prefix, then the response must be ignored (spoofed). Skip steps 2-5.
2) If the second label of the response QNAME does not match the query XQID, then the response must be ignored (spoofed). Skip steps 3-5.
3) If the first label of the response QNAME is a XQID-response prefix (server supports XQID), the DNS resolver can simply process the rest of the response as normal - confident that it wasn't spoofed. Skip steps 4-5.
4) If the response is a referral for a domain name equal to or a parent of the original QNAME (without prefix and XQID), the DNS resolver can simply process this referral as normal - confident that it wasn't spoofed. Skip step 5.
5) The DNS client must resend the query without the XQID-query prefix and XQID to the same DNS server.
The following response is of course vulnerable to DNS spoofing as normal. The benefits of XQID are only realized when both sides of a transaction implement it.

IMPORTANT POINTS

• The DNS resolver must never fall back to resending the query without the XQID or accept any response without the correct XQID, before first having received a response containing the correct XQID - no matter what kind of error responses it might receive.
  If it did, the DNS resolver might as well not be using XQID at all, because the attacker could then spoof the error response.
• Only true DNS resolvers should send DNS queries with XQIDs and only in queries where the RD flag (recursion desired) is NOT set.
  XQID should generally not be used in queries from clients, forwarders, and any other software that send recursive queries (RD flag set) because an upstream DNS resolver or forwarder which does not support XQID might forward to a DNS server that does supports XQID and then not be able to match the response QNAME.

POSSIBLE ISSUES

• Longer QNAMEs. The XQID labels take 32 to 71 bytes from QNAME. As per RFC883 domain names cannot be longer than 255 bytes. This therefore may reduce the resolvable domain name length to 185 bytes from DNS servers that do not implement XQID.
  Don't know if there are many Internet names that are that long around? IDNs?
• Adding XQID labels to QNAME may be a problem with TSIG and DNSSEC packets (this has not been explored), but then there is probably no need to use XQID for such queries.
• XQID will generate additional DNS traffic between DNS resolvers that implement XQID and authoritative DNS servers that do not (resending queries/responses without XQID).
  Implementers of DNS resolvers may consider reducing this traffic by caching a list of DNS server IP addresses that do not support XQID (based on previous responses) and avoid sending those servers further queries with XQIDs.

EXAMPLE

An XQID enabled DNS resolver is asked to resolve www.example.com.

1) The DNS resolver sends a DNS query to an IP address from the pre-configured root server list (a.k.a. "hints file").
It generates a random XQID "p0yw5c4eq0c2hszuvr92dnw3".
The QNAME in this query therefore is "xqid--q.p0yw5c4eq0c2hszuvr92dnw3.www.example.com".

The response from the DNS root server is a referral to ".com" TLD DNS servers.
The QNAME of this response may begin with either "xqid--r" or "xqid--q" depending on whether the root server implements XQID or not - but this doesn't matter to the resolver for referral responses.
Either way the DNS resolver knows that the response is not spoofed because the second label of the response QNAME contains the correct XQID.

2) The DNS resolver sends a DNS query to one of the ".com" TLD DNS servers.
It generates a new random XQID "cl6ny86sk9elznx1jswibslu".
The QNAME in this query therefore is "xqid--q.cl6ny86sk9elznx1jswibslu.www.example.com".

The response from the ".com" TLD DNS server is a referral to one or more DNS servers responsible for "example.com".
The QNAME of this response may begin with either "xqid--r" or "xqid--q" depending on whether the ".com" TLD server implements XQID or not - but this doesn't matter to the resolver for referral responses.
Either way the DNS resolver knows that the response is not spoofed because the second label of the response QNAME contains the correct XQID.

3) The DNS resolver sends a DNS query to one of the "example.com" DNS servers.
It generates a new random XQID "ry8p9ldbe4tufrqr4trioo5h".
The QNAME in this query therefore is "xqid--q.ry8p9ldbe4tufrqr4trioo5h.www.example.com".

If the "example.com" DNS server implements XQID:
The response QNAME is "xqid--r.ry8p9ldbe4tufrqr4trioo5h.www.example.com".
The DNS resolver knows that the response is not spoofed because the second label of the response QNAME contains the correct XQID.
The response Answer section contains an A-record for "www.example.com" pointing to the IP address of the web-server.
The name is now resolved (and not spoofed) and the DNS resolver returns this data to the client as normal.

If the "example.com" DNS server does not implement XQID:
The response is NXDOMAIN.
The response QNAME is "xqid--q.ry8p9ldbe4tufrqr4trioo5h.www.example.com".
The DNS resolver knows that the response is not spoofed because the second label of the response QNAME contains the correct XQID.
Because the response QNAME starts with the XQID-query prefix ("xqid--q") and the response is not a valid referral, the DNS resolver resends the last query without the XQID and proceeds as normal.

LIVE TEST IMPLEMENTATION

The XQID server side functionality has been implemented in a private build of Simple DNS Plus now running on the following authoritative DNS server:

• nsks.jhsoft.com [204.9.75.101]

This servers will respond to DNS queries with XQID as described in this document.
For example lookup "xqid--q.012345678901234567890123.www.simpledns.com".

ACKNOWLEDGEMENTS

The idea described in this document was inspired by the Internet Drafts Use of Bit 0x20 in DNS Labels to Improve Transaction Identity (DNS-0x20) by Paul Vixie and David Dagon, Measures for making DNS more resilient against forged answers by Bert Hubert and Remco van Mook, as well as recent discussions on the IETF "namedroppers" list.

AUTHOR

Jesper G. Høy
JH Software ApS
Nordre Skanse 68
9900  Frederikshavn
Denmark
E-mail: jesper@jhsoft.com

PURPOSE AND STATUS OF THIS DOCUMENT

I have been contemplating something like this for a long time, but recent Internet drafts and IETF discussion (see acknowledgements) seem to indicate a renewed interest in this subject.
Initially I hope to get feedback from experts in the DNS community.
If the idea and concept stands up to this, I hope someone with experience in writing RFCs will be interested in co-authoring with me and turning this into a real Internet draft and eventually RFC.

First published on April 22nd 2008 at http://www.jhsoft.com/dns-xqid.htm