How to do embedding steganography securely

Steganography is the art and science of hiding secret messages in communications over a public channel in a way that conceals the fact that there is a hidden message. Embedding stegosystems are stegosystems that do the concealment by embedding a hiddentext message into a given covertext to generate a normal-looking stegotext. Many practical embedding stegosystems have been proposed to embed hiddentext in various media such as images, video, audio, and text documents in multiple languages. There have been some recent attempts to formalize steganographic security notions and to construct stegosystems that are provably secure under those notions. In these models, covertness is defined as either statistical or computational indistinguishability between covertexts and stegotexts. However, thus far, none of the analyzed systems are embedding stegosystems — all of the schemes based on these notions assume either precise knowledge of the covertext distribution or the existence of a black box sampling oracle capable of drawing random samples from the true covertext distribution. These schemes are thus impractical or irrelevant in scenarios where the covertext distribution is unknown, under control of the sender, or too complex to sample from efficiently. These scenarios include many of the media thus far proposed for practical embedding stegosystems, including natural images, video clips, voice conversations, and text documents. In this paper, we address the above-mentioned issue of impracticality by focusing on practical embedding stegosystems and formal security notions. We give formal definitions of embedding stegosystems and their underlying embedding and authenticated encryption schemes, then formally define three steganographic security properties: covertness, privacy, and integrity against meaningful attacks. Moreover, we characterize the relations among the proposed security notions which concrete proofs. We also provide a practical generic construction for embedding stegosystems based on cryptographic primitives, and we give reduction proofs that the construction is secure under all of our proposed security properties, assuming the security of the underlying cryptographic primitives. Most practical stegosystems allow users to choose a specific covertext and embed a secret message in that covertext to produce a stegotext. Following our approach guarantees that such systems simultaneously achieve covertness, privacy, and authenticity.