wiki:RecursiveQueryLogic

BIND10 Validating Recursive Resolver Notes

Unmet prerequisites for a validating recursive resolver:

Decisions to make:

  • We need a fast mechanism for passing packets from process to process, OR, we need to agree that all query services should be handled by a single process. Serving a single query may involve multiple switches back and forth between authoritative and recursive lookup, and if the context switching isn't very efficient, this is likely to have a significant performance impact.
  • We need to settle on a crypto library (OpenSSL? Crypto++? Other?)

Code to write:

  • ACL
  • TSIG
  • Cache; must be fast, should be searchable by exact match or closest match
  • Something like BIND 9's adb (address database)
  • Pseudorandom number generator (may come from crypto library)
  • A "DNSSEC Key" object, with a method for validating signed data
  • Some sort of task/event processing mechanism (ASIO?)
  • Dispatch: A means of sending out queries to delegated name servers, using random src-port/TXID, identifying the responses when they arrive and passing them back to the resolver context in which they originated.

High-level overview of recursion

Initial Preparation:

Read a packet; check it for general validity; if it is not valid DNS, exit.

Parse the packet. If it is an update, notify, or XFR query, pass it to the appropriate module, and exit. If it is a response which matches a current resolver query, go to RESUME. If it is not a query, exit.

If the packet contains an EDNS OPT RR, handle it: set size limits for the response, note whether DO is set, etc.

If the packet has a TSIG option, determine whether the packet is validly signed by a known TSIG key. If so, make note of the key.

Check the query ACL against the srcaddr/srcport/dstaddr/dstport/key. If it does not match, exit.

Allocate space for a response message; copy the question into it.

If the server is configured to support recursive queries, check the recursion and cache-query ACLs; make note of the results. If the client is allowed to recurse, set the RA bit in the response. If the client is not allowed to recurse, clear the RA bit.

LOOKUP:

Attempt to answer the query as an authoritative server (as BIND 10 does now). If a full authoritative answer can be given for the requested name, set the AA bit, and go to ANSWER.

If the client is not allowed to query the cache, go to ANSWER.

Search the cache for an exact match on QNAME/QCLASS/QTYPE or QNAME/QCLASS/CNAME. If found (and still within TTL, and flagged as either validated or not secure), add it to the answer; if the rrset found is a CNAME but QTYPE wasn't, then change QNAME to the CNAME target and go to LOOKUP.

If we have a complete answer now, or if recursion was not requested or permitted, go to ANSWER.

Check to see if the data from the authoritative data source contains a delegation; if not, or if so but the delegation is not to the immediate parent of QNAME, then search the cache for an NS rrset that matches closer. If no delegation is found using either of these methods, use root hints, generate a priming query, get a fresh ./NS RRset, and delegate to that.

RESQUERY:

For each name server in the NS rrset to which we're delegating, set up a list of addresses. Round robin through the addresses, sending DNS queries for QNAME/QCLASS/QTYPE (using random srcport and txid, and keeping track of them). Send out the query and exit (we will resume processing after receiving the response packet).

RESUME:

We have received a response to an outstanding resquery. If we have a complete answer, go to ANSWER. If we have an answer with an incomplete CNAME chain, reset QNAME to TARGET and go to LOOKUP. If the response contains a delegation, go to DELEGATION.

DELEGATION:

If the answer contains a secure delegation, validate and cache it (if there is no DNSKEY for the current zone in cache, send a query to the nameserver to obtain that, then validate and cache it, before validating and caching the DS). Cache the NS and address data as glue. Switch to the delgated name server, and go back to RESQUERY.

ANSWER:

Validate all the signed RR's in the answer data we've acquired; if validation fails, return a SERVFAIL, otherwise cache the data as secure. Cache glue at a lower trust level. Render the answer to wire format; if it is incomplete, just put in what we have. Send the answer to the client, and exit.

Steps for validating a signed RRset

  • Is the name that is being validated under a configured trust anchor? If not, mark the zone insecure and stop validation.
  • Is lookaside validation configured?
    • If not, mark the zone as insecure and stop validation.
    • Otherwise, concatenate the DLV zone name and the apex of the current zone and search the cache for a DLV record of the resulting name. If a DLV record is not in the cache, start a fetch to retrieve it, and validate and cache the response. If the DLV record does not exist, mark the zone as insecure and stop validation. If it does, use it in place of the parent DS record.
  • Search the cache for the zone apex's DNSKEY. If present, go on to the next step. Otherwise, start a few fetch to get it. If the DNSKEY RRset contains a key which matches either a validated parent DS, a validated DLV record, or a configured trust anchor, then validate the DNSKEY RRset against that key. If valid, cache it.
  • Using the cached DNSKEY RRset, validate the RRset

