Writing DNS messages from scratch using Go

Hey,

Yesterday I read a pretty interesting article from James Routley with the title Let’s hand write DNS messages. It goes all the way down to preparing a UDP query by hand and then interpreting it by reading the bytes received back.

That was cool mainly because it makes clear that DNS messages are not all that complicated.

It takes some encoding/decoding to create a message and understand its result but, still, not hard.

I took the opportunity to go through the article and the DNS RFC and then implement myself something similar. The result is cirocosta/rawdns.

Now, to the article.

• Why recreate the wheel?
• The types
• A little bit of digression - getting and set bits in a byte-aligned language
• Asking the questions
• Closing thoughts

Why recreate the wheel?

It’s pretty evident that the work I did is unnecessary. There are great packages for creating DNS servers/clients (like the excellent miekg/dns which I even used in a simple DNS recursive server I wrote (cirocosta/sdns some time ago). If all you need is resolving the IP of a host, just use plain “net”/LookupAddr, it does the job much better than my tool.

The good side of doing though is that I had the opportunity to:

• review some networking concepts
• check out how to do UDP with Go (I had only dealt with UDP in C before)
• review some bitwise operations
• have a more in-depth view of how the DNS protocol works

Should you do the same? Well, maybe.

It’s a common practice to do something similar in a networking class, but in my case, we didn’t do it (had some other assignments).

The types

I started the project by looking at which types I should deal with.

Fortunately, there are just a few.

• DNS Message: the piece that goes in both ways (request and response), always contains the header and then other pieces (like question and RR) depending on the message being a request or response;
• DNS Message - Header: this gives general information about what’s coming in the message, like, how many queries are there … how many answers … what is the ID that identifies this “session” and some other pieces of information. It’s what tells you how to parse what’s coming next and give context to the semantics.
• DNS Message - Question: contains the actual query that you want to perform against a nameserver. It can be of many types and classes; here I just carried about one: A records against recursive servers.
• DNS Message - RR: representation of a resource record (in this case, we can treat it as a plain answer). Regardless of the type, this always comes packed with the same format, but it leaves a field (RDATA) to be parsed after the fact depending on the type.

This translated to the following files in cirocosta/rawdns:

rawdns
└── lib
    ├── header.go               // header
    ├── header_test.go
    ├── message.go              // full DNS msg
    ├── question.go             // question
    ├── question_test.go
    ├── rr.go                   // rr
    └── rr_test.go

As the whole message (message.go) is pretty much a composition of Header, Questions and Answers, I started by making sure that each one of them could be both parsed from a sequence of bytes as well as they could create a sequence of bytes from their definition.

The tricky part is that all the types we have in Go are byte aligned, while some parts of the header section, for instance, take only 3 bits, or 4 bits … some others, just 1bit. This means that we have to fit that kind of information in an 8bit type.

A little bit of digression - getting and set bits in a byte-aligned language

The whole idea of fitting pieces of information in a single byte is very natural to think about as we can easily refer to “this bit of this byte” but some languages (like Go) gives no native interface to that.

Looking at the description of the DNS message header, we have the following description:

        FIRST BYTE                SECOND BYTE
   ----------------------- || ---------------------

     0  1  2  3  4  5  6  7  0  1  2  3  4  5  6  7
   +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
   |QR|   Opcode  |AA|TC|RD|RA|   Z    |   RCODE   |
   +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

The structure can be thought as two bytes which have values placed at different offsets with some maximum values that they can take (given the number of bits that they can hold):

   first_byte:
   {
      QR:      offset=0 , size=1bit
      Opcode:  offset=1 , size=4bit 
      AA:      offset=5 , size=1bit
      TC:      offset=6 , size=1bit
      RD:      offset=7 , size=1bit
   }

   second_byte:
   {
      RA:      offset=0 , size=1bit
      Z:       offset=1 , size=3bit 
      RCODE:   offset=4 , size=4bit
   }

Back in the days in which I used to do some C I remember there was a pretty good way of dealing with this: bit fields. In Go, however, there are no language features that can help us directly (see golang-nuts - Bit fields/binary parsing).

In C this allows us to make use of a struct to represent a byte and then use field access operators to gather these bit values without having to deal with bitwise operations.

What I mean is, suppose that you have a multiplayer game where four players are connected and in your loop, you have to evaluate what’s the next position of each player based on their directions.

We could establish that these directions come in the form of an enum which takes 2bits to represent any direction:

typedef enum direction {
        NORTH = 0,
        EAST,
        SOUTH,
        WEST
} e_direction;

Being a 4-player game, we can store this information in a single byte:

     0  1  2  3  4  5  6  7 
   +--+--+--+--+--+--+--+--+
   |DIR1 |DIR2 |DIR3 |DIR4 |
   +--+--+--+--+--+--+--+--+
     /\
   +-------------------------------+
   | direction of the first player |
   +-------------------------------+

such that in C that would translate two:

typedef struct player_directions {
        unsigned char p1_dir : 2;
        unsigned char p2_dir : 2;
        unsigned char p3_dir : 2;
        unsigned char p4_dir : 2;
} t_player_directions;

so in our loop, we could check the directions by accessing the fields of this 1byte struct:

/* definitions above ... */

int main () {
  t_players_directions directions = {
    .p1_dir = NORTH,
    .p2_dir = NORTH,
    .p3_dir = SOUTH,
    .p4_dir = EAST,
  };

  printf("sizeof(directions)=%ld\n", sizeof(t_players_directions));
  printf("p1_dir=%x\n", directions.p1_dir);
  printf("p2_dir=%x\n", directions.p2_dir);
  printf("p3_dir=%x\n", directions.p3_dir);
  printf("p4_dir=%x\n", directions.p4_dir);

  return 0;
}

/**
 *   $  gcc -o main ./main.c
 *   $  ./main
 *
 *        sizeof(directions)=1
 *        p1_dir=0
 *        p2_dir=0
 *        p3_dir=2
 *        p4_dir=1
 *
 **/

What about Go, then? Bit shifting.

When setting values: set the bits in the right position and then merge it to the value you want them in.

   given that we want to pack it in
   1 byte:

     0  1  2  3  4  5  6  7   ==>  dirs uint8 = 0
   +--+--+--+--+--+--+--+--+
   |DIR1 |DIR2 |DIR3 |DIR4 |
   +--+--+--+--+--+--+--+--+

   assume that we want the following 
   values packed:
   dir1 = 0     ===> 0 0
   dir2 = 0     ===> 0 0
   dir3 = 2     ===> 1 0
   dir4 = 1     ===> 0 1

   then it means that we need to get
   dir1 shifted all the way to the 
   first position, then dir2 to the
   second, dir3 to the third and dir4
   to the forth.

   dirs = 0             - start with 0 0 0 0 0 0 0 0
                        
   dirs |= 0 << 6       - move `00` six times and "merge"

   0 0 0 0 0 0 0 0 
   d1  ----------

   dirs |= 0 << 4       - move `00` four times and "merge"

   0 0 0 0 0 0 0 0 
   d1  d2  -------

   dirs |= 2 << 2       - move `10` two times and "merge"

   0 0 0 0 1 0 0 0 
   d1  d2  d3  ---

   dirs |= 1 << 0       - move `01` 0 times and "merge"

   0 0 0 0 1 0 0 1 
   d1  d2  d3  d4

That in Go code turned out to the following (for the case of the header):

//				0  1  2  3  4  5  6  7
//      0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
//    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
//    |                      ID                       |
//    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
//    |QR|   Opcode  |AA|TC|RD|RA|   Z    |   RCODE   |
//    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
//    |                    QDCOUNT                    |

func (h Header) Marshal() (res []byte, err error) {
	var (
		buf       = new(bytes.Buffer)
		h1_0 byte = 0
		h1_1 byte = 0
	)

        // using `binary.Write` we can take the 16bit
        // int that the ID is made of and have it split
        // in two bytes following big endian order (most
        // significant bit first, less significant second)
	binary.Write(buf, binary.BigEndian, h.ID)

	// first 8bit part of the second row
	// QR :		0
	// Opcode:	1 2 3 4
	// AA:		5
	// TC:		6
	// RD:		7
	h1_0 = h.QR << (7 - 0)
	h1_0 |= byte(h.Opcode) << (7 - (1 + 3))
	h1_0 |= h.AA << (7 - 5)
	h1_0 |= h.TC << (7 - 6)
	h1_0 |= h.RD << (7 - 7)

	// second 8bit part of the second row
	// RA:		0
	// Z:		1 2 3
	// RCODE:	4 5 6 7
	h1_1 = h.RA << (7 - 0)
	h1_1 |= h.Z << (7 - 1)
	h1_1 |= byte(h.RCODE) << (7 - (4 + 3))

	buf.WriteByte(h1_0)
	buf.WriteByte(h1_1)

	binary.Write(buf, binary.BigEndian, h.QDCOUNT)

        // ..
}

When retrieving though, the idea is the same. The only difference this time is that you shift to the right and apply a mask to the remaining bits:

  0 0 0 0 1 0 0 1   current value    
  d1  d2  d3  d4

  how to know what's set for `d3`?

  shift the whole thing to the right by
  two places:

  0 0 0 0 0 0 1 0
  --- d1  d2  d3 

  and then mask the remaining (in this case
                               it's not necessary
                               but I assume we don't
                               know that in advance)
  0 0 0 0 0 0 1 0
& 0 0 0 0 0 0 1 1 
  ---------------
  0 0 0 0 0 0 1 0

  this way we know that at d3 we have `2` as the value.

  i.e.: d3 = (dirs >> 2) & ((1 << 2) -1)

If you’re wondering why (1 << 2) - 1, that’s because we want n places to the right filled with 1s and all the places to the left with 0s such that when we AND them, only the n to the right remain.

0 0 0 0 0 0 0 1     1   = (1 << 1 ) - 1
0 0 0 0 0 0 1 1     3   = (1 << 2 ) - 1
0 0 0 0 0 1 1 1     7   = (1 << 3 ) - 1
0 0 0 0 1 1 1 1     15  = (1 << 4 ) - 1
0 0 0 1 1 1 1 1     31  = (1 << 5 ) - 1
0 0 1 1 1 1 1 1     63  = (1 << 6 ) - 1
0 1 1 1 1 1 1 1     127 = (1 << 7 ) - 1
1 1 1 1 1 1 1 1     255 = (1 << 8 ) - 1

If you’re curious to see how that looks like, check out the method lib/header.go#UnmarshalHeader from cirocosta/rawdns:

//      0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
//    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
//    |                      ID                       |
//    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
//    |QR|   Opcode  |AA|TC|RD|RA|   Z    |   RCODE   |
//    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
//    |                    QDCOUNT                    |
//    .......

func UnmarshalHeader(msg []byte, h *Header) (n int, err error) {
	var (
		h1_0 byte = 0
		h1_1 byte = 0
	)

	// ID is formed by the first two bytes such that
	// it results in an uint16.
	// As this comes from the network in UDP packets we 
        // can assume that it comes in BigEndian (network byte 
        // order), thus, consider the first byte of each,
	// the most significant.
	h.ID = uint16(msg[1]) | uint16(msg[0])<<8

	// take the first byte of the second row (QR, Opcode, AA, TC and RD)
	h1_0 = msg[2]

	// Each value is got from right bitshifting
	// followed by masking such that we end up
	// with only that number.
	// Here we're starting from right to left.
	h.RD = h1_0 & masks[0]
	h.TC = (h1_0 >> 1) & masks[0]
	h.AA = (h1_0 >> 2) & masks[0]
	h.Opcode = Opcode((h1_0 >> 3) & masks[3])
	h.QR = (h1_0 >> 7) & masks[0]

        // ...
}

Once you can recreate messages from a sequence of bytes and write bytes from a structure, you’re ready to start communicating with a real server.

Asking the questions

This is the easiest part (ps.: assuming we’re not entirely implementing all the details of the protocol, like truncating messages when above 512bytes and making use of some security features).

The DNS RFC states:

The DNS assumes that messages will be transmitted as datagrams or in a byte stream carried by a virtual circuit. While virtual circuits can be used for any DNS activity, datagrams are preferred for queries due to their lower overhead and better performance. …

The Internet supports name server access using TCP [RFC-793] on server port 53 (decimal) as well as datagram access using UDP [RFC-768] on UDP port 53 (decimal).

That’s essentially meaning that we should make use of UDP when sending queries and that these queries should be performed against port 53 (by default).

That in Go is translated to a UDP dial:

c.conn, err = net.Dial("udp", cfg.Address)
if err != nil {
        err = errors.Wrapf(err,
                "failed to create connection to address %s",
                cfg.Address)
        return
}

which allows us to write() a sequence of bytes to it and then wait for responses.

The fun thing is that UDP is connectionless. That means that we’re not setting up a full-fledged connection like with TCP, performing ACKS and NACKS all the way to make sure things go smoothly in the channel.

Here I didn’t make use of timeouts and other mechanisms to control the possible scenario where no message comes back, but in practice, that’s totally needed.

// LookupAddr queries a DNS server specified in
// the client initialization for A records concerning
// the address `addr`.
func (c *Client) LookupAddr(addr string) (ips []string, err error) {
        // ...
        // Construct the query struct which
        // represents the whole message.
        // Here we're specifying that we
        // have a single question, that
        // recursion is resired, that the
        // message is a query and then in
        // the question we specify that we
        // want A records, the type is "internet"
        // and the address is 'addr'.
	queryMsg := &Message{
		Header: Header{
			ID:      id,
			QR:      0,
			Opcode:  OpcodeQuery,
			QDCOUNT: 1,
			RD:      1,
		},
		Questions: []*Question{
			{
				QNAME:  addr,
				QTYPE:  QTypeA,
				QCLASS: QClassIN,
			},
		},
	}

        // Because each piece of the message can be
        // marshalled as a sequence of bytes (`Header`
        // implements a `Marshal()` method, as well as
        // `Question` ..), the marshalling of `Message`
        // becomes simply a sequence of `Marshall` calls
        // which sum up to a sequence of bytes
	payload, _ = queryMsg.Marshal()

        // Write the bytes that represent our query to
        // the "connection"
	_, err = c.conn.Write(payload)

        // Prepare a buf to receive the response.
        // We're assuming here the best scenario where
        // the response is always less than 512 as, if it
        // was, then we'd need to tie together multiple
        // messages.
	buf := make([]byte, 1024)
	_, err = c.conn.Read(buf)

	responseMsg := &Message{}

        // construct the Message struct from the sequence
        // of bytes.
	err = UnmarshalMessage(buf, responseMsg)

        // return the IPs (as we asked for IPv4 address,
        // each one will have 4bytes).

        // 3.4.1. A RDATA format
        //     +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        //     |                    ADDRESS                    |
        //     +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        //
        // where: 
        // ADDRESS         A 32 bit Internet address.
        //
        // Hosts that have multiple Internet addresses will have multiple A
        // records.
        ips = make([]string, len(responseMsg.Answers)
	for idx, answer := range responseMsg.Answers {
                ips[idx] = answer.RDATA[idx*4:idx*4+4]
	}

	return
}

With that, we’re set!

There are some other details like compression that are implemented in rawdns that you can check out, but the gist of it is described above.

Closing thoughts

I found the experiment to be very cool.

At first I was expecting a tedious task, but in the end, it was fun to look at how well documented the RFC is and how “future-proof” it was intended to be (even though not everything got really implemented).

I plan to learn more about DNSSEC soon, so this was a good start.

If you want to know more or just get in touch, reach me at @cirowrc on Twitter.

Have a good one!

finis