Windows does have /dev/random

You know, I spent too many years reading Slashdot. I somehow got the impression that Windows did not have a good source of cryptographically strong pseudo-random numbers. While true for Windows 95 and Windows 98, this has not been true for years.

Microsoft Windows has had, since Windows 2000, a form of /dev/random/ called CryptGenRandom(). Indeed, it appears that MinGW/Msys have the required wincrypt.h header file for supporting this function.

I will have to, once I get the DNS resolution bugs fixed, set things up so Deadwood uses CryptGenRandom() for some of the entropy for random query IDs and ports, and not require a secret file.

On CNAME records

I thought handling incomplete CNAME records would be really easy once I had support for glueless NS referrals.

I was wrong.

I can understand why DJB took some shortcuts with CNAME records in DJBdns. CNAME handling is pretty much the last thing I’m adding support for in Deadwood, MaraDNS 2.0’s recursive resolver. It’s like I have been running a 40 kilometer marathon and I’m within 50 meters of the finish line. I just want to run as fast as possible to the finish line and end the marathon.

So, yeah, I’m making some shortcuts with CNAME referrals. DJB has it so that CNAME records are not stored at all in the cache. Deadwood right now stores CNAME records in the cache, but only when the CNAME record is completed. For example, if I ask for up.nytimes.com, which is right now an incomplete CNAME record that points to up.about.akadns.net, Deadwood stores the completed version of up.nytimes.com with the IP for up.about.akadns.net in the entry for up.nytimes.com, but only when we get all of the information.

In addition, the CNAME records before the final answer (up.nytimes.com in the above example) have a fixed TTL of 60 seconds (which doesn’t mean anything); the final answer has a fixed TTL of 3600 seconds (one hour).

Right now, incomplete CNAME records only work if the record the incomplete CNAME points to is already in the cache. Resolving this is hopefully easier than getting CNAME records already in the cache working was; I think I have mostly done this when I got glueless NS referrals to work.

Another thing: If the resolution of an incomplete CNAME record is needed to handle a glueless record, the resolved record will not be used to help solve the parent query that needed the glueless record until that query is sent to Deadwood again. I may or may not fix this before releasing MaraDNS 2.0.

OK, back to finishing up incomplete CNAME referral support. I will hopefully have Deadwood 2.6.04 out in a few days.

chain_id actually will not work

Thinking about it some more, chain_id will not work. The problem is this: Let us suppose we have the following process for resolving example.com:

• The root servers at 127.0.1.1 says the .com servers are at 127.0.1.2
• The .com server at 127.0.1.2 (ns.com) says the example.com server is ns1.example.net
• The root server at 127.0.1.1 says the .net servers are at 127.0.1.3
• The .net server at 127.0.1.3 says the example.net server (ns2.example.net) is at 127.0.1.4
• The ns2.example.net server at 127.0.1.4 says the ns1.example.net server is at 127.0.1.5
• The ns1.example.net server at 127.0.1.5 says that example.com is at 127.0.1.6

Let us suppose that we, at the same time, ask for both example.com and ns1.example.net.

We will now have ns1.example.net in the process of being resolved; this process continues when we get the glueless NS referral ns1.example.net in the process of resolving example.com.

So, at this point, the example.com resolution process has its own chain_id (lets make it “1”) while the process to resolve ns1.example.net has another chain_id (lets make it “2”). For our “use chain_id to stop resolution loops” idea to work, both resolutions now need the same chain_id. Since these chains can be fairly long and since multiple resolutions (such as resolving “www.example.com”, “blog.example.com”, and “ftp.example.com”) can use the same glueless resolution, we potentially might have to change a number of different chain_id values.

This is getting hairy.

It is far simpler to not use chain_id. We can stop loops by simply using recurse_depth; if recurse_depth exceed 32, we give up on solving a given query. Every time we follow a glueless NS referral or an incomplete CNAME chain, we either:

• Create a new resolution process with its recurse_depth being the “parent”’s recurse_depth + 1
• Connect to an already existing resolution process; when this happens, we increment both the parent’s and child’s recurse_depth.

