shawn@home:~/blog >_

Writing a DNS Resolver From Scratch (Part 1)

20 Jan 2022

EDIT: I’ve discontinued this series because I’ve frankly just lost interest and am focused on other things.

If you haven’t already, I highly recommend you read “An Introduction to DNS” and “Writing Sub-Byte Data in C” before continuing. DNS was first described in RFC 882, 883, and 973, and the current DNS specification is detailed in RFC 1034 and 1035; it is also recommended you give these RFCs a read. In pursuit of a basic DNS resolver implemented in C, this writeup will be staying consistent with RFC 1034 and 1035.

Contents

• Objective
• Resolvers vs Recursive Servers
• Inspecting a DNS Query
  • DNS Format
  • DNS Headers
  • DNS Questions
• Creating a DNS Query From Scratch
  • Creating the Header
  • Creating the Body
  • C Sockets
  • Response Observation
• Part 2: Interpreting Responses

Objective

The goal of this writeup is not to create a complete, robust, all-edge-cases-accounted-for implementation of a fully-fledged DNS name server. In fact, it’s not even to implement a typical DNS name server on the Internet that holds records. No, the objective of this writeup is to create a basic DNS resolver from scratch in C that will be able to perform a hardcoded DNS lookup, going through a series of iterative queries with DNS name servers on the Internet to interpret, communicate, and process data sent and received.

Why? Well, for educational purposes, of course! Our motivation today is to understand what DNS looks like from the perspective of a resolver. By implementing it from scratch, we gain a deeper-level understanding of the specification. We want our resolver to:

• have a domain to look up, which, for demonstration purposes, will be hardcoded, but in real applications is either received from other processes or in the case of a recursive server, from hosts on the network;
• go through a series of iterative queries to finally get the IPv4 address associated with a domain;
• and communicate the final IPv4 address to the user.

Note that the scope for this writeup is restricted to IPv4. This is not the case in real life.

Resolvers vs Recursive Servers

In “An Introduction to DNS”, I briefly talked about how DNS can be set up on a local host and/or network. Recall that a resolver that exists at the network level, with whom local hosts on the network communicate with through their own local host stub resolvers, is referred to as a recursive server. Thus, recursive servers are just resolvers shared by the network. At this level, I may interchangeably use the terms “recursive server,” “resolver,” and “local name server.” While there are differences later on at where this software is run, there is no meaningful difference at the level of this writeup.

Inspecting a DNS Query

With Wireshark, we can inspect DNS queries that are generated when we perform an action that utilizes DNS, such as visiting a website with a web browser or SSHing into a server using a domain. The following is a DNS query generated from opening up a browser and visiting shawnd.xyz.

DNS Format

This is consistent with RFC 1035. Both RFC 883 and 1035 reference a format for DNS messages, with RFC 1035 describing it in section 4.1:

All communications inside of the domain protocol are carried in a single format called a message. The top level format of message is divided into 5 sections (some of which are empty in certain cases) shown below:

    +---------------------+
    |        Header       |
    +---------------------+
    |       Question      | the question for the name server
    +---------------------+
    |        Answer       | RRs answering the question
    +---------------------+
    |      Authority      | RRs pointing toward an authority
    +---------------------+
    |      Additional     | RRs holding additional information
    +---------------------+

DNS Headers

What we see in the query are the header and question. The header itself is defined in RFC 1035 section 4.1.1:

The header contains the following fields:

                                    1  1  1  1  1  1
      0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                      ID                       |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |QR|   Opcode  |AA|TC|RD|RA|   Z    |   RCODE   |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    QDCOUNT                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    ANCOUNT                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    NSCOUNT                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    ARCOUNT                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Summarizing, the individual sections are:

DNS Questions

The question section is defined in RFC 1035 section 4.1.2:

The question section is used to carry the “question” in most queries, i.e., the parameters that define what is being asked. The section contains QDCOUNT (usually 1) entries, each of the following format:

                                    1  1  1  1  1  1
      0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                                               |
    /                     QNAME                     /
    /                                               /
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                     QTYPE                     |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                     QCLASS                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Summarizing, the individual sections are:

* This is in the format [1 B label length n][n B label] and always terminates with the root label (null). No padding is used.

In hexadecimal, the query was:

42 6a 01 00 00 01 00 00 00 00 00 00 06 73 68 61 77 6e 64 03 78 79 7a 00 00 01 00 01

Let’s break that down. The header section is a fixed length of 12 bytes. Therefore, our header is:

42 6a 01 00 00 01 00 00 00 00 00 00

ID........... 0x426a
QR........... 0 (query)
OPCODE....... 0 (standard query)
AA........... 0 (N/A, 0 because this is not a response)
TC........... 0 (this message was not truncated)
RD........... 1 (request the name server to use recursion)
RA........... 0 (N/A, 0 because this is not a response)
Z............ 0
RCODE........ 0 (N/A, 0 because this is not a response)
QDCOUNT...... 1 (we have 1 question)
ANCOUNT...... 0 (N/A, 0 because this is not a response)
NSCOUNT...... 0 (N/A, 0 because this is not a response)
ARCOUNT...... 0 (N/A, 0 because this is not a response)

