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!)