Timeline for a recursive query

  • Packet is sent by client, requesting QNAME/QTYPE, QR=0, RD=1, CD=0. EDNS0 OPT RR contains DO=1.
  • Packet is received by server.
  • Packet is parsed and determined to be a valid DNS query.
  • EDNS0 OPT RR is parsed. DO status is noted, UDP payload size is noted.
  • Packet is checked for a TSIG RR. If present, signature is checked against known keys. If a match is found, the keyname is noted.
  • The "query" ACL is checked against the packet's source and destination addr/port, and matching key if any. If a match is found, query is permitted.
  • Space is allocated for the answer.
  • Server attempts to answer the query using authoritative data sources (following the algorithm described in AuthServerQueryLogic). There are five possible outcomes:
    1. Complete positive answer: We are authoritative for QNAME, and QNAME/QTYPE exists (or QNAME/CNAME exists, we are also authoritative for TARGET, and TARGET/QTYPE exists). In this case we set CD=0 and AA=1 and return the answer.
    2. Complete negative answer: We are authoritative for QNAME, and neither QNAME/QTYPE nor QNAME/CNAME exist. In this case we set CD=0 and AA=1, add SOA and NSEC records to the authority section, and return NXDOMAIN or NODATA/NOERROR.
    3. Incomplete answer: We are authoritative for QNAME, but QNAME/CNAME exists and we are *not* authoritative for TARGET. In this case we reset QNAME to TARGET, set AA=1, and proceed to the next step.
    4. Delegation: We are *not* authoritative for QNAME, but we *are* authoritative for an ancestor of QNAME, and we can return a delegation to a closer zone. In this case we proceed to the next step.
    5. Zone not found: We are not authoritative for QNAME. In this case we proceed to the next step.
  • The "query-cache" ACL is checked. If a match is not found, querying the cache is not permitted; we return as much of the answer as we have.
  • The "recursion" ACL is checked. If a match is found, set RA=1 in the response, and note that recursion is permitted.
  • We search the cache for an exact match on QNAME/QTYPE. If found (and the data is within TTL and is flagged as authentic), add it to the answer. If not found and QTYPE != CNAME, search the cache for QNAME/CNAME; if found, add it to the answer; reset QNAME to TARGET and repeat the search until data is found matching QTYPE, OR until a cache miss occurs.
  • If a complete answer has been found, return it.
  • If the information we have collected so far does NOT include a delegation to another name server, then search the cache for the NS RRset with the closest match to QNAME. If the answer we have now DOES include a delegation, but it is not the direct parent of QNAME, search the cache for an NS RRset that matches more closely. If found, replace the delegation with that NS RRset.
  • If no NS record has been found at this point, use the root hints, and send a new query for "./NS"; delegate the query to the resulting NS RRset.
  • For each server in the NS RRset, check the cache for a matching address. (This must be done even if glue was returned from the authoritative data source, because the cache may have more accurate address data. It can be skipped if we used the root hints. For any name server which did not have address glue supplied, we have to start a new lookup to obtain it.)
  • Pick a server address and send a it a query for QNAME/QTYPE. Wait for a reply. If a reply doesn't come soon enough, send the same query to the next address, and so on.
  • A reply arrives from the delegated name server. There are several possible outcomes:
    1. Reply contains a complete positive answer. We validate and cache the answer, then send it to the client with AA=0.
    2. Reply contains a complete negative answer. We validate and and negatively cache the answer, then send it to the client with AA=0.
    3. Reply indicates a server error. We try again with the next server, until all have been tried.
    4. Reply contains a partial positive answer (i.e., QNAME/CNAME exists but the server is not authoritative for TARGET). We validate and cache the answer, then start a new lookup to find TARGET (this includes searching the authoritative data sources again).
    5. Reply contains a further delegation. We cache it as glue; if it was a secure delegation we also validate and cache the DS. We check the cache for better address data for the given name servers. If necessary, we start a lookup to find address data for the name servers. Then we go back to the delegation step, sending the current query to the delegated name server, repeating until a complete answer has been assembled.
  • Render the answer into wire format, and send it to the original client.

Validation timeline

