Landon Fuller

Storing Arbitrary Messages in Remote DNS Caches

A few months ago, I read Dan Kaminsky's presentation slides, Attacking Distributed Systems: The DNS Case Study. In the presentation, Kaminsky documents a method of implementing single bit data transfer with nothing more than:

• A recursive, caching name server
• A wildcard zone

After a particularly stressful week, I decided I needed to work on something fun -- an implementation of a DNS-based dead drop messaging system, utilizing Kaminsky's ideas.

Recursion Desired: Signaling 0s and 1s

In each DNS query, 7 bits are reserved for a number of flags, one of which is the Recursion Desired (RD) flag. If set to 0, the queried DNS server will not attempt to recurse -- it will only provide answers from its cache.

Combine this with a wildcard zone and it's possible to signal bits (RD on), and read them (RD off). To set a bit to 1 the sender issues a query with the RD bit on. The wildcard zone resolves all requests, including this query. The receiver then issues a query for the same hostname, with the RD bit off. If the bit is 1, the query will return a valid record. If the bit is 0, no record will be returned.

So, it's easy to signal a single bit, but what if you want to share more than 1 bit of data? This requires both sides to compute a list of records -- one record for every bit of data we wish to send. In my implementation, I chose to do this with a pre-shared word list and initialization vector (IV). Given the same word list and IV, both sender and receiver can independently compute an identical mapping of words to bit positions. The sender can then signal the '1' bits, and the receiver can query all bits.

To communicate, the sender and receiver need to pre-share a word list, an initialization vector (IV), the IP of a recursive nameserver, a wildcard domain, and a communications window (time of day). For the sake of simplicity, I borrowed a page from Pascal: Every message is prepended with an 8-bit unsigned value specifying the full message length. Here's how the protocol works:

Sender:

• Step 1: Split the message into individual bits.
• Step 2: Permute the word list in a reproducible fashion using the shared IV.
• Step 3: Encode the length of your message as an 8 bit unsigned value, and prepend the length to your message data.
• Step 4: Each word in the ordered word list corresponds to a single bit of your message. Generate a valid hostname for each bit by combining each word with the wildcard DNS zone
• Step 5: For each bit that is 1, do a recursive lookup against the shared nameserver for the corresponding wildcarded hostname.

Receiver:

• Step 1: Permute the word list in a reproducible fashion using the shared IV.
• Step 2: Each word in the ordered word list corresponds to a single bit of the message. Generate a valid hostname for each bit by combining each word with the wildcard DNS zone.
• Step 3: Acquire the message length by doing a non-recursive lookup against the shared nameserver for the first 8 bits of the message. Names that return answers are 1, those that do not are 0.
• Step 4: For each word in the word list, do a non-recursive lookup against the shared nameserver for the remainder of the message.
• Step 5: Reconstruct the message from the individual bits.

Download

You can download a copy of NSDK here. It's written in Python, and depends on Twisted Core and Twisted Names.

Usage

nsdk.py [dns IP] [wildcard domain] [word list] [iv] 

Each bit of your message requires at least one DNS query. I strongly suggest testing this implementation against name servers and zones that you control.

To send a message:

./nsdk.py 10.0.0.1 wildcard.example.com /usr/share/dict/words 42 "Abusing DNS for fun and profit"
Message sent successfully!

To receive the message:

./nsdk.py 10.0.0.1 wildcard.example.com /usr/share/dict/words 42
Read 240 bits from DNS server
The Secret Message: Abusing DNS for fun and profit