I've often wondered if malware use this as a communications channel with C&C servers. DNS queries are often passed unrestricted through firewalls and it would be simple to have one or more domains setup where the query is the information you want to pass and a custom DNS server receives the data and replies to either confirm the receipt of data or answer requests for instruction.
For example, you could encode harvested data (eg: keystrokes) as a DNS query for h28sdhnz890j1hadsl.sj12h89shbapqp8n15kl258.example.com. The TXT record you get back would be the server's response signed with the C&C server's private key. This is so that you can use multiple domains and rotate them in case one gets seized and the signed response prevents spoofing.
Such a system would be quite passive and likely to fly under the radar on most systems.
So-called covert channels can involve DNS, ICMP, packet transmission timing, even processor responsiveness (think of communicating morse code using the timings of a program that switches between a compute-loop and idle, as observed from another program on the system), and any number of other techniques.
Here's a very quick presentation on DNS channels and DNS tunnels from a few years back:
Full IPv4 tunneled through DNS[1] and even ICMP[2] has been possible for ages, and I've personally used ICMP-TX on an airliner to avoid paying for Wi-Fi (not because I'm cheap, mind, but because their registration didn't work).
For some reason those always crap out on me while OzymanDNS (the first major implementation in perl by dan kaminski) works pretty much every time, though it's quite different in operation.
To implement your own custom DNS server,
use Net::DNS::Nameserver; # (and see ozymandns for implementation example)
Around last October when I was in need of internet access I played with dig and noticed that I can query any DNS servers with no restrictions. I thought that this was a great discovery, but as it turns out it seems that this has been discovered long time ago.
Btw today I even wrote a tiny DNS server in Ruby which can be used for fetching short http pages.
https://gist.github.com/912187
It doesn't support splitting, I just wrote it quickly as a proof of concept.
For real use there is the earlier mentioned by jedsmith Iodine.
Stuff like this has been on security peoples radar for a long time, mostly for data exfiltration purposes. What you are suggesting is certainly not a new concept in any way shape or form.
Sadly, although the talk was released in 2009, I still don't see his todo list of "release the code" completed. I think I'm going to email the guy; it would be interesting to look at his code.
These days I'd probably use PowerDNS's pipe backend to implement it rather than a full DNS server in Perl (there's helper modules like ruby-pdns that make writing a DNS server with specialised purposes incredibly easy).
While this might be true if you try to AXFR large zones I think most people who have large zones have solutions to this, it's just like scaling anything else.
For example there's IXFR which is helpful when doing dynamic updates.
Alternatively don't use DNS for transfers -- there's nothing forcing its use, except for talking to clients -- SQL replication works (e.g. with PowerDNS), or the approach most spam blocklists take and rsync zones around for serving by a special server (rbldnsd); DNS just becomes a common query protocol because every client supports it.
Reading the title, I imagined it'd be about a further abstraction to the DNS: a service where by you query an authority, eg: Wikipedia, a sequence of search terms, eg: Hot Sauce Committee, and it gives you the most relevant URL, eg: http://www.beastieboys.com/.
How awesome would it be if Dropbox had "tunneling over DNS" build in? Basically the usability of Dropbox with the ability to get to it at airports, etc. would be awesome.
For example, you could encode harvested data (eg: keystrokes) as a DNS query for h28sdhnz890j1hadsl.sj12h89shbapqp8n15kl258.example.com. The TXT record you get back would be the server's response signed with the C&C server's private key. This is so that you can use multiple domains and rotate them in case one gets seized and the signed response prevents spoofing.
Such a system would be quite passive and likely to fly under the radar on most systems.