This is a rough timeline for the recursive query and validation on a freshly-started, non-primed name server, with nothing in cache. The server has been configured as a validating resolver with a trust anchor for the root zone. The test query is for "farside.isc.org".

(Note: This is not exactly how BIND 9 handles this.)

Terminology:

NS(X): The authoritative name server for zone X. KSK(X): The key-signing key for zone X. ZSK(X): The zone-signing key for zone X.

  • Select address for NS(.)
  • Query -> NS(.) for "farside.isc.org/A"
  • Response <- NS(.), authority section contains org/NS, org/DS, org/RRSIG(DS); signed by ZSK(.)
  • Authenticate and cache org/DS:
    • "." is a secure zone (under a trusted key, no insecure delegation)
    • ZSK(.) DOES NOT match the trust anchor
    • Cache does NOT contain "./DNSKEY"
    • Query -> NS(.) for "./DNSKEY"
    • Reponse <- NS(.) contains ./DNSKEY, ./RRSIG(DNSKEY); signed by KSK(.)
    • Authenticate and cache ./DNSKEY:
      • KSK(.) matches trust anchor
      • Validate ./DNSKEY using the trust anchor
      • Cache ./DNSKEY as secure.
    • Verify that ./DNSKEY contains ZSK(.)
    • Validate org/RRSIG(DS) using ZSK(.)
    • Cache org/DS as secure
  • Cache as glue org/NS
  • Cache as glue all name server addresses in the additional section.
  • For any NS RR not represented in the additional section and not in the cache, start fetches for those names' A/AAAA records. Cache as not yet validated.
  • Select address for NS(org)
  • Query -> NS(org) for "farside.isc.org/A".
  • Response <- NS(org), authority section contains isc.org/NS, isc.org/DS, isc.org/RRSIG(DS); signed by ZSK(org).
  • Authenticate and cache isc.org/DS:
    • "org" is a secure zone
    • Cache contains org/DS, secure
    • Cache does NOT contain org/DNSKEY
    • Query -> NS(org) for "org/DNSKEY"
    • Repsponse <- NS(org) contains org/DNSKEY, org/RRSIG(DNSKEY); signed by KSK(org)
    • Authenticate and cache org/DNSKEY:
      • org/DS matches KSK(org)
      • Validate all the keys in org/DNSKEY using KSK(org)
      • Cache org/DNSKEY as secure.
    • Verify that org/DNSKEY contains ZSK(org)
    • Validate isc.org/RRSIG(DS) using ZSK(org)
    • Cache isc.org/DS as secure.
  • Cache as glue isc.org/NS.
  • Cache as glue all name server addresses in the additional section.
  • For any NS RR not represented in the additional section and not in the cache, start fetches for those names' A/AAAA records. Cache as unvalidated.
  • Select address for NS(isc.org)
  • Query -> NS(isc.org) for "farside.isc.org/A"
  • Response <- NS(isc.org) contains farside.isc.org/A and farside.isc.org/RRSIG(A), authority section contains isc.org/NS and isc.org/RRSIG(NS).
  • Authenticate and cache farside.isc.org/A:
    • "isc.org" is a secure zone
    • Cache contains isc.org/DS, secure
    • Cache DOES NOT contain isc.org/DNSKEY
    • Query -> NS(isc.org) for isc.org/DNSKEY
    • Repsponse <- NS(isc.org) contains isc.org/DNSKEY, isc.org/RRSIG(DNSKEY); signed by KSK(isc.org)
    • Authenticate and cache isc.org/DNSKEY:
      • Verify that isc.org/DS matches KSK(isc.org)
      • Validate all the keys in isc.org/DNSKEY using KSK(isc.org)
      • Cache isc.org/DNSKEY as secure.
    • Authenticate and cache farside.isc.org/A:
      • Verify that isc.org/DNSKEY contains ZSK(isc.org)
      • Validate using that ZSK(isc.org)
      • Cache farside.isc.org/NS as secure
    • Authenticate and cache farside.isc.org/NS:
      • Verify isc.org/DNSKEY contains ZSK(isc.org)
        • Validate using that ZSK(isc.org)
        • Cache farside.isc.org/NS as secure
    • Also authenticate and cache any signed glue records
  • Respond to client with farside.isc.org/A in answer and isc.org/NS in authority (plus RRSIGs if DO==1), and AD=1.
Last modified 7 years ago Last modified on Aug 31, 2010, 8:52:58 PM