nybble41 t1_jbdba8a wrote

Any steganography system will assume that the adversary doesn't have access to the original file to check the hash. Obviously if they do then the fact that the file was altered in some fashion can't be hidden, though you might be able to provide some other plausible excuse for the changes (e.g. compression).

The claim here is that it's impossible to distinguish the files containing messages from others of the same type. In other words given two images, one with a message and one without, there is no analysis which could say which one contained the message without the decoding key. There is nothing inherently impossible about this on par with perpetual motion machines; it's just extremely difficult to get right when you don't have control over the encoding you're trying to blend in with.

A simpler task would be to hide a message in a highly redundant format of your choosing. For example, any data can be encoded in 2x the original space as interleaved bits from two bitstreams A and B where A consists of strong (pseudo-)random bits and B is the original data XOR A. Both A and B will appear random, but A XOR B gives the original data. (One plausible reason to do this might be to avoid long runs of 0's or 1's in electronic signals or radio transmissions.) Given such an encoding you could replace the random bits (A) with the ciphertext of your hidden message, which should be indistinguishable from noise, and compute B as usual. For anyone without the key there is no way to tell whether the interleaving of A and B contains a hidden message, but someone with the key can simply apply it to the "random" bits.

Of course for this to function as steganography people would need to use this encoding when they weren't sending hidden messages, which is not very likely, or else the encoding itself would give it away. However, real data formats can have similar properties where there is an element of randomness in the encoding. The trick is to substitute random-seeming ciphertext in place of natural noise without leaving any traces. This is the same basic principle as replacing low-order bits in an image with ciphertext, except it's actually not that easy to blend in since natural low-order bits aren't completely devoid of patterns and bias.