I got a call yesterday – from Egypt. It was around noon local time, i.e. shortly after Egypt's government had restored regular internet access (see also, more graphs). At the time of the call, I didn't know that, though.
The guy asked me whether I could help him set up DNS tunneling. Today, he called again and inquired how things were going. He told me he wanted to have a backup internet connection if things would get messy again.
I think, however, that DNS tunneling wouldn't be able to bypass the internet block. On the day of the shutdown (Jan 27th, shortly before midnight UTC),
"Approximately 3,500 individual BGP routes were withdrawn, leaving no valid paths by which the rest of the world could continue to exchange Internet traffic with Egypt's service providers, ... Virtually all of Egypt's Internet addresses are now unreachable, worldwide."
For a more technical analysis, see this BGPmon blog post.
What this means is that Egypt was essentially split off the net. Thus, even a DNS query from inside Egypt (which would be relayed to a server in, say, Germany) could not be forwarded by the provider's DNS servers. Neither could a DNS request from Germany reach a name server located in Egypt. This blog post claims that the providers did shut down DNS access as well (which wouldn't matter much in that situation, anyway).
So, to evade this blockade (i.e., IP won't get routed) it takes more than just trying to sneak data out using covert IP channels.
There are other methods, of course. Protesters set up a voice to tweet converter:
"Over the weekend we came up with the idea of a speak-to-tweet service – the ability for anyone to tweet using just a voice connection," they said.
Voice mail messages left at +16504194196; +390662207294 or +97316199855 will instantly be converted into text messages, referred to as tweets, and posted at Twitter with an identifying "hashtag" of
#egypt.
You could use other radio infrastructure as well to communicate with other countries, which would then feed your data stream into the net. That's not possible on a large scale and for the typical user, however.