DNS Decompression

As part of my analysis of the DNS protocol (I’m writing a DNS server from the ground up), I’ve learnt some cool things that the DNS protocol does to reduce the number of bytes transmitted over the wire.

Let’s say you do a DNS lookup for:

stwalkerster.co.uk.            IN      AAAA

The actual DNS data received as a response is something like this:

Transaction ID: 0x707c
Flags: 0x0100 Standard query response, No error
  1... .... .... .... = Response: Message is a response
  .000 0... .... .... = Opcode: Standard query (0)
  .... .0.. .... .... = Authoritative: Server is not an authority for domain
  .... ..0. .... .... = Truncated: Message is not truncated
  .... ...1 .... .... = Recursion desired: Do query recursively
  .... .... 1... .... = Recursion available: Server can do recursive queries
  .... .... .0.. .... = Z: reserved (0)
  .... .... ..0. .... = Answer authenticated: Answer/authority portion was not authenticated
  .... .... ...0 .... = Non-authenticated data: Unacceptable
  .... .... .... 0000 = Reply code: No error (0)
Questions: 1
Answer RRs: 1
Authority RRs: 0
Additional RRs: 0
Queries
  stwalkerster.co.uk: type AAAA, class IN
    Name: stwalkerster.co.uk
	Type: AAAA (IPv6 address)
	Class: IN (0x0001)
Answers
  stwalkerster.co.uk: type AAAA, class IN, addr 2a01:7e00::f03c:91ff:feae:5fd9
    Name: stwalkerster.co.uk
	Type: AAAA (IPv6 address)
	Class: IN (0x0001)
	Time to live: 1 hour
	Data length: 16
	Addr: 2a01:7e00::f03c:91ff:feae:5fd9

… or at least, that’s a marked-up representation the actual byte stream. The actual byte stream looks like this (Ethernet/IP/UDP headers hidden for clarity):

0000   .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..  ................
0010   .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..  ................
0020   .. .. .. .. .. .. .. .. .. .. 70 7c 81 80 00 01  ..........p|....
0030   00 01 00 00 00 00 0c 73 74 77 61 6c 6b 65 72 73  .......stwalkers
0040   74 65 72 02 63 6f 02 75 6b 00 00 1c 00 01 c0 0c  ter.co.uk.......
0050   00 1c 00 01 00 00 0e 10 00 10 2a 01 7e 00 00 00  ..........*.~...
0060   00 00 f0 3c 91 ff fe ae 5f d9                    ...<...._.

The interesting part is that you can see the looked up name appearing twice in the human-readable form, but only once in the actual byte stream. To describe why, we need to look at how labels (or names) are stored within the protocol.

Let's start at a point in the byte stream which is the location of a label. The position I'm gonna look at is byte 0x37, which has the value 0x0c (0d12). This tells us to look for another 12 bytes, which forms this segment of the label. If we read this in, we get "stwalkerster". We now read in the next length byte, which is 0x02 (0d2). This gives us a segment of "co". The next length is also 0x02, which gives us "uk". Finally, we read in the next length (we don't know this is the end yet!), which gives us a length of 0x00, a zero-length label. This is the end of the label.

Thus, the final result is something like this:

dns

The next instance of this label is at 0x4e. We notice that the first byte has the initial two bits set, so we read the next byte too, to give a value of: 0b1100 0000 0000 1100. The first two bits indicate that this is a pointer, with the rest of the bits indicating the offset from the start of the DNS byte stream the occurrence of the label.

dns2

The DNS packet is therefore compressed in such a way that the duplication of the parts of the label already mentioned is eliminated. This is smart, so a packet containing labels for stwalkerster.co.uk, www.stwalkerster.co.uk, test.www.stwalkerster.co.uk, and simonwalker.me.uk will only mention the suffix of a name once:

dns3 (1)

This pointer-based approach saves a fair amount of bandwidth in large DNS packets where a name may be repeated many times for a round-robin type record.

There are some issues with specific implementations of this though, namely the restrictions on where a pointer may point. Consider this:

dns4

What is the label interpreted by this? simonwalker.me.simonwalker.me.simonwalker.me.simonwalker.me.....

In some bad implementations, this may cause a stack overflow (if done recursively, like mine), or just hang (stuck in an infinite loop, possibly eating RAM). Voila, Denial of Service attack. This can take several forms though, as there could be several pointers involved:

dns5

dns6

dns7

All of the above are technically valid labels. They will just almost never appear as a legitimate request to a DNS server. Any attempt to do something like that should be interpreted as a bad request, or a malicious request and dropped. It shouldn't result in a crash of the DNS server - but I do wonder how many Internet DNS servers are vulnerable to this.

Using LDAP as backend storage for a DNS tree

I’m just on my way back from a meeting with Peter King, one of the lecturers at uni, and my new dissertation supervisor. He’s said yes to my project proposal for developing a solution which uses directory services over LDAP to store a DNS tree, properly integrating LDAP into DNS in such a way that you can use the full flexibility of LDAP to describe a network tree, and DNS will reflect that.

I’m still fleshing out the full project, and I’ve still got to actually write the proposal etc, but I’m hoping to set bounds on the core of the project and set out my goals for it, but it’s pretty exciting to see a project like this come to life from an idea I had a few days ago from a need with my server cluster.

End of Year 3, coursework, exams, et al.

It’s been so long since my last post! So much has been going on I just haven’t had time to write anything.

I’ll start with uni stuff, maybe do a few other posts about other things later.

Our group project was finished with much caffeine consumed by a couple of us, finishing off the documentaton and doing a lot of the coding, especially after one or two people in the group, well, let’s just say that I can’t actually say what they did in the end. We got the main requirements done though, even if the whole staff management side of the system was missing… it was a low priority requirement anyway.

Foundations 2 was a really interesting module, one which actually put to use some of the skills that we’ve been taught over the past couple of years such as text parsing, and other cool stuff like that. Turing machines also really tested algorithmic thinking in a much more low-level sense than C or even assembly, and given we had to write the TM simulator as well as the TM, itwas quite interesting to see how it turned out. The exam wasn’t so bad either – it wasn’t great but it was a lot better than I’d expected.

Formal Spec, though, was a different matter. I strongly dislike SML, and Z for that matter, and this was a module built on those two alone. The exam paper seemed more like a competition between the lecturers as to who could get the fewest papers to mark, rather than a test of our knowledge. I don’t think I’ve come across one person who walked out of that exam happy. The SML coursework was a nightmare too, especially as I just can’t do SML.

The Software Engineering / Professional Development exam was really easy, but I’m hoping that it wasn’t deceptively easy, we shall see how that turns out when the results arrive.

MEng Interview

Having sent a CV to the lecturer in charge of admissions to the MEng course a while ago, I’m quite happy to say that I had an interview for it today, and while the official results are yet to be published, I’m reasonably confident about it :). I just hope that my feeling is a good one.

