The Case Against Steganography In Perceptually Encoded Media

[Peter Wayner]

>Cypherpunks,


This is certainly a point that many people are coming to believe. But 
I think you have to be careful with taking it to extremes. Are there 
problems with changing the character of noise? Yes, but as you 
pointed out it may be possible to sculpt the inserted information to 
conform to the statistical character of the overall file. One of the 
simplest tricks is just to insert a relatively small message in a 
relatively large file. Any statistical changes will be lost in the 
noise. This is a pretty practical solution because there are plenty 
of images that take hundreds of thousands if not millions of bytes. A 
thousand bytes of text gets lost pretty quickly.

It's also important to remember that there are many tricks that avoid 
making changes in the usual way. I'm currently very intrigued with 
the potential to rearrange lists of items. (You can try out an applet 
here: http://www.wayner.org/books/discrypt2/sorted.php)

I guess it's important not to let an obsessive attention to 
mathematical perfection  prevent you from accomplishing something 
cool. After all, every RSA key can be factored eventually, but we 
still use the system because it's practically secure.

-Peter


>
>I had an interesting revelation last night. It's a bad idea to use
>perceptually-coded media to embed steganographic data. By definition, it
>means making the coder make decisions that it otherwise would not have made.
>If the coder is good, then the coder's decisions are not arbitrary but
>rather each bit is focused on producing the minimal representation necessary
>for adequate presentation to humans. This means that encoding extra "random"
>data on top of this will always produce compressed output that is of lower
>quality than the original. From an information theory standpoint, if you're
>tacking on a data stream to compressed output, the stream that is the sum of
>the two contains more information and must be represented with more bits.
>For example, to attack steganographically-encoded pictures, the pictures
>could be analysed and those with lower-quality encoding than expected would
>be flagged for analysis as suspect.
>
>The conclusion is remarkable (to my little mind, at any rate): since most
>media transmitted over the Internet is perceptually compressed (JPG, MOV,
>AVI, MP3, etc.) the efforts to steganographically encode data within most
>Internet media are fundamentally doomed.
>
>Where, then, can one hide information streams? The answer is wherever
>*random* information is communicated. (Even just partial randomness is okay;
>I've got a paper on this I hope to be presenting soon!)