pondělí 4. ledna 2010

Steganography - an invisible ink in digital age

Steganography is an ancient art of invisible communication. It permits to exchange private messages between two parties without raising suspicion of potential eavesdroppers. Steganography achieves its goal by hiding the private message into innocuous looking object, which in present times is usually digital image, audio file, movie, etc. The art of steganography is very old. First documented use of steganography goes back to ancient Greece to 5 century before christ. The way, how steganography was used was innovative, but not very practical. Heredotus, a historian, tells the story about the Histiaeus, who wanted to warn the Ionian city of Miletus before invasion of Persians. Histiaeus correctly expected that if his slave delivering the message is captured by Persians and the Persians become suspicious that the slave carries something important, they will kill the slave and the message will not be delivered. To avoid this, Histiaeus shaved the slave's head and tattooed the message on slave's scalp. When slave's hairs grew back, he sent him to Miletus, the slave had delivered the message, and Miletus was saved. Throughout the centuries, more practical ways of steganography were discovered. As an examples, we can name invisible ink (remember “Rychle sipy”), microdots used by Nazi's during 2nd World War, messages written on the back of post stamps, etc. Presently, digital objects such as images, audio and video files, are the most used hideout medias for steganography, since they offer high capacity, they are easy to use, and easy to communicate (Internet).

Why people uses steganography, when there is cryptography? Although both fields achieves the same thing, there is a substantial difference. When cryptography is used, everyone who eavesdrop the message knows, that communicating parties wants to hide something, because communicated message looks like gibberish, i.e. sequence of random bits. This can have deadly consequences, because in countries like China, Russia, etc., the use of cryptography is either prohibited or severely limited. On the other hand, eavesdropped steganographic message looks (or should look) perfectly normal.
The following example shows a letter of Gov. A. Schwarznegger to Tom Ammiano. The letter seems to be normal, but if you know what to read, you will get another message.

This brings us to the next question, who uses steganography? We can guess that it is used by secret services, but quite naturally, we do not have any details about it. On the other hand, media has reported that the steganography was used to mask illegal activities such as coordination of terrorist networks, distribution of child pornography, theft of trade secrets, etc. Because of this malicious use, there is a need for algorithms / methods detecting the presence of hidden message in the object under investigation. This complementary problem of recognizing objects carrying hidden messages is called steganalysis.

How does steganography works?

The simplest algorithm for steganography in digital images is LSB replacement. During hiding of the message, LSB replacement replaces least significant bit of selected pixels by bits from the message (here we assume greyscale image). Since human eye cannot recognize a difference between two neighboring levels of grey (e.g. grey 127 and grey 128), there will be no visible difference between both images. When receiver want to pull out the message, he simply read it from least significant bits of correct pixels. The pixels which were used to hide the message are determined by the secret key shared between sender and receiver.
A simple example of LSB replacement to hide a unencrypted message is exercised on the following images. One image is clean while the other contains a piece of art. Clicking on the image reveals its LSB.

Although above example shows that it is relatively easy to create steganography invisible to human eyes and the steganography itself is an easy task, there exists methods which allows to detect the presence of message hidden by LSB replacement with very high accuracy. Therefore, for practical use, we have a stronger requirement, we require the statistical undetectability. Statistical undetectability means that there does not exists a method capable of recognizing objects with and without hidden message. Of course in practice, we are never sure that such method exists. And from exactly this reason steganographic schemes are being broken and replaced by improved or completely different ones.

Modern steganography and steganalysis is multi-disciplinary field comprising digital signal processing, image modelling, image compression, statistics, machine learning, coding theory, and many others. My personal interest within the field is an application of machine learning algorithms to solve various task around steganalysis, for example determining algorithm used to hide the secret message, estimating length of hidden message, determining compression history of images to improve accuracy of steganalysis, etc. And because it is good to know weapons of your opponent, I am playing with designs of new steganographic algorithms as well.

In June 2010, we are going to launch international challenge in steganalysis called Break Our Steganographic System (BOSS). If you are interested, visit http://boss.gipsa-lab.grenoble-inp.fr and join the game.

Tomas Pevny

1 komentář: