The IP-over-DNS protocol is as follows: Encoding: We don't want to go outside alphanumerics and hyphens, ie hostname-legal. So we do base32 encoding: 8 hostname characters encoding 5 bits each, which encodes 5 bytes of input data. * Packets "up": - client splits packet into appropriate fragments - makes A queries for We use CNAME queries. The request/response Q and R are bit-encoded into the labels of the query domain and answer section domains, respectively. So requests by the client are QCLASS=IN QTYPE=CNAME !RD QNAME=. and responses are !RD !RA AA 1 IN CNAME The server maintains a local cache of questions we have been asked and answers we gave. Neither side ever retries packets; so any responses from our server's cache are due to resolvers between the client and the server. Requests by client: Create Association Q client-init-nonce remaining Unfragmented initial message data bytes R associd queue-len-info remaining=payload Request Down Q associd client-message-nonce R queue-len-info remaining=payload Submit Up Q associd client-message-nonce payload R queue-len-info remaining Unfragmented response message data bytes queue-len-info := 4* bits Logarithmic server queue length # ciel(log_2( Number of bytes of queued message data + 1 )) # clamped to maximum value payload := [ If there is actually any data to send: 1 bit Only fragment ? [ If not only fragment: 1 bit Final fragment ? 12 bits Fragment offset [ In packets from server: 8* bits netlink-packet-sequence-number # In payloads from client, the client-message-nonce # is used for reassembly. ] ] remaining Data Bytes ] associd := 32* bits Assigned by server client-init-nonce := 64 bits Random number client-message-nonce := 8* bits Sequence number, starts at random value # Ie if we start having more than 255 queries outstanding, we're # going to start losing things. With our default TTL of 1s and # a compliant DNS server, that might limit us to 255 packets/sec. # With noncompliant DNS servers it might reduce available bandwidth. Lengths marked with * are configurable. Need to test transparency of: A -> CNAME CNAME PTR TXT TXT with binary data