Doing things this way is far simpler than trying to use chain_id.

Another thing: We need to add a “ns” dw_str to the resolution process; this will store the particular glueless ns record we are in the process of resolving.

(As an aside, the latest Deadwood snapshot can resolve glueless NS referrals if the A record in question is already in the cache)

How Deadwood will do glueless NS referrals

“Glueless NS referrals” is when a DNS servers gives us the name, but not the IP, of a given DNS server which is “closer” to the answer we seek.

In order to handle glueless NS referrals, we will have to perform some recursion to resolve them. Since Deadwood uses the select() model, the recursion has to be handled by hand. In addition, since we do multiple in-flight merging, things are a little more complicated.

Here is my current plan:

• We will add three numbers to each outgoing recursive request: recursion_depth (int; can be 16-bit or bigger), parent_id (int 16-bit or bigger), and chain_id (32-bit)
• recursion_depth is how many times we’ve followed a glueless NS record (or incomplete CNAME referral); if this exceeds 32, we stop.
• parent_id is the ID of the request that needs to be solved before we can continue solving this DNS name. For example, if we ask for www.example.com, and the .com DNS servers tell us, without giving us an IP, that the nameservers for example.com are ns1.example.net and (say) ns2.example.net, we hold the current request, and make the parent ID one solving ns1.example.net. Called “parent_id” because multiple recursion attempts might be trying to solve the same name at the same time, but a given recursion attempt only has a single parent_id
• chain_id This is a unique 32-bit number. When we spawn a “parent” request, we first make sure there isn’t a request already in-flight which would cause a loop. This is done because, when spawning a “parent”, the parent has the chain_id as the “child” request; if we find a request already in-flight with the same chain_id, we consider it a loop and give up.

Glueless NS referrals will be a little complicated to implement with Deadwood, but this is the last major hurdle before we have full recursion (we will also use the same code to handle incomplete CNAME referrals).

Deadwood: Revising the hash structure

Currently, the upstream DNS servers are stored in their own special hash. However, in order to implement full recursion, the upstream/root DNS servers need to be stored in the same hash cached entries are stored in.

However, there are some things different about upstream/root NS referrals in the hash:

• They will not be part of the file we store the offline cache in
• The entries will not be part of the queue we use to delete unused entries (and put stuff in the cache diskfile)
• It will not be possible to delete the entries once they are in the hash

My next task for Deadwood is to modify the hash structure to accommodate these “immutable” elements; after that, have upstream_servers and root_servers stored in the hash.

OK, how to store tasks in recursive Deadwood

Since Deadwood is currently a non-recursive cache, we have only one task we perform: We send a DNS query to an upstream server, whose reply we cache and forward on to the end-user.

Since Deadwood only does one task, the structure for remote connections doesn’t need to store what task we’re doing with a remote connection.

This needs to be changed to implement full recursion.

So, let’s add to that structure a “task” element: What we’re doing right now in our process of solving a recursive DNS query.

We can have Deadwood perform the following tasks:

• We are connecting to an upstream DNS server with the RD (recursion desired) bit set. Whatever reply they give us is one we will cache and forward on to the stub resolver. This is currently the only task Deadwood can do. Should the connection fail, or the reply is not a “complete” DNS reply, we will try another upstream server.
  
• We are connecting to a DNS server which is marked as being a possible NS server to our query. The reply is one we may or may not pass on to the client, depending on whether it is a complete reply.
  
• We got an incomplete CNAME referral, which indicates we need to change the name of our query to whatever name was at the end of the incomplete referral and do a new query
  

Tasks will be stored as a stack. The first taks we will have is to connect to the “lowest” NS server we have an entry for. Here is how our remote query will look:

Main -> Non-recursive NS server connect (solve client query).

Should we need to resolve the IP for a glueless NS server, here is how the above task list will then look like this:

Main -> Non-recursive NS server connect (solve glueless IP) -> Non-recursive NS server connect.

