I had some time on my hands and got TCP over DNS working. It's obviously quite slow, but certainly useable. A fun exercise anyway.
It's also interesting to note that Julian Assange (AFAIK) was the first person to come up with this idea back in 2006.
http://re-iq.blogspot.com/2006/12/ip-over-ppp-over-dns-over-...
I have to interject here - not to blow my own trumpet, but as a 'point of fact'. (Oops... once you start correcting misinformation on the internet, you are going to be busy for a long time.)
I wrote about this in 1998, when I released source code that did this on the bugtraq mailing list - http://gray-world.net/papers/dnstunnel.txt has a copy of my mail.
Before that there was a long standing existing technique to tunnel data through UDP packets that simply pretended to be destined for the DNS port (53). That stopped working if the network admin filtered outbound UDP and forced people to use their local DNS server instead. My method still works in that scenario though.
(If anyone knows of an earlier reference to the method I posted about, please let me know.. for all I know it was a well-known tactic in the underworld before I posted to bugtraq.)
From Julian's post, it's not possible to see which of the two methods his code used, since the rb file seems to have disappeared. I suspect it was "my" method.
I do like the ppp interface through - mine just tunneled bash commands + responses.
Oskar
HN'ers -- Despite Kaminsky's ego, all signs indicate Oskar invented DNS tunneling.
Also, a quick search for "dns-over-tcp" yields several results.
It's not very efficient, though.
If you have a server somewhere, there's no real limit to the creative ways you can get around network restrictions.