As a follow up to the last entry, one other thing I learnt while working on the DNS forwarding server was DNS label compression. Recall that each DNS “message” is comprised of 5 sections: header, question, answer, authority, and some additional space. The QDCOUNT in the header section indicates the number of questions. The question section, which is the second one in a DNS message, has the following structure:

• NAME: A domain name, represented as a sequence of “labels”
• TYPE: 2-byte int; the type of record (1 for an A record, 5 for a CNAME record etc.¹)
• CLASS: 2-byte int; usually set to 1²

To discuss compression, it helps to discuss how domain names are encoded in the NAME section. Essentially, labels are encoded as <length><word> sequences, where <length> is a single byte that specifies the length of <word> to follow, and <word> is the specific section of the DNS label (host, subdomain, domain, TLD), presented as is. This sequence is then terminated by a null byte, \x00. Something like www.google.com is therefore encoded as:

\x03www\x06google\x03com\x00

The question section typically only has one domain name, but the label itself is repeated in a response message, where the same label can be plugged into the answer, authority, or an additional section. For this exercise though, we had to handle cases where QDCOUNT could be greater than 1. Either way, it makes sense to use compression of some sort so that we won’t have to repeat the same label again and again: remember that DNS uses UDP by default, which has a maximum packet size of 512 bytes (though extensions like EDNS0 allow larger sizes).

This was all very novel to me, by the way. Most of my adventures with DNS so far had involved managing some records here and there through portals and some terraform plumbing, and verifying a bunch of information for stakeholders using dig. Hmm, maybe some TXT verification strings as well. But this shit? This is fresh because it’s so fucking old… and so fucking reliable and well engineered (as is the internet as a whole, when you think about it), which is something I wish more engineers cared about these days instead of shoving GPT slop everywhere. Anyway. Compression. Right, think about the most intuitive way you can tell someone to refer back to something that already exists. There are two pieces of information to be conveyed here: “hey, I have already seen this!”, and “here’s where I saw it!” - both of which are exactly what DNS message compression achieves.

This information is encoded in 2 bytes. In those 16 bits, if the first two bits are flipped to 11, it indicates compression. The following 14 bits then encode the address to the label. So when we’re parsing the label section byte by byte, if we encounter a length byte that has value greater than 0b11000000, we know this indicates compression and instead of telling us the length of the word to follow, it’s telling us to look for that label at a certain offset in the message. In hex, the value 0b11000000 is 0xC0. On a high level then, this is what the logic should look like:

if packet[j] >= 0xC0:
	'''
	Compression detected!
	Parse the 14 bits after 11
	To get the offset!
	'''
else:
	'''
	This is the length of the word to follow,
	like 6 for google, as discussed above
	'''

Remember now the bit arithmetic we had discussed in the previous post. If packet[j] and packet[j+1] indicate the 2 bytes where we have all the information required, it should be fairly easy to see that:

offset = (packet[j] & 0x3F) << 8 | packet[j+1]

Okay, that can be a bit confusing even if you know your bit-shifting business. So step by step:

1. packet[j] & 0x3F will preserve the last 6 bits of the first byte, since we do a logical AND with 0b111111 (0x3F). If packet[j] was 0b11000010, this will give us 0b000010 (gets rid of beginning 11)
2. We then shift this entire value to the left by 8 to create space for packet[j+1]. This will convert 0b000010 to 0b000010 00000000
3. After which we just do a logical OR of these two values to set the last 8 bits. If packet[j+1] was 0b10110010, we get the final offset value as 0b000010 10110010

And here’s the code presented as is, with some comments I had put in to help myself when I was working on this. Note that the CodeCrafters exercise presented test cases where QDCOUNT was greater than 1, which as I’ve mentioned is rarely the case in the wild. Therefore, to pass all the testcases, I chose to extract the domains out into a list and run them through my DNS message builder class to ease the construction of the entire message packet. Presented here is the function I had written to extract all the FQDNs.

def list_of_domains(packet, qdcount):
    '''
    Basically, this unpacks a compressed question section inside a DNS packet.
    It looks at the QDCOUNT from the DNS query header, and iterates over it.
    In every iteration, it checks for compression, and if found, jumps to the domain name indicated by the address.
    The goal is to essentially unpack the domains, since we need to provide answers for each of them.
    '''
    domain_names = []
    j = 12  # Remember that question section starts after the header, which is always of size 12

    for _ in range(qdcount):
        domain_name = []
        while packet[j] != 0:  # Stop at null terminator, since that's what separates each domain name in a question
            length = packet[j]  # Each component of a domain name has its length encoded first, so www.google.com will be 3www6google3com

            if length >= 0xC0: # bin(0xC0) means 0b11000000 - in DNS spec, if first two bits of length are set to 11, it indicates compression.
                offset = (packet[j] & 0x3F) << 8 | packet[j+1]
                length = packet[offset] # we have now jumped to the beginning of the domain name, which has the length
                j = offset + 1
                ptr = j
            else:
                j += 1
                ptr = j

            # Read label and append to domain name
            domain_name.append(packet[ptr:ptr+length].decode('utf-8'))
            j += length  # Move past label
        j += 1  # Move past the null terminator
        domain_names.append(".".join(domain_name))
        # Skip QTYPE (2 bytes) and QCLASS (2 bytes)
        j += 4
    return domain_names

Fun.

footnotes