If, when trying to solve the glueless IP, we need to solve an incomplete CNAME referral:

Main -> Non-recursive NS server connect (solve incomplete CNAME referral) -> Non-recursive NS server connect (solve glueless IP) -> Non-recursive NS server connect (solve client query)

OK, looking at this, our task will always be trying to make a non-recursive NS server connection. However, we need to store why we’re making this query (client query, glueless IP, or incomplete CNAME referral).

So, we’ll keep the SOCKET, remote_id and the time-to-die, as well as a pointer to the local queries for this query and the initial local query in the “root node”. However, the number of retries as well as the query we’re doing to store this particular task, as well as the list of NS servers we will try to connect, and the number of times we will try before giving up, need to be stored in a special “task” structure which will be stored as a stack pointed to by the “root” DNS query.

More on how recursion is done

Recursion will be done in Deadwood as follows:

• We look for a record in the cache with the same name and type as the stub resolver requested.
  
• If not found, we will look for a CNAME referral with the same name as what the stub resolver requested
  
• If not found, we will look for a NS referral with the same name as what the stub resolver requested
  
• If not found, we will lop names off of the front of what they requested as a NS referral until we find something in the cache
  

When we find a CNAME referral, we change the name of what we request to be the final name in the CNAME referral, note that we had this CNAME referral, and continue processing.

When we find a NS referral, we use a NS server at random. If the server is glueless, we will have to find out the IP address of the NS server before proceeding. To hand glueless records, we note the list of NS records as the current step in the recursive process, look up the glueless record, and then continue as before.

I will discuss how to store this entire process in a future blog entry.

How Deadwood stores pending remote connections

To implement full recursion, I will have to do an overhaul of how Deadwood stores pending remote connections. In more detail: A pending local connection is when a DNS stub resolver sends a query for Deadwood and is waiting for a reply. A pending remote connection is when Deadwood sends a DNS query to another DNS server and is waiting for a reply.

Here is the structure for basic UDP remote connections:

typedef struct {
        SOCKET socket; 
        int64_t die;
        uint16_t remote_id; 
        int retries; 
        dw_str *query;
        uint16_t num_locals; 
        local_T **local; 
} remote_T;

Note that, in the actual source code, this is commented. To expand on the comments:

• socket is the number for open socket which will get the UDP data. It’s called a “SOCKET” here because Windows, unlike UNIX, doesn’t use integers for sockets.
  
• die is a timestamp for when this connection will be timed out and needs to be discarded. Note that this is a 64-bit number; Deadwood uses 64-bit timestamps to minimize Y2038 problems
  
• remote_id is the 16-bit randomly created query ID generated by Deadwood using a cryptographically strong pseudo random number generator. If the reply doesn’t have the same query ID, it might be a DNS spoof attempt.
  
• retries is the number of remaining times we will retry if the remote server doesn’t reply to our query when it runs out of time (when our time is the same or greater than the die time)
  
• query is the query (name, DNS record type) we sent to the remote server; we keep a copy of it here because we need to make sure the query we get is the same as the query we sent them (again, to make spoofing harder).
  
• num_locals is the number of local connections we send an answer to once we get a reply from the upstream server. This was added when I implemented the merging of multiple in-flight requests with the 2.4.07 release of Deadwood (August 31, 2009). When one program asks for, say, www.google.com and another program or computer asks for www.google.com while we’re still waiting for the first reply, Deadwood will merge the second request in to the first request, and send the reply to both clients once we get the reply upstream.
  
• locals is a list of “local” connections (which can be either UDP or TCP connections); there are the connections we send a reply to downstream once we get a reply upstream
  

Now, this structure is a simple structure which is fine when the upstream server does the heavy lifting and we’re just caching and forwarding the reply they send us, but this will need to become a lot more fancy in order to make full recursion a reality.

I will discuss what changes I plan to make to this to make recursion possible in a future blog entry.

New Deadwood snapshot: NS referral format revised

