===== Steganography and steganalysis =====

Steganography is the art and science of hiding information by embedding a message within another. Only the sender and the intended recipient of the message know that there is hidden information within.

The word steganography originates from the Greek words __steganos__ (cover or protect) and __graphein__ (write).

Steganography tries to hide the presence of message; cryptography tries to hide the contents of a message.

The ancient Greeks used the wooden backing of a wax tablet before applying the beeswax or the shaved head of a slave in order to hide their secret messages.

There are several possibilities how information can be hidden in digital media:
  * By using the noise in an image or a sound file
  * By spreading the information (over several pixels,…)
  * By adoption of a statistical model (e.g. q very often is followed by u in languages like english or german)
  * By miming real content (e.g. of a text)
  * By replacing randomness (with hidden information)
  * By changing order
  * By splitting the information into pieces (which can/should take different routes to it's destination)
  * By hiding the origin
 
There is no doubt that criminals are highly interested in using steganography in order to hide their communication – but that group is of course not the only one who might be using it. 

This technology also can support the weak – e.g.:
  * Anonymously seeking advice
  * Anonymously informing authorities
  * Anonymously leaking information to the media
  * Anonymously joining a discussion without losing face/…

Further uses are:
  * Digital watermarks
  * Document tracking tools
  * Digital signatures embedded in documents

In the following text I will only concentrate on digital steganography and use the word steganography synonymously.

According to the theory of information hiding, the legitimate or official communication within sender and recipient is called __covertext__, the hidden information embedded is called __stegotext__.

A stegosystem is an algorithm to create a stegotext with an embedded message. The goal of this algorithm is to hide a stegotext in a way that it just looks like the covertext.

The more formal way of a definition of a __stegosystem__ is:

Let $C$ be a distribution on a set C of covertexts. A stegosystem is a triple of probabilistic polynomial-time algorithms (SK, SE, SD) with the following properties.

  * The key generation algorithm SK takes as input the security parameter n and outputs a bit string sk, called the stego key.
  * The steganographic encoding algorithm SE takes as inputs the security parameter n, the stego key sk and a message m to be embedded and outputs an element c of the covertext space C, which is called stegotext. The algorithm may access the covertext distribution $C$.
  * The steganographic decoding algorithm SD takes as inputs the security parameter n, the stego key sk, and an element c of the covertext space C and outputs either a message m or a special symbol S. An output value of S indicates a decoding error, for example, when SD has determined that no message is embedded in c.

The probability that the decoding algorithm outputs the correct embedded message is called the __reliability__ of a stegosystem.

__References__:

  - [[target=_blank|http://en.wikipedia.org/wiki/Steganography|Steganography]] (Wikipedia, the free encyclopedia)
  - Pfitzmann, B. (1996). Information hiding terminology. Information Hiding, First International Workshop,   Lecture Notes in Computer Science, vol. 1174, ed. R. Anderson. Springer, Berlin, pages 347-350
  - Encyclopedia of Cryptography and Security, edited by Henk C. A. van Tilborg, ISBN-13: 978-0387-23473-1, 2005, pages 159-164
  - Wayner, Peter (2009). Disappearing cryptography: Information hiding: Steganography & watermarking, 3rd ed., Elsevier Inc, Burlington, MA 01803, USA