Building a DNS resolver in Go from scratch - Part 3
Mostafa Ahmed
Recap
In the last 2 parts we went over the DNS protocol flow and terms, then in part 2 we built the query packet and sent it to a root nameserver.
In this part, we will parse the response we got and complete our simple resolver.
Israel is committing a genocide against the people of Palestine.
Find out how you can help https://techforpalestine.org/learn-more/
Free Palestine 🇵🇸 End the occupation 🇵🇸
View the full code
Response format
A DNS response is identical to the query format, but has additional sections populated depending on the response's type.
If the response is a referral we will get records in the authority - and probably additional - sections, if it's an answer the answer section will be populated. In all cases, the question section will always have the values sent by the client.
Setting things up
On to parsing the response, but before we start let's define some utilities and types that will help us
Utilities
The utilities are just simple renames for functions in the binary package to make them shorter as we will be using them a lot.
// dns/utils.go
package dns
import (
"encoding/binary"
)
var btoi16 = binary.BigEndian.Uint16
var btoi32 = binary.BigEndian.Uint32
Adding types: Header & DNS message
For the types, we start by defining the headers and a simple DNS message that we'll expand on it as we go.
// dns/message.go
type Header struct {
TransactionId int
QueriesCount uint16
AnswersCount uint16
AuthoritiesCount uint16
AdditionalCount uint16
}
type DNSMessage struct {
Header Header
}
Parsing function
In a new file parser.go will be the function that parses the packet, it accepts the bytes slice and returns a pointer to DNSMessage after it populates all it's values.
// dns/parser.go
package dns
func ParseDNSReponse(b []byte) *DNSMessage {
response := DNSMessage{}
// Parsing logic
return &response
}
Parsing the header
To parse the response's content, we'll use a cursor variable to keep track of how far we've parsed into the packet.
Parsing the header is straightforward, the length of each field is known so we can easily populate the Header struct by indexing through the packet. After we do so, the cursor will be 12 bytes in.
func ParseDNSReponse(b []byte) *DNSMessage {
response := DNSMessage{
Header: Header{
QueriesCount: btoi16(b[4:6]),
AnswersCount: btoi16(b[6:8]),
AuthoritiesCount: btoi16(b[8:10]),
AdditionalCount: btoi16(b[10:12]),
},
}
cursor := 12
// Parse the remaining sections
return &response
}
Handling resource records
The remaining sections will be parsed using the same logic. We iterate using the counts we got from the header and parse the records in each section.
func ParseDNSReponse(b []byte) *DNSMessage {
response := DNSMessage{
Header: Header{
QueriesCount: btoi16(b[4:6]),
AnswersCount: btoi16(b[6:8]),
AuthoritiesCount: btoi16(b[8:10]),
AdditionalCount: btoi16(b[10:12]),
},
}
cursor := 12
for range response.Header.QueriesCount {
// Parse fields for query, append result to `response` and move the cursor
// All sections below will do the same
}
for range response.Header.AnswersCount { }
for range response.Header.AuthoritiesCount { }
for range response.Header.AdditionalCount { }
return &response
}
But first, let's take a look at what the contents of the records are.
Resource record fields
RFC 1035 makes a distinction between the format of the question's records and the resource records of the other sections. But I decided to treat questions as a subset of the other records. That way, we can have a single function to parse them and just return early if what we're parsing is a question.
RDLENGTH & RDATA are of special interest, RDLENGTH tells us the size of RDATA in bytes. The meaning of RDATA depends on what the TYPE of the resource record is.
For example, if TYPE = A or AAAA, that means RDATA is an IPv4 or v6 address respectively. If TYPE = NS, that means RDATA represents a domain name, encoded similar to how we did with our query.
TYPE can take many values, but for our resolver's purposes A, AAA and NS are all we'll need to handle.
Adding RR parsing function & types
Going back to DNSMessage struct, lets add to it a new struct for a resource record, and a mapping for the record types that we'll use for conversions.
// dns/message.go
var rrtypes = map[uint16]string{
1: "A",
2: "NS",
28: "AAAA",
}
type ResourceRecord struct {
Name string
RRType string
Class string
TTL uint32
// Available on RRs with type `NS`
Nameserver string
// Available on RRs with type `A` & `AAAA`
Address net.IP
}
type DNSMessage struct {
Header Header
Queries []ResourceRecord
Answers []ResourceRecord
Authorities []ResourceRecord
Additional []ResourceRecord
}
Now let's create a new function that will parse a RR. It returns a ResourceRecord struct and an int for bytes read into the packet, that way ParseDNSReponse can keep it's cursor up to date.
// dns/parser.go
func parseRR(b []byte, offset int, isQuery bool) (ResourceRecord, int) {
var n int
var rr ResourceRecord
// Parse the RR
return rr, cursor - offset
}
func ParseDNSReponse(b []byte) *DNSMessage {
response := DNSMessage{
Header: Header{
QueriesCount: btoi16(b[4:6]),
AnswersCount: btoi16(b[6:8]),
AuthoritiesCount: btoi16(b[8:10]),
AdditionalCount: btoi16(b[10:12]),
},
}
cursor := 12
for range response.Header.QueriesCount {
rr, n := parseRR(b, cursor, true)
cursor += n
response.Queries = append(response.Queries, rr)
}
for range response.Header.AnswersCount {
rr, n := parseRR(b, cursor, false)
cursor += n
response.Answers = append(response.Answers, rr)
}
for range response.Header.AuthoritiesCount {
rr, n := parseRR(b, cursor, false)
cursor += n
response.Authorities = append(response.Authorities, rr)
}
for range response.Header.AdditionalCount {
rr, n := parseRR(b, cursor, false)
cursor += n
response.Additional = append(response.Additional, rr)
}
return &response
Parsing questions
To parse a resource record for a question we need to:
Parse the name, basically loop over the labels until we're on a zero byte
Parse the record type using our mapping
Parse the class, for our simple resolver this will always be
IN
Below is the logic for this, with the name parsing extracted into parseName:
// dns/parser.go
func parseName(b []byte, offset int) (string, int) {
labels := []string{}
cursor := offset
for {
labelLen := int(b[cursor])
cursor += 1
// Reached terminator
if labelLen == 0 {
break
}
l := string(b[cursor : cursor+labelLen])
cursor += labelLen
labels = append(labels, l)
}
return strings.Join(labels, "."), cursor - offset
}
func parseRR(b []byte, offset int, isQuery bool) (ResourceRecord, int) {
var n int
var rr ResourceRecord
cursor := offset
rr.Name, n = parseName(b, cursor)
cursor += n
rr.RRType = rrtypes[btoi16(b[cursor:cursor+2])]
cursor += 2
rr.Class = "IN"
cursor += 2
return rr, cursor - offset
}
In parseName, we loop until we land on a zero byte indicating the domain name is done, then we return the extracted parts joined by a . .
Handling name compression
Before moving on to parsing the remaining sections, let's take a quick detour to see how domain names are compressed in a response.
When a resource record has a domain name (or part of a name) that was repeated in a previous field, it can point to the previous occurrence instead of repeating the name twice. The second occurrence will be a pointer to where the first occurrence is located in the packet.
For example, if the name example.com is present in the question section, and a record in the answers section has the string as its value, the answer record's entry will be a 2 byte pointer. The first two bits are set to 1 to indicate that it is a pointer, and the remaining 14 are the offset where we'll find the first occurrence.
Compression is also used for suffixes of a name. For example the name ns2.google.com only has ns2 and pointer to the previous occurrence of google.com in the questions section.
With pointers thrown into the mix, the possible cases for a domain name are:
Sequence of labels
Sequence of labels ending with a pointer to a compressed suffix/name
Just a pointer
Basically, whenever we come across a pointer we know that the domain name we’re parsing is finished. With that in mind, let's update the name parsing function to account for compression
// dns/parser.go
func parseName(b []byte, offset int) (string, int) {
labels := []string{}
cursor := offset
for {
isPtr := b[cursor]&0xC0 == 0xC0
// Pointer always signifies end, RFC 1035 4.14
if isPtr {
packetOffset := btoi16([]byte{
b[cursor] & 0x3F,
b[cursor+1],
})
l, _ := parseName(b, int(packetOffset))
labels = append(labels, l)
cursor += 2
break
}
labelLen := int(b[cursor])
cursor += 1
// Octet labels terminator
if labelLen == 0 {
break
}
l := string(b[cursor : cursor+labelLen])
cursor += labelLen
labels = append(labels, l)
}
return strings.Join(labels, "."), cursor - offset
}
The tricky bit hehe is knowing if we're at the start of a pointer, we check for this by ANDing the current byte with 0xC0 (11000000). After that we need to convert the remaining 14 bits as an integer, ANDing the first byte with 0X3F (00111111) then converting both bytes to an int.
Notice that we only increment the cursor by 2 and discard the number of bytes read from following the pointer. Now our parser can handle names with pointers, gg ez.
Parsing answers, authorities & additional records
With a simple update to parseRR we'll be able to parse the remaining records.
// dns/parser.go
func parseRR(b []byte, offset int, isQuery bool) (ResourceRecord, int) {
var n int
var rr ResourceRecord
cursor := offset
rr.Name, n = parseName(b, cursor)
cursor += n
rr.RRType = rrtypes[btoi16(b[cursor:cursor+2])]
cursor += 2
rr.Class = "IN"
cursor += 2
// For queries, we're done after the common fields
if isQuery {
return rr, cursor - offset
}
rr.TTL = btoi32(b[cursor : cursor+4])
cursor += 4
dataLen := int(btoi16(b[cursor : cursor+2]))
cursor += 2
switch rr.RRType {
case "NS":
rr.Nameserver, _ = parseName(b, cursor)
case "A", "AAAA":
rr.Address = net.IP(b[cursor : cursor+dataLen])
}
cursor += dataLen
return rr, cursor - offset
}
Based on the record type, we will either parse the domain name of the nameserver or an IP address from the bytes of RDATA. Now we've completed parsing all the things we'll need in a response.
Wrapping up the resolver
The last step is to update the resolver, it will follow a simple strategy:
Ask the root server
Does the response have an authority with a known IP (sent in additional RRs) ?
Yes, query the next authority
No, resolve the authority from the root and query it
Repeat step 2 until we get an answer
func ResolveFromRoot(domain string, root string) string {
target := root
for {
conn, err := net.Dial("udp", target+":53")
if err != nil {
fmt.Println("connection to server failed")
os.Exit(1)
}
defer conn.Close()
message := NewDNSMessage(domain)
conn.Write(message)
b := make([]byte, 1024)
n, _ := conn.Read(b)
response := ParseDNSReponse(b[:n])
// Answer found!
if response.Header.AnswersCount > 0 {
return response.Answers[0].Address.String()
}
// Resolve NS with unknown IP
if response.Header.AuthoritiesCount > 0 && response.Header.AdditionalCount == 0 {
nameserver := response.Authorities[0].Nameserver
target = ResolveFromRoot(nameserver, root)
}
// Ask the next server
for _, rr := range response.Additional {
if rr.RRType == "A" {
target = rr.Address.String()
break
}
}
}
}
Aaaaand we're finally done, I left logging, reading args from the command line & piecing everything together in main.go, you can view the full implementation in this repository if you're interested.
Thanks for sticking till the end so far and hope you enjoyed the ride <3
Subscribe to my newsletter
Read articles from Mostafa Ahmed directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
Mostafa Ahmed
Mostafa Ahmed
Free Palestine, end the genocide 🇵🇸 https://techforpalestine.org/learn-more/