I have slightly revised the format of a NS referral in the second Deadwood snapshot for today. In the revised NS referral, we start off the string describing the NS referral with a single DNS label (DNS name) describing where in the DNS space the referral string points to (whether this packet should point to NS servers for all of the .com records, the google.com NS servers or what not).

Besides this, the format of a NS referral is identical.

How Deadwood will store the referral types

As I mentioned in my last Deadwood blog entry, I will create some new types so Deadwood better supports recursion. Types 0, 1, and 2 (“complete” DNS answers; in other words answers that can be sent to a stub resolver) will be stored in the same manner Deadwood 2.4 stores them (the DNS packet, a list of offsets of the records in the packet, AN/NS/AR counts, and finally the “type” byte).

However, CNAME referrals (type 17 replies) and NS referrals (type 16) will be stored somewhat differently. A CNAME referral will be stored as a list of DNAME records in the following format:

{length}{DNAME}

{length} will be a signed 16-bit integer. {DNAME} will be a raw DNS name (samiam.org will be \x06samiam\x03org\x00). After this list, we will have the following three bytes

{final offset}\0x11

The final offset will be an unsigned 16-bit integer with a pointer to the beginning of the final DNAME entry.

A NS referral will be stored as follows:

{type (A, AAAA, or name)}{data}

Type will be an eight-bit number which can be either A (1), AAAA (2), or name (3). The type determines the data; an A NS referral is a 4-byte IPv4 IP, an AAAA NS referral is a 16-byte IPv6 IP, and a “name” type will be a DNAME with the glueless NS referral.

After all of the NS referral, we will have a list of unsigned 16-bit offsets pointing to the NS referrals in the string, followed by a signed 8-bit number with the number of NS referrals (Deadwood ignores NS records after the first 16 records), followed by the \x10 byte indicating that this record is a NS referral.

Some more thoughts on Deadwood’s “Type”

I’ve been thinking some more about Deadwood’s type byte, which I discussed in the last blog entry. The reason why the only thing the type byte notes is whether the NXDOMAIN bit is set is because, when I was making Deadwood a simple DNS cache that treats DNS data, as much as possible, like a “black box”.

For a caching-only DNS program, we don’t care what’s in the packet except to decide how long to cache it. We only used the type byte because it was the only place I could store the NXDOMAIN bit in the header.

There’s a lot of confusion about the NXDOMAIN bit, and, as DJB has pointed out, a lot of naive DNS implementations get it wrong. The NXDOMAIN bit in the DNS header indicates that not only isn’t there a DNS entry for this name with this record type, there is no DNS entry for this name for any record type. You can also have a simple DNS “not there” reply, which is a DNS record without the NXDOMAIN bit set, but in the format of a NXDOMAIN: No answer in the AN section, and a SOA record in the NS section.

So, in reality, we have positive DNS answers, and we have two types of negative DNS answers: “Not there” DNS replies, and NXDOMAINs.

Deadwood currently treats “not there” and positive answer DNS replies the same: Both DNS replies are passed as-is on to the client. They are both type 0 (answer to pass on to the client without setting the NXDOMAIN bit) replies.

Now that we are doing a deeper inspection of DNS packets, I would like to change that. I would like to have positive replies distinguished from non-NXDOMAIN “not there” replies, and require a reply with the NXDOMAIN bit set to be, in fact, a NXDOMAIN reply.

So, my revised list of types:

• Type 0: Positive answer
• Type 1: NXDOMAIN negative reply
• Type 2: Non-NXDOMAIN negative reply
• Type 16: NS referral
• Type 17: CNAME referral
• Type 18: All known servers timed out last time we tried to get this data

The reason for the revised numbering scheme is that I would like types 0-15 to be set aside for replies we pass on to the client, with 16-31 used for data which means we have to do more work to find an answer. Type 18 will let us know to be more patient with the servers (maybe they’re just really flaky), and even allows there to be framework to have Deadwood periodically try to contact these servers just in case it’s a case of the servers being offline whenever the admin unplugs the server to plug in the fridge to cool down the beer (note: I’ll probably not implement this).

