Slashdot Mirror
Collage, and the Challenge of "Deniability"
Slashdot regular Bennett Haselton has written a piece on a new program called Collage that can circumvent censorship by embedding messages in user-generated content on sites like Flickr. The program demonstrates that a long-standing theoretical concept can be reduced to practice but Bennett wonders if anybody would actually need it, as long as they can exchange encrypted messages over Gmail and AIM. He begins "In a presentation delivered at USENIX, Georgia Tech grad student
Sam Burnett and his colleagues
described how their new program, "Collage," could circumvent Internet censorship
by embedding messages in user-generated content on sites like Flickr. The short
version is that a publisher uses the Collage system to break a message into pieces
that are small enough to embed into a photograph using standard
steganography,
the photos are published according to some protocol (e.g. "all
photos in the photostream of user xyz" or "all photos tagged with the 'xyz' tag"),
and receivers who know the protocol for identifying the photos, can retrieve
them and decode the message. According to the authors'
paper, the system is general
enough that it could be adapted to almost any site where user-generated content is
published. (All of this can be done by hand using existing tools, but Collage automates
the process to hide the individual steps from the user.)"
From this short description, you can see the two salient facts about Collage:
(1) it's robust, in the sense that in order to shut it down completely, the censor
would have to block every site containing user-generated content; and (2) it's
efficient only for small text messages (which is what the authors used to test it),
and not for high-bandwidth communications such as video. The authors have also
highlighted the claim that Collage is (3) deniable, in the sense that in using it,
you won't attract the attention of the censors for browsing "innocent" sites like
Flickr. On this point, I'm not so sure; I think it's highly dependent on the kinds
of publication system that the sender and the recipient agree on. For example, if the sender
publishes their messages in photos all in one user's photostream, and that photostream
is used primarily by recipients in censored countries to receive encoded messages,
and if virtually nobody ever visits that photostream for any other reason, then if
the censor ever finds out about that photostream, they could flag any user who ever visits it.
It doesn't matter if the "site" as a whole is "innocent", if that one user's
photostream is not.
But there's a more fundamental issue: Currently, in all censored countries, there is at least one way to receive prohibited text messages more efficiently (and with greater deniability) than with Collage. So Collage may work perfectly, but even when it gets released, I'd be very surprised to see large numbers of people using it unless all the simpler alternatives get blocked.
Most tools that people use to circumvent Internet censorship, are not "deniable" in the sense described above. If you visit a proxy site like VTunnel, any censor who is monitoring your Internet connection can see that you connected to a known proxy site. If you connect to the proxy site using "https://" instead of "http://", then a censor eavesdropping on your connection, won't be able to tell what you looked at through the proxy site (unless they confiscate your computer and look through your browser history), but they'll still be able to tell that you visited a proxy site. Similarly, if you use a tool like UltraSurf or Tor, those tools can circumvent the censor's filters by re-routing your Internet connection through a server outside the censored country -- but a censor monitoring your traffic, can still see that you connected to an UltraSurf or Tor server outside the country, even if they can't tell what Web sites you were visiting.
But if all you want is to receive short text messages, then there are many options that are completely "deniable." The simplest is probably to use Gmail and to choose the option to always read messages over https://. (If you sign in to Gmail, under "Settings" you can choose between "Always use https" and "Don't always use https".) If you read your inbox contents using https, then a censor eavesdropping on your connection can't see anything at all -- not the contents of messages that people send you, not the email addresses of people who are writing to you, not even the username that you use to sign in to read your Gmail messages. This gives you more or less perfectly deniability. As long as many Gmail users are using Gmail over https://, then doing this by itself would not attract undue attention from censors monitoring your Internet traffic. Using Gmail, you could also exchange higher-bandwidth content like images and video (up to Gmail's attachment size limit, currently 25 megabytes), something not possible with Collage.
Of course, if you remember the case in which Yahoo turned over information about one of its Chinese account-holders to the Chinese government (who subsequently arrested the user and sentenced them to 10 years in prison), you may be wary of trusting any Western corporation with your privacy. But in this case, you wouldn't have to. Because even if the Chinese government found out that some Gmail users were using Gmail to receive anti-government messages from the U.S., the censors wouldn't be able to eavesdrop on https-protected connections to find out which users were receiving the messages or what they said, so there would be no information for them to demand that Google turn over to them.
Or if you want to exchange encrypted text messages in real time, you can use any instant messaging client that supports encryption. Whether or not this is "deniable", in the sense of not attracting undue attention for "suspicious activity", depends on what proportion of other users are using the chat program in encrypted mode as well. The current version of AOL Instant Messenger, for example, apparently encrypts all instant messages by default. (Although you should take care to understand exactly what is "encrypted" when using an instant messaging client. In my experiments, when using AOL Instant Messenger, the contents of messages were encrypted, but the specific screen names that you're sending and receiving messages from, are not. In other words, a censor eavesdropping on your traffic, can see which screen names you exchanged messages with, but not the message contents. So if there were an AOL user account in a non-censored country that was a dummy account used primarily for passing banned information to users in censored countries, then if the censors ever found out about that account, they could flag and investigate any user in their country who exchanged messages with that screen name.)
The bottom line is that as long as at least one of these alternatives remains unblocked in your country, they would serve as an easier way to achieve the same goals that Collage achieves. They're generally faster, more convenient, and most of the time, more "deniable", in the sense that the traffic they generate won't look as suspicious as, say, browsing a Flickr feed that later becomes widely known as source of banned encoded messages. Collage does demonstrate that an interesting idea can be reduced to practice, and is robust in the sense that the general scheme cannot be blocked unless a regime blocks access to every site hosting user-submitted content. But there doesn't seem to be a compelling reason to use it unless and until all of the simpler methods get blocked.
I write all of this as someone who also wrote a program a few years ago that was meant to serve as a more robust back-up, in case a more popular method of circumventing censorship ever got shut down by the censors. In my case, I thought that most censoring regimes would start blocking all popular Web proxy sites, so I wrote an install script called "Circumventor" that would let you set up a Web server and James Marshall's CGIProxy script on your home computer, turning it into a mini-Web-proxy site. I assumed that eventually, most people in censored countries would have to rely on someone in a non-censored country to set up a private Web proxy like this and e-mail them the URL, once China and Iran got their act together and started blocking most publicly known Web proxy sites. But that never happened, partly because Web proxy sites are now springing up faster than most censors' databases can keep up with. So the web proxy install script fell by the wayside -- but that's good news, because it means that nobody really needed it, since the simpler, more straightforward methods continued to work. Why pester your cousin in the U.S. to set up a Web proxy for you, when most Web proxies you can find in Google are not even blocked yet?
And so it goes for Collage. It sounds like a perfectly fine idea, and it will be great news all around if nobody ever actually has to use it, because the censors never get around to blocking all of the simpler alternatives.
But there's a more fundamental issue: Currently, in all censored countries, there is at least one way to receive prohibited text messages more efficiently (and with greater deniability) than with Collage. So Collage may work perfectly, but even when it gets released, I'd be very surprised to see large numbers of people using it unless all the simpler alternatives get blocked.
Most tools that people use to circumvent Internet censorship, are not "deniable" in the sense described above. If you visit a proxy site like VTunnel, any censor who is monitoring your Internet connection can see that you connected to a known proxy site. If you connect to the proxy site using "https://" instead of "http://", then a censor eavesdropping on your connection, won't be able to tell what you looked at through the proxy site (unless they confiscate your computer and look through your browser history), but they'll still be able to tell that you visited a proxy site. Similarly, if you use a tool like UltraSurf or Tor, those tools can circumvent the censor's filters by re-routing your Internet connection through a server outside the censored country -- but a censor monitoring your traffic, can still see that you connected to an UltraSurf or Tor server outside the country, even if they can't tell what Web sites you were visiting.
But if all you want is to receive short text messages, then there are many options that are completely "deniable." The simplest is probably to use Gmail and to choose the option to always read messages over https://. (If you sign in to Gmail, under "Settings" you can choose between "Always use https" and "Don't always use https".) If you read your inbox contents using https, then a censor eavesdropping on your connection can't see anything at all -- not the contents of messages that people send you, not the email addresses of people who are writing to you, not even the username that you use to sign in to read your Gmail messages. This gives you more or less perfectly deniability. As long as many Gmail users are using Gmail over https://, then doing this by itself would not attract undue attention from censors monitoring your Internet traffic. Using Gmail, you could also exchange higher-bandwidth content like images and video (up to Gmail's attachment size limit, currently 25 megabytes), something not possible with Collage.
Of course, if you remember the case in which Yahoo turned over information about one of its Chinese account-holders to the Chinese government (who subsequently arrested the user and sentenced them to 10 years in prison), you may be wary of trusting any Western corporation with your privacy. But in this case, you wouldn't have to. Because even if the Chinese government found out that some Gmail users were using Gmail to receive anti-government messages from the U.S., the censors wouldn't be able to eavesdrop on https-protected connections to find out which users were receiving the messages or what they said, so there would be no information for them to demand that Google turn over to them.
Or if you want to exchange encrypted text messages in real time, you can use any instant messaging client that supports encryption. Whether or not this is "deniable", in the sense of not attracting undue attention for "suspicious activity", depends on what proportion of other users are using the chat program in encrypted mode as well. The current version of AOL Instant Messenger, for example, apparently encrypts all instant messages by default. (Although you should take care to understand exactly what is "encrypted" when using an instant messaging client. In my experiments, when using AOL Instant Messenger, the contents of messages were encrypted, but the specific screen names that you're sending and receiving messages from, are not. In other words, a censor eavesdropping on your traffic, can see which screen names you exchanged messages with, but not the message contents. So if there were an AOL user account in a non-censored country that was a dummy account used primarily for passing banned information to users in censored countries, then if the censors ever found out about that account, they could flag and investigate any user in their country who exchanged messages with that screen name.)
The bottom line is that as long as at least one of these alternatives remains unblocked in your country, they would serve as an easier way to achieve the same goals that Collage achieves. They're generally faster, more convenient, and most of the time, more "deniable", in the sense that the traffic they generate won't look as suspicious as, say, browsing a Flickr feed that later becomes widely known as source of banned encoded messages. Collage does demonstrate that an interesting idea can be reduced to practice, and is robust in the sense that the general scheme cannot be blocked unless a regime blocks access to every site hosting user-submitted content. But there doesn't seem to be a compelling reason to use it unless and until all of the simpler methods get blocked.
I write all of this as someone who also wrote a program a few years ago that was meant to serve as a more robust back-up, in case a more popular method of circumventing censorship ever got shut down by the censors. In my case, I thought that most censoring regimes would start blocking all popular Web proxy sites, so I wrote an install script called "Circumventor" that would let you set up a Web server and James Marshall's CGIProxy script on your home computer, turning it into a mini-Web-proxy site. I assumed that eventually, most people in censored countries would have to rely on someone in a non-censored country to set up a private Web proxy like this and e-mail them the URL, once China and Iran got their act together and started blocking most publicly known Web proxy sites. But that never happened, partly because Web proxy sites are now springing up faster than most censors' databases can keep up with. So the web proxy install script fell by the wayside -- but that's good news, because it means that nobody really needed it, since the simpler, more straightforward methods continued to work. Why pester your cousin in the U.S. to set up a Web proxy for you, when most Web proxies you can find in Google are not even blocked yet?
And so it goes for Collage. It sounds like a perfectly fine idea, and it will be great news all around if nobody ever actually has to use it, because the censors never get around to blocking all of the simpler alternatives.
if the Chinese government found out that some Gmail users were using Gmail to receive anti-government messages from the U.S., the censors wouldn't be able to eavesdrop on https-protected connections to find out which users were receiving the messages or what they said, so there would be no information for them to demand that Google turn over to them.
In this case, I'd say the Chinese government would already have the IP address of the party in question, and the time span(s) during which they connected to Yahoo (or Yawhoever) via https. Seems to me that's plenty of information for them to go knocking on Yahoo's door and demand full session details.
If libertarians are so opposed to effective government, why don't they all move to Somalia?
The summary says "...as long as they can exchange encrypted messages over Gmail and AIM."
That's a pretty tall order if you are in the type of situation where you need to do that because of censorship. Even in the US (which I would call average good in regards to exchanging ideas freely there were efforts to block/slow down encrypted communications (DES, http://en.wikipedia.org/wiki/Data_Encryption_Standard). If you are somewhere where the protection of encryption for "legitimate" concerns (like discussing why your brother whom held up a sign disappeared), I am willing to bet use of crypto is not safe. It makes far more sense to put crypto messages into stenography such as this. I know I would if I was sending encrypted messages out of fear of the content of my conversation.
Wow, sent an e-mail as suggested when clicking on "use classic" banner, and got a fast response that addressed my msg
Ok but how to do you communicate the "protocol" to your audience which may be scattered around the globe? And how do you guarantee communicating the "protocol" hasn't been compromised? As soon as the "protocol" is discovered it becomes easy to begin censoring again. I suppose it could work if you could be face to face with the person you're trying to communicate with and manually give them the "protocol" but if you can do that then you can just exchange public keys too and use the standard public key cryptography setup.
I came to the datacenter drunk with a fake ID, don't you want to be just like me?
Obviously, what they need to do is apply this technique to embed the message in spam messages, in the random dictionary garbage or images in the spam. The recipient then just has to know which spam messages to check for the hidden messages.
Now, we just need someone to do this to show how to smuggle information in/out of the major spam-email-producing countries, and perhaps there will suddenly be more interest in shutting down spammers.
The false assertion is that because gmail and other email can be fully encrypted that the CCCP/"surveillance state of choice" will have no information upon which to demand information. This is false as long as gmail and others track IP addresses, and they do for data-mining and advertising purposes.
how the hell is having encrypted messages in your email account "deniable"? It seems like the whole premise of this article is that "Tha Goog won't give you up, man!". If the "censors" can get yahoo to hand it over, google will too.
The whole point of collage is that nobody knows if there is data hidden in the images or if they're regular old images. i.e. the only person that can "hand over" the data is the sender or receiver, none of the middle-men.
People who have no idea about what they're talking about should shut up.
a Blackberry version would be useful for people living in Saudi Arabia, UAE, India and most importantly, the US.
How about a web based client interface for browsing encrypted content that is dispersed throughout the web to increased readership of closed circle content and a trust system for automatically sharing access to friends?
Open Standards Portal
I hate to break the news, but this sort of thing is more easily recovered than you might think. It's one of the basic, elemental things that people in the business of reading some one else's mail have done for years. All it takes is a few messages to build a statistical base, and away it goes.
The problem with steno is that the program has to leave footprints in the image file so it can extract the encoded text. If the BBG (Big Bad Government) knows what those footprints look like they can search the web for images that contain them. After 9/11 there was a lot of interest in terrorists using steno to communicate, so someone decided to search the whole Internet for images with known steno identifiers. Now where did I read about that...oh yeah: http://slashdot.org/yro/01/09/26/1418252.shtml
"I'm not a quack, I'm a mad scientist! There's a difference." - Dr. Cockroach
Some cryptography 101:
Plausible dependability in cryptography means that even if someone suspects there is hidden encrypted data in a data set, they can't prove it, even if they have full knowledge of the protocol.
What is presented here is automated steganography over image sites with many users (hiding the information). If the surveillance entity intercepts such messages and analyses them, they will know that *something* is there, though they won't be able to read it.
Anyway, what it boils down is, that you can't just say there is no message if someone confronts you, and this might very well lay the foundations for your gravestone in countries where the governing entities have a somewhat undemocratic method of dealing with things.
On the other hand, if they don't like you, and really suspect you are up to no good, they will probably shoot you anyway, evidence or not.
But I thought it'd be more fun to actually send steganographic stuff, so I coded up a little bit of stuff in matlab (what I was using at the time) that merged a jpeg and a stream of ascii, alternately adding and subtracting the bits of the ascii from the jpeg values. The resulting pictures looked just like pictures: it wasn't visually obvious.
Then I'd post the unmodified pictures in an unlinked directory on my website (this was pre-flickr) so she could download the originals and subtract out the difference.
This would have been easily defeated by the chinese firewall just re-encoding jpegs that passed through to a slightly different size or quality, but they never did so it worked fine. But it was a pain in the butt to actually *use*.
But it'd be even more of a pain in the butt to detect.
Nostalgia's not what it used to be.
> The commercial and freeware products today do most certainly leave traces.
To convince you that undetectable steganography is possible, think about the following algorithm (which, I admit, has a very, very low ratio of information to carrier). While generating the images I want to use for my carrier data, I set my camera to snap 250 images each time rather than 1. If the scene and the camera are at all realistic, there will be enough entropy in the sets of 250 images so that I can always (for all practical purposes) select one image out of each set of 250 images such that 4 bits of a cryptographic hash of it prefixed by a secret key is a particular nybble.
The encrypted message is then just a sequence of images, one per nybble, where none of the images has been altered in any way whatsoever, merely selected. One has to be careful, however, not to be caught with the other 249 images, and as you have also pointed out, this will not give security against traffic analysis.
Sorry if you already knew this, I see you aren't the original poster, who gave the impression that good steganography was more or less impossible.