DNS Compression In Dart

Last time, we successfully generated a DNS Query and get the results from the DNS server.

I would like to analyze this result, but this data is compressed.

In this Section. I'll explain about dns compression.

DNS Message Compression

According to (RFC1035)[https://datatracker.ietf.org/doc/html/rfc1035], We can specify the location to be referenced by OFFSET in the following format.

a domain name represented as a sequence of labels, where each label consists of a length octet followed by that number of octets.  

The domain name terminates with the zero length octet for the null label of the root.  

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 1  1|                OFFSET                   |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

For example, adding "example.com" to the buffer would look like this

     +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
  13 |           6           |           e           |
     +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
  22 |           x           |           a           |
     +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
  24 |           m           |           p           |
     +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
  26 |           l           |           e           |
     +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
  28 |           3           |           c           |
     +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
  30 |           o           |           m           |
     +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
  30 |           0           | 
     +--+--+--+--+--+--+--+--+

From now on, if you return a URL named www.example.com, you can use

     +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
  40 |           3           |           w           |
     +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
  42 |           w           |           w           |
     +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
  44 | 1  1|                13                       |
     +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

You will be able to express yourself in the above way.

Write This In Dart

Let's write a code to compress URLs, which can be written in about 30 lines of code.

// dnsdict.dart
import 'dart:convert';
import 'dart:typed_data' show Uint8List;

class DNSCompressionDictItem {
  int index;
}

class DNSCompressionDict {
  Map<String, DNSCompressionDictItem> dict = {};
  Uint8List add(String item, int index) {
    var items = item.split('.');
    var buffer = <int>[];
    for (var i = 0; i < items.length; i++) {
      var key = items.sublist(i).join('.');
      if (dict.containsKey(key)) {
        // 既に登録されていれば、そのアドレスを返す
        var tmp = dict[key].index | 0xC000;
        buffer.addAll([(tmp >> 8) & 0xFF, tmp & 0xFF]);
        return Uint8List.fromList(buffer);
      } else {
        // 登録されていないならば、保存する
        buffer.add(items[i].length);
        buffer.addAll(ascii.encode(items[i]));
        dict[key] = DNSCompressionDictItem()..index = index;
        index += items[i].length + 1;
      }
    }
    if (buffer.isNotEmpty) {
      buffer.add(0);
    }
    // 登録されていないならば、保存する
    return Uint8List.fromList(buffer);
  }
}

// dnsdict_test.dart

import 'package:info.kyorohiro.dns/dns.dart';
import 'package:test/test.dart';

void main() {
  group('DNSName', () {
    setUp(() {});

    test('DNSName.encode()', () {
      var dict = DNSCompressionDict();
      int index = 0;
      {
        var bufferSrc = dict.add('yahoo.co.jp', 0);
        index += bufferSrc.length;
        expect(DNSBuffer.fromList(bufferSrc).toHex(), '057961686f6f02636f026a7000');
      }
      // 057961686f6f02636f026a7000(13)

      {
        var bufferSrc = dict.add('google.co.jp', index);
        index += bufferSrc.length;
        expect(DNSBuffer.fromList(bufferSrc).toHex(), '06676f6f676c65c006');
      }
      // 057961686f6f02636f026a7000(13)
      // 06676f6f676c65c006(9)

      {
        var bufferSrc = dict.add('www.google.co.jp', index);
        index += bufferSrc.length;
        expect(DNSBuffer.fromList(bufferSrc).toHex(), '03777777c00d');
      }
      // 057961686f6f02636f026a7000(13)
      // 06676f6f676c65c006(9)
      // 03777777c00d(6)

      {
        var bufferSrc = dict.add('www.google.co.jp', index);
        index += bufferSrc.length;
        expect(DNSBuffer.fromList(bufferSrc).toHex(), 'c016');
      }
    });
  });
}

Decompress In Dart

If you are writing in C, you need to check if you are accessing invalid memory. However, since this is a Dart program, we have not checked for infinite loops.
You may want to check for infinite loops.

This too can be written in about 30 lines of code.

// dnsname.dart

  static Tuple2<String, int> createUrlFromName(Uint8List srcBuffer, int index) {
    var outBuffer = StringBuffer();
    var i = index;
    for (; i < srcBuffer.length;) {
      var nameLength = srcBuffer[i];
      if (nameLength == 0) {
        // TEXT END
        i++;
        return Tuple2<String, int>(outBuffer.toString(), i - index);
      } else if ((0xC0 & nameLength) == 0xC0) {
        // Compression
        var v = ((nameLength & 0x3f) << 8) | srcBuffer[++i];
        var r = createUrlFromName(srcBuffer, v);
        if (outBuffer.length > 0) {
          outBuffer.write('.');
        }
        outBuffer.write(r.item1);
        i++;
        return Tuple2<String, int>(outBuffer.toString(), i - index);
      } else {
        var nameBytes = srcBuffer.sublist(i + 1, i + 1 + nameLength);
        if (outBuffer.length > 0) {
          outBuffer.write('.');
        }
        outBuffer.write(ascii.decode(nameBytes, allowInvalid: true));
        i = i + 1 + nameLength;
      }
    }
    throw DNSNameException('Not Found Null Char');
  }

Next time

Parse the DNS Message retrieved from the DNS server last time and display the result.