The format of packets in the cache

The last byte of a cache entry for Deadwood is a single “type” byte (also called “is_nxdomain” in the source code). This is an unsigned 8-bit value; right now only two values are used for this:

• 0, which indicates that it is a complete answer to our DNS question, and the NXDOMAIN bit in the header is not set (NXDOMAIN means “thisf host does not exist for any record type”)
• 1, which indicates that it is a complete answer to our DNS question, with the NXDOMAIN bit in the header set to 1 (which means, but Deadwood won’t use this, that no other host names exist for this query)

With eight bits to play with there, we can use this type to indicate various records which, while not complete DNS answers, are useful for a recursive DNS server

• Have type 2, which is a NS referral. A NS referral can be any combination of glued and glueless NS records. NS records with A or AAAA (IPv4 or IPv6) glue that we can use is converted in to the A and AAAA addresses we get from the glue records; NS records without glue are kept only as names (speaking of glueless, I am a pretty hard critic of DJB, but I am glad we got A6 and DNAME killed)
• Have type 3, which is an incomplete CNAME referral; this thing can be a CNAME chain if the upstream server gave us a CNAME chain

I will discuss the binary format of type 2 (NS referral) and type 3 (CNAME referral) records in a future blog.

New Deadwood snapshot: Bailiwick check done

Yes, I am getting married this week. However, I was able to get a little time to devote to Deadwood, and have just made a new Deadwood snapshot. In today’s snapshot, I have taken all of the Bailiwick checking code I wrote last week and have integrated it with the rest of the code which scans a DNS packet.

Right now, the DNS packet scanning does the following:

• It looks at the AN (answer) section of the DNS reply. Anything that is not either a direct answer to our query or part of a CNAME chain leading up to our answer is marked “RRX_IGNORE”.
• If there are any records in the AN section of the DNS reply, we mark as “RRX_IGNORE” all records in the NS and AR section of the DNS reply
• If there is no answer (AN) section, we look at the NS and AR sections
• We verify that all NS records are in-Bailiwick (as described in previous blog entries)
• We then look at records in the AR (glue records) section; any IPv4 and IPv6 records are compared to NS referrals in the NS section; if a given glue record corresponds to a NS record, we mark the glue record as “Glue for NS record number X”, where X is a number from 1 to 16 (we only support the first 16 NS records), and note that the NS record in question has IPv4 or IPv6 glue
• At this point, all NS records are marked as being either out of bailiwick, glueless, with only IPv4 glue, with only IPv6 glue, or with both IPv4 and IPv6 glue

Next: Based on this information we have gotten, figure out what to do next (whether we have our answer, whether this is a CNAME referral, or give the list of NS server to go to, either as glueless records or as a list of IPs).

Timeline: I’m getting married Friday, guys.

New Deadwood snapshot

I posted a new Deadwood snapshot last night where I have begun work on the bailiwick checks. My plan for the bailiwick check, which I will do next week, is as follows:

• Look at what the NS record points at and the query sent by the client.
• If they are the same, go to the next part of the bailiwick check.
• Remove one label from our query (make www.example.com example.com or make example.com simply .com, or make .com the name of the root server)
• See if they are the same; if they are we pass this part; if not, keep lopping off labels until we match or the query is less than zero-length (fail, exit routine)

Part two:

• Let’s get the Bailiwick for this query (if this NS record was told by us upstream that these are records for .org; the bailiwick is .org; if this is a root server, tha bailiwick is any querty; if this NS record was told by us upstream this is for example.com, the bailiwick is example.com, and so on)
• Let’s remove one label from the NS record given to us
• Let’s compare the NS record with the bailiwick this NS record has
• If they are the same, we’re gold and have passed the bailiwick check
• Otherwise, remove labels from the NS record and compare with the bailiwick until we either get a match or the truncated NS record is shorter than our bailiwick. If we get a match, it’s gold, otherwise it’s out-of-bailiwick