The question section is the remainder of our message. Therefore, our question is:

06 73 68 61 77 6e 64 03 78 79 7a 00 00 01 00 01

We first start with the QNAME until we reach the root label. 06 denotes a label length of 6, and 73 68 61 77 6e 64 is just hex for shawnd. The next label has a length of 03 and is 78 79 7a (xyz). The next label has a length of 00, meaning that we’ve hit the root. Therefore, our label is shawnd.xyz..

QNAME....... shawnd.xyz.
QTYPE....... 1 (IPv4)
QCLASS...... 1 (Internet)

QTYPE values are described in RFC 1035 sections 3.2.2 and 3.2.3. QCLASS values are described in RFC 1035 sections 3.2.4 and 3.2.5.

Cool, now we know the format for a typical DNS query! Note that all of this happens over UDP. At this point, we can start writing queries in C.

Creating a DNS Query From Scratch

We first start off with our includes and definitions. We use <arpa/inet.h> for all things networking and <string.h> for some string operations when creating the body later on. We additionally need <stdlib.h> for some memory operations. As always, we’ll use <stdio.h> for input and output:

#include <arpa/inet.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define FQDN "shawnd.xyz."
#define ROOT "198.41.0.4"

/* Header options. */
enum
{
	ID      = 0x426a,
	QR      = 0,
	OPCODE  = 0,
	AA      = 0,
	TC      = 0,
	RD      = 1,
	RA      = 0,
	Z       = 0,
	RCODE   = 0,
	QDCOUNT = 1,
	ANCOUNT = 0,
	NSCOUNT = 0,
	ARCOUNT = 0,
};

ROOT is a root DNS name server. How does the resolver know the root name server IP? Simple: it’s pre-communicated. You can find a full list of root servers here: IANA.

Creating the Header

Now we can write our header:

/* Create a DNS query message header. */
char *create_header(int id, char qr, char opcode, char aa, char tc, char rd, char ra,
	char z, char rcode, int qdcount, int ancount, int nscount, int arcount)
{
	char *header = (char *)calloc(12, sizeof(char));

	/* ID. */
	header[0] = (id & 0xFF00) >> 8;
	header[1] = id & 0x00FF;

	/* QR, OPCODE, AA, TC, RD. */
	header[2] = qr;
	header[2] = (header[2] << 4) | opcode;
	header[2] = (header[2] << 1) | aa;
	header[2] = (header[2] << 1) | tc;
	header[2] = (header[2] << 1) | rd;

	/* RA, Z, RCODE. */
	header[3] = ra;
	header[3] = (header[3] << 3) | z;
	header[3] = (header[3] << 4) | rcode;

	/* QDCOUNT. */
	header[4] = (qdcount & 0xFF00) >> 8;
	header[5] = qdcount & 0x00FF;

	/* ANCOUNT. */
	header[6] = (ancount & 0xFF00) >> 8;
	header[7] = ancount & 0x00FF;

	/* NSCOUNT. */
	header[8] = (nscount & 0xFF00) >> 8;
	header[9] = nscount & 0x00FF;

	/* ARCOUNT. */
	header[10] = (arcount & 0xFF00) >> 8;
	header[11] = arcount & 0x00FF;

	return header;
}

If you’re confused, I’d recommend you give “Writing Sub-Byte Data in C” a read.

Creating the Body

The next step is to write our body. Writing the body is going to be a little bit trickier.

/* Create a DNS query message body. */
char *create_body(char *fqdn, int length, int qtype, int qclass)
{
	int n = 0;
	char *body = NULL;

	/* Body size should be enough for the labels, lengths, QTYPE, and QCLASS. */
	n = length+5;

	/* Allocate the body. */
	body = (char *)calloc(n, sizeof(char));

    /* QTYPE, QCLASS. */
	body[n-4] = (qtype & 0xFF00) >> 8;
	body[n-3] = qtype & 0x00FF;
	body[n-2] = (qclass & 0xFF00) >> 8;
	body[n-1] = qclass & 0x00FF;

	/* Make all labels and their lengths. */
	for (int i = 0, n = 0; i < length; i++)
	{
		if (fqdn[i] == '.')
		{
			body[n] = i-n;
			memcpy(body+n+1, fqdn+n, i-n);
			n = i+1;
		}
	}

	return body;
}

Take a moment to read through the logic of that. The logic is actually easier to follow than it seems at first glance.

With both these functions created, we can now integrate them into the main function to form the full message.

