Steganography and Digital Watermarking: introduction

Steganography comes from the Greek and literally means "covered writing".[JJ98-1] It is one of various data hiding techniques, which aims at transmitting a message on a channel where some other kind of information is already being transmitted. This distinguishes steganography from covert channel techniques, which instead of trying to transmit data between two entities that were unconnected before.

In this paper we'll consider two different applications of steganography:

The first is what we call classical steganography, and its aim is that of transmitting a message by means of another innocent or casual-looking medium
The second is invisible digital watermarking, which purpose is to assess the ownership or integrity of some pieces of information, named after the watermarks we are used to see on bills or legal documents for the same purpose. It can be used also to provide additional informations on a message inside the message itself.

A sample scenario for classical steganography can be the "Prisoners' Problem", formulated by Simmons in 1983, where Alice and Bob were in jail, and were planning an escape plan. Only, all of their communication was passed through the warden, Willie, and if Willie discovered an encrypted message, he would send them into solitary confinement. Thus, they had to exchange their messages in a covert way.[AP97]

The scenario for digital watermarking is much more from the real world: someone wants to be able to enforce his copyright over some informations or to check their integrity, and embeds some data in the informations themselves for this purpose.

In the copyright protection problem, we can distinguish between proper watermarking or fingerprinting. In the former the entity that embeds the data wants only to be able to show its ownership over it, so basically it inserts the same message in every copy of the informations. In fingerprinting the same entity wants to be able to tell who between the recipient of the data misused it, so it embeds personalized messages in every issued copy.[AP97]

Data hiding techniques can also be classified with respect to the extraction process:

cover escrow methods need both the original piece of information and the encoded one in order to extract the embedded data.
blind or oblivious schemes can recover the hidden message by means only of the encoded data.

Blind data hiding is usually preferred nowadays, since it is usually impractical to distribute certified copies of the original medium.[MBR98]

Both classical steganography and digital watermarking are based on a fundamental assumption: it is quite easy to foil the human senses. This can lead to a simple formula: given an original piece of data d, there is a threshold t below which any changes to the data won't be spotted by a person. t is depended on the experience of the observer, but there is a minimum that's beyond the capabilities of the human senses. Thus, we can always afford to make a change c on d without being spotted, as long as

d + i < t [JJ98-2]

If the matter is, instead, to foil some technically gifted attacker, then we can rephrase the formula using the entropy function H(): assuming that the message we insert is perfectly encrypted, then it is indistinguishable from random data, so the entropy will be strictly additive. The entropy of the stego-medium S will be given by the sum of the entropy of the cover C and of the embedded message M:

H(S) = H(C) + H(M)

And the embedded message would be undetectable if:

The entropy H(M) is much less than the uncertainty in the attacker's measurement of H()
H(C) is reduced by some means before processing, so it is restored by adding H(M)

As a rule of thumb, we must give the attacker as little stego-data as we can, so he won't be able to gather any good measurement of entropy. [AP97]

What distinguishes classical steganography from invisible digital watermarking in the very end is that in the former what is important is the hidden message and not what a casual observer can see, while in watermarking we are adding content to some data which are important by themselves, for the purpose of completing them or protecting them.

This distinction also arises from a basic tradeoff that anyone who attempts to hide data in other data faces: the one between the ratio of hidden informations over the normal ones, and the subsequent robustness of the embedded message.

Roughly, this leads to a simple formula: given a piece of information in which we want to hide some data and being sure that the data is ideally undetectable, we have

amount_of_hidden_data x robustness = constant

Now, what we have supposed is that classical steganography is used as a service which is important for both the transmitter and the receiver. Hence we'll want to push up as much as we can the amount of data hidden, and eventually losing robustness.

On the other hand, for digital watermarking we have a completely different setting: the watermark is inserted by the transmitter, and it must avoid any receiver could be able to remove, counterfeit or destroy it by any means. This assumption demands that the watermark be as robust as it can. We can satisfy this need since a watermark is usually represented by a very small amount of data, not violating our equation.

Another topic that this paper will deal with is steganalsys, a series of techniques aimed at either discovering and extracting a hidden message or "destroying" it. Steganalisys is very similar to criptoanalisys for what regards the technical means it uses and the different kinds of attacks. [JJ98-2]

References:

Previous:cover

Next: a brief history

Matteo Fortini