AI Exam (continued…)

So, yesterday I found out that one topic in the AI exam which I thought I must have completely glossed over in the notes – well, it wasn’t actually in the notes. In fact, the only reference to it was in one of the “recommended reading” – a list which is reasonably long.

That question was worth seven marks.

Multi-lingual interfaces for a website

One of the uni projects I’m doing is a Hotel Management system for “The Blackfish Hotel”, as part of the third-year group project. Part of this is an online booking system, where customers can book rooms in the hotel.

Our “customer”, the manager of the hotel, has asked for the website to have a version in Finnish as well as English, as apparently a large percentage of his customers are from Finland. This posed a challenging problem for us to solve… well… sort of.
Continue reading

Exams and Hurricane Bawbag

After lots of last-minute panicking over the Computer Graphics exam, being resigned to not remember half of the matrix transformations and the Phong equation, we were all taken by surprise by the exam – almost a cakewalk – and a lot of us were saying that too.

AI, on the other hand, couldn’t have got much worse.

Everything that was a “guaranteed” question on the past papers didn’t come up. Everything most people revised didn’t come up. In fact, a fair description of the entire AI module is this:

I could rant on about the coursework too, where we had to produce two expert systems on the same topic – one data driven and one goal driven. We were given two examples, one data driven and one “goal” driven, but the “goal” driven example that we all based our “goal” driven systems off was actually also data driven.

Goal driven was worth 2/3 of the marks.

Just as the AI exam finished, an announcement was made that due to the adverse weather, all exams after this one had been postponed by the university…… in some ways I’m glad it’s out of the way though.

It was a bit windy when we left campus, being on the outskirts of the city it’s pretty exposed – some roofing came off one of the buildings on campus right next to the main bus stop, so that meant the only bus stop that could work on campus was the one at the back of the CS building :D Only in Scotland it be called something like “Hurricane Bawbag”!

Oh well, there’s only Foundations to go, with it’s joys of lambda calculus.

Pigs do actually fly!

Well, we finished the Computer Graphics project!

Take a look at some of the photos on the page about it!

It took more than a couple of nights in the Uni Linux labs to complete, but we managed it.

This was Vasileios’ first time using Git, and to be quite honest, I don’t think we could have done this without using some form of version control software. Other groups were messing around trying to dig the latest files out of each other’s home directories, which is a rather bad way of doing it. Git handled all of that for us automatically.

OpenGL is quite an interesting bit of software too, I’d not expected it to be quite so straight-forward. It’s simply a case of saying what you want to draw, giving it a set of vertices, and then telling it to draw them. You then can apply mathematical transformations to the set of vertices, and draw more vertices and transform those to build your final model. By using the matrix stack and some clever modelling techniques such as scene graphs, you can (for example) draw an apple, move it onto a tree, then move the entire tree plus apple to where you want it.

It’s been a very interesting project, even if the final rush and the heaps of documentation (read: 78 pages) that needed to be written almost overnight made me hate the module.

NUS Reclaim Your Voice 22/03/2011

It’s been too long since I’ve been on a good protest march!

I got the chance to change that, and fight against the introduction of tuition fees in Scotland with about 4000 other students from across Scotland today on Edinburgh’s Royal Mile, finishing up outside Holyrood and the Scottish Parliament, as part of the Reclaim Your Voice campaign

There were a few speeches, unfortunately my phone messed up (probably an id=10t error on the part of the operator) recording, so I lost the Green Party speech, and the first bit of the Lib Dem speech, and another one too.

Mike Russell (Education Secretary):

Des McNulty (Scottish Labour):

Margaret Smith (Scottish Lib Dems):

I’m annoyed I lost the Green Party speech, as it had a brilliant bit in it where the guy (Patrick Harvie) said “I can’t promise you that I won’t vote to increase tuition fees, but you can promise me something – I want you to promise to sack me if I ever vote for tuition fees!”

The Guardian also has an article about this, and there are quite a few pictures on flickr.