int main()
{
	char *header = create_header(ID, QR, OPCODE, AA, TC, RD, RA, Z, RCODE,
		QDCOUNT, ANCOUNT, NSCOUNT, ARCOUNT);
	char *body = create_body(FQDN, strlen(FQDN), 1, 1);
	char *message = (char *)calloc(12+strlen(FQDN)+5, sizeof(char));

	memcpy(message, header, 12);
	memcpy(message+12, body, strlen(FQDN)+5);

	return 0;
}

C Sockets

The next part scares most people, but I promise it’s actually a lot easier than it seems: sockets. Sockets in C can be daunting at first but they’re actually fairly intuitive once you get the hang of it. We first start off by making some structures, a descriptor, and a length buffer:

struct sockaddr_in ns;    // Address structure for the name server.
struct timeval timeout;   // Time structure for the timeout.
int sockfd  = 0;          // Socket file descriptor.
int socklen = 0;          // Socket length (used later).

Then, we define our destination:

ns.sin_family       = AF_INET;           // IPv4.
ns.sin_addr.s_addr  = inet_addr(ROOT);   // Turn "198.41.0.4" into an Internet address.
ns.sin_port         = htons(53);         // htons - host to network short; 53 is the port.

Now, we can define the length of the socket and timeout parameters. Let’s go for a 60-second timeout:

socklen = sizeof(ns);   // This will get used later.

timeout.tv_sec  = 60;
timeout.tv_usec =  0;

At this point, we can create the socket and set the socket options:

sockfd = socket(AF_INET, SOCK_DGRAM, 0);
setsockopt(sockfd, SOL_SOCKET, SO_RCVTIMEO, (char *)&timeout, sizeof(timeout));

The specification for socket is:

int socket(int domain, int type, int protocol);

We have created an IPv4 UDP (AF_INET, SOCK_DREAM, respectively) socket. As protocol is 0, the system will select the default protocol for the domain/type.

The specification for setsockopt is:

int setsockopt(int socket, int level, int optname, const void *optval, int optlen);

The specification for setsockopt is a tad bit more complex, but not by much. We are setting the options for the socket at sockfd, with SOL_SOCKET meaning that the options will be set at the socket level, SO_RCVTIMEO meaning that we’re setting the timeout, and the last two arguments are obviously the timeout and the length of the timeout. This, well, sets the timeout.

At this point, we have all the logic necessary to send with sendto, whose specification is:

ssize_t sendto(int socket, const void *message, size_t length, int flags,
	const struct sockaddr *dest_addr, socklen_t dest_len);

Thus, we’d write:

sendto(sockfd, message, 12+strlen(FQDN)+5, 0, (struct sockaddr *)&ns, socklen);

If it returns a negative value then that signifies an error. We’ll also have to receive the response with recvfrom, whose specification is:

ssize_t recvfrom(int socket, void *restrict buffer, size_t length, int flags,
	struct sockaddr *restrict address, socklen_t *restrict address_len);

Thus, we’d write:

recvfrom(sockfd, buff, 1024, 0, (struct sockaddr *)&ns, &socklen);

We’d of course have to create a new buffer for this, which is no problem at all. At this point, we can integrate it into the main function and test it, inspecting the traffic with Wireshark. We won’t receive in C just yet – only observe from Wireshark:

int main()
{
	/* Socket. */
	struct sockaddr_in ns;
	struct timeval timeout;
	int sockfd  = 0;
	int socklen = 0;

	/* Message. */
	char *header = create_header(ID, QR, OPCODE, AA, TC, RD, RA, Z, RCODE,
		QDCOUNT, ANCOUNT, NSCOUNT, ARCOUNT);
	char *body = create_body(FQDN, strlen(FQDN), 1, 1);
	char *message = (char *)calloc(12+strlen(FQDN)+5, sizeof(char));

	/* Buffers. */
	char buffer[1024] = {0};

	/* Copy the header and body into the message. */
	memcpy(message, header, 12);
	memcpy(message+12, body, strlen(FQDN)+5);

	/* Define the destination. */
	ns.sin_family       = AF_INET;
	ns.sin_addr.s_addr  = inet_addr(ROOT);
	ns.sin_port         = htons(53);

	/* Define the socket length and timeout. */
	socklen = sizeof(ns);
	timeout.tv_sec  = 60;
	timeout.tv_usec =  0;

	/* Create the socket and set options. */
	sockfd = socket(AF_INET, SOCK_DGRAM, 0);
	setsockopt(sockfd, SOL_SOCKET, SO_RCVTIMEO, (char *)&timeout, sizeof(timeout));

	/* Send the query. */
	if (sendto(sockfd, message, 12+strlen(FQDN)+5, 0, (struct sockaddr *)&ns, socklen) < 0)
	{
		puts("Error encountered when sending query!");
		return -1;
	}

	return 0;
}

Response Observation

The query is successful, and we observe the response:

It goes on for quite a bit…

Part 2: Interpreting Responses

At this point, we’ve successfully created a single DNS query that receives a DNS response. In the next installment in this series, we will be interpreting DNS responses.

Happy hacking!