Note: This write-up assumes familiarity with DNS, in particular the entire question-answer (“resolution”) process. Some helpful pages to refer:
- Section 4.1 of RFC 1035, which goes through the top level format of a DNS packet.
- This writeup which can serve as a good introduction.
- Endinanness on Wikipedia.
I found myself in a bit of a funk late last year, and realised that I haven’t written any code in a while that I had felt truly proud of. I mean sure, there’s the usual LeetCode grind I’ve taken up every now and then: that Sisyphean ordeal every engineer working in tech takes up to go through those somewhat mechanical interview rounds. I doubt most engineers enjoy it (I certainly don’t), so to save myself any more unwarranted self-loathing, I figured I should do a fair bit more of hobby coding. I was introduced to CodeCrafters by a coworker, and decided to solve the DNS server challenge. It was an easy pick: I’ve been working in Edge engineering for a while now, so I figured this challenge would teach me some practical bits about a service I’m more or less familiar with…
No matter how well you thought you knew something, it’s surprising how little you actually know.
I did manage to finish the challenge. The code is still pretty fucking shit, you can see it for yourself here. It might not make a ton of sense unless you go through the challenge yourself, but it serves as a basic DNS forwarding server that receives some DNS questions, forwards them to a resolver, retrieves the answer and sends it back to the asking client. It’s not a complete implementation - not yet, at least. I may get to expanding upon it and turning it into a complete forwarding server at some point. For now though I’m happy with this being finished in the context of the challenge, and so I’m going to talk about some of my learnings while going through this ordeal.
Enough yapping, let me talk about the first interesting thing - setting specific bits inside a DNS header. To reiterate, a DNS header is a 12 byte field that’s arranged like this:
Field | Size (bits) | Description |
---|---|---|
Transaction ID | 16 | Unique identifier for request/response |
Flags | 16 | Controls query type, recursion, etc. |
Questions | 16 | Number of entries in the Question section |
Answer RRs | 16 | Number of resource records in Answer section |
Authority RRs | 16 | Number of resource records in Authority section |
Additional RRs | 16 | Number of resource records in Additional section |
Of importance to us are the flags, which have to be set in the context of the request received:
Bit(s) | Field | Description |
---|---|---|
0 | QR | Query (0) or Response (1) |
1-4 | OPCODE | Query type (standard, inverse, etc.) |
5 | AA | Authoritative Answer |
6 | TC | Truncated Response (set to 1 if message is larger than 512 bytes, 0 in UDP responses) |
7 | RD | Recursion Desired (indicate to server to resolve the request recursively) |
8 | RA | Recursion Available |
9-11 | Z (Reserved) | Used to indicate DNSSEC (was a reserved bit during inception) |
12-15 | RCODE | Response code (success, format error, etc.) |
This stage of the challenge asked us to craft a DNS header with some specific values for the various fields described above. When I started thinking about the problem, I knew I had to use a bytearray(12)
to achieve this. (remember: DNS headers are of fixed size, 12 bytes). But I also wanted this to be somewhat easier to work with: a user should be able to call something like:
test_dns_packet = DNSPacket()
test_dns_packet.set_header(
ID=1234,
QR=0,
OPCODE=1,
AA=0,
TC=0,
RD=1,
RA=0,
Z=0,
RCODE=0,
QDCOUNT=1,
ANCOUNT=0,
NSCOUNT=0,
ARCOUNT=0
)
which should allow them to set flags individually by sending values that are more friendly (instead of passing bits/binary values around). This is not something I had worked with in a long time: how do I toggle specific bits within the 2 bytes (16 bits) reserved for 8 flag values individually, and also make it so that a user invoking the method can pass a regular int
value (a full fledged object in Python) to toggle those? A combination of memory, bunch of Google searches, and some LLM queries led me back to bit arithmetic - something I had studied way back in college, and came across every now and then, but never paid much attention to otherwise. Surprising how far bit shifts and logical ANDs can get you.
Say you have a 2 byte value ID
that’s set to hex 0xABCD
. If you remember those lectures on endianness, you’d remember that 0xAB
is the MSB (most significant byte) and 0xCD
is the LSB (guess). Big endian (network byte order) places the MSB first, little endian prioritises LSB, so the byte order would look like:
- Big endian:
0xAB
0xCD
- Little endian:
0xCD
0xAB
Here’s 0xABCD
in binary: 1010101111001101
or: 10101011 (0xAB) 11001101 (0xCD)
Now let’s discuss left shifting and right shifting:
- Left shifting (
<<
): Moves bits to the left, and pads zeroes on the right. So0b1 << 8
would move1
8 times to the left, resulting in0b100000000
. Mathematically, left shifting byn
bits multiplies the original value with2^n
. Indeed,0b100000000
evaluates to 256, which is 1 (original value) multiplied by 2^8. - Right shifting (
>>
): Moves bits to the right, padding zeroes on the left. So0b11110000 >> 4
would get rid of the last 4 zeroes, and pad 4 in beginning, giving us0b00001111
. Right shifting byn
bits does the opposite: it divides the value by2^n
. Since0b11110000
evaluates to 240, right shifting by 4 would have us divide 240 by 2^4, yielding us the value 15 (0b00001111
).
So to extract 0xAB
into a single byte, MSB
:
ID = 0xABCD # 10101011 11001101
MSB = ID >> 8 # 00000000 10101000
MSB = MSB & 0xFF
The last step is important here: MSB & 0xFF
evaluates to (00000000 10101000) & 11111111
, which gives us 10101000
, packing MSB into a single byte. Similarly, if we just want to extract the LSB, we don’t have to engage in bit shifting, as just logically ANDing it with 0xFF
would yield us the last 8 bits:
LSB = ID & 0xFF
And then setting the transaction ID portion of the DNS header is as simple as:
# self.header is a bytearray() of size 12
self.header[0] = MSB
self.header[1] = LSB
From the logic that we’ve discussed so far, the bit layout for flags can be set as follows:
'''
Suppose we receive the following values:
QR = 1
OPCODE = 2
AA = 1
TC = 0
RD = 1
RA = 0
Z = 0
RCODE = 3
'''
FLAGS = (QR << 15) | (OPCODE << 11) | (AA << 10) | (TC << 9) | (RD << 8) | (RA << 7) | (Z << 4) | (RCODE & 0xF)
This maybe a bit difficult to parse at first, but it’s quite intuitive once you understand the shifting business: whatever values you receive in the set_header()
function are shifted according to the bit space assigned to them, and we build FLAG
by successively logically ORing:
1000 0000 0000 0000 (QR << 15)
| 0001 0000 0000 0000 (OPCODE << 11)
| 0000 1000 0000 0000 (AA << 10)
| 0000 0000 0000 0000 (TC << 9)
| 0000 0001 0000 0000 (RD << 8)
| 0000 0000 0000 0000 (RA << 7)
| 0000 0000 0000 0000 (Z << 4)
| 0000 0000 0000 0011 (RCODE & 0xF)
--------------------------------------
1001 1001 0000 0011 (Final Binary)
This gives the final FLAG
value as 1001 1001 0000 0011
, which is the hex value 0x9903
. We can then pack these values into the header in a manner similar to the transaction ID:
self.header[2] = (FLAGS >> 8) & 0xFF
self.header[3] = FLAGS & 0xFF
QDCOUNT, ANCOUNT, NSCOUNT, ARCOUNT
are similarly straightforward to pack.
All in all, my set_header()
method finally looks like:
def set_header(self,
ID=0,
QR=0,
OPCODE=0,
AA=0,
TC=0,
RD=0,
RA=0,
Z=0,
RCODE=0,
QDCOUNT=0,
ANCOUNT=0,
NSCOUNT=0,
ARCOUNT=0
):
# set PID
self.header[0] = (ID >> 8) & 0xFF
self.header[1] = ID & 0xFF
#set flags
FLAGS = (QR << 15) | (OPCODE << 11) | (AA << 10) | (TC << 9) | (RD << 8) | (RA << 7) | (Z << 4) | (RCODE & 0xF)
self.header[2] = (FLAGS >> 8) & 0xFF
self.header[3] = FLAGS & 0xFF
#set QDCOUNT
self.header[4] = (QDCOUNT >> 8) & 0xFF
self.header[5] = QDCOUNT & 0xFF
#set ANCOUNT
self.header[6] = (ANCOUNT >> 8) & 0xFF
self.header[7] = ANCOUNT & 0xFF
#set NSCOUNT
self.header[8] = (NSCOUNT >> 8) & 0xFF
self.header[9] = NSCOUNT & 0xFF
#set ARCOUNT
self.header[10] =(ARCOUNT >> 8) & 0xFF
self.header[11] = ARCOUNT & 0xFF
Which of course is not neat, and requires some work, etc. But I’m satisfied with where it has landed at the moment. The few hours I spent trying to figure this out, reading the RFC and understanding bit shifts felt rewarding, a word that I don’t use often when discussing tech with my peers and friends these days.
I hope this was helpful. I intend to write another post or two about some other things I’ve learnt through this challenge before I move on, but I’m also open to covering something specific if you’d like me to. Feel free to write to me for suggestions, feedback etc.