Steganography

From CryptoWiki
Jump to: navigation, search

Back
Steganography: word for word means "secret writing". Derived from the Greek: steganos - secret; graphy - record. Steganography is the science of secret transmission of information by hiding the fact of transmission at all. Do not confuse it with cryptography, which hides the content of the message, but not its presence. These two methods of information protection are not interchangeable, however, they perfectly complement each other.

Contents

Security challenge

Even in the ancient world, people have tried to solve the problem of information security. Two main directions of solutions were steganography and cryptography. The objective of cryptography is to prevent understanding of message, if an attacker succeed in getting the message. The objective of steganography, on the contrary, is to hide the message so that an attacker does not know about its presence.

There are many ways to hide the presence of message. However, all these methods have one common thing. The message to send is embedded in some unsuspected object. The object is then passed to the recipient.

In ancient times people used wooden boards covered with wax. The information was scratched out on a board, then the board was covered with wax. On top of this wax something insignificant was written. People also used their slaves' heads - slave shaved its hair, master wrote ( tattooing )something on slave's head and waited for the hair to grow back again. Then master sent his slave to the addressee, who shaved his hair and delivered a message. This method of communication was relatively safe, but required a lot of time. Later they began to use the sympathetic (invisible ) ink. Probably each of us in his childhood wrote secret messages with milk or apple juice. Such messages could be read by simply heating the paper. Also, there are ways to hide information in the text with the replacement of one or more words, or by making minor errors.

Due to the rapid development of computer technology, tools of computer steganography are being increasingly used. Now the message is inserted into the digital signals having analogous nature, namely, speech, images, video, audio.

Interest in steganography is so high due to several factors: firstly, in some countries there are restrictions on the use of cryptographic protection tools, and secondly, there is the problem of protecting the rights of ownership of digital information.
Currently, there are three closely related application of steganography with the same roots: hiding data (messages), digital watermarks and captions.

Hiding data imposes certain requirements on the size of the container. It should be several times larger than the introduced data. Consequently, there are difficulties with the choice of container, because in most cases embedded messages have a large size. Digital watermarks (DW) are used to protect the copyright of digital images, photographs, or other digitized works of art. Basic requirements - reliability and resistance to distortions.

To embed DW they use methods, which are more sophisticated than methods for embedding messages or just headers, despite the small amount of embedded information.

The third appliction - captions ( headlines ). It's mainly used for marking images in large electronic storage of digital images, audio and video.

Steganographic methods in this case are used to embed an identifying header and the other individual attributes of file. The implemented headers have a small volume, and the requirements for them are minimal: the headings should make slight distortion and be resistant to major changes.

Nowadays people have developed the following requirements for stegosystem (steganosystems)[Г00]:

  • Properties of the container should be modified so that the change can not be identified by visual inspection. This requirement determines the quality of the implemented hiding messages: to ensure unhampered transmission of stegomessage through the communication channel, it should not attract the attention of the attacker.
  • Stegomessage must be resistant to distortions, including the harm from an attacker. In the process of transmitting the image (sound or other container) may undergo various transformations: decrease or increase, converted into another format, etc. In addition, it can be compressed, including using a lossy data. An embedded message should be saved.
  • They must use error correction codes to save the integrity of embedded message.
  • The embedded message can be duplicated for increased reliability.

And also according to the[Г02,S96]:

  • The number of steps for embedding / extracting information should be acceptable.
  • They must provide reasonable capacity.
  • Methods for authorized persons must ensure the integrity and authenticity.
  • The offender can not reveal the contents of secret messages, even if he has an idea of how stegosystem ​​works, but does not know the key. (This requirement is quite difficult, since it is assumed that the offender should not even know about the fact of transmittion of message.)

Stegosystems' general view is shown in Figure 1.

Рисунок 1E new.png

Figure 1. General view of steganosistem

Main Page

Theoretical issues

There are certain problems of using steganography systems. The main problem - the problem of sustainability. For a fixed size of container reliability dependence on the size of hiding messages can be seen in Figure 2.

Рисунок 2E new.png

Figure 2.Dependence between the size of the embedded message and reliability of hiding for a fixed size of container

It is thus seen that it is impossible to embed a large amount of information without visually noticeable distortion of the container. The problem of steganography is to strike a balance between the quality of the container after insertion, the size of the embedded message (bandwidth), container's degree of resistance to modifications and analisys. Depending on the particular problem solving by steganography, different methods that require a different amount of embedded information are used. Accordingly, for a variety of purposes the use of different methods of steganography is optimal.

Images:

According to [Г02], the majority of the researches are now focused on the research of image-containers. This is due to several reasons:

  • Nowadays there is practically significant problem of protection of paintings and photographs from the illegal distribution and use;
  • Contemporary formats can store the image in a good quality. It is necessary for this to store a large amount of image information, and, therefore, it is possible to embed a messages of large size or of increased robustness;
  • The size of container is known in advance, the insertion is not limited with requirements of installation in real time;
  • In the majority of real images there is a noise structure, which is well suited for embedding information;
  • The system of the human vision is not very sensitive to small changes in image color , brightness , contrast, distortion near the contours and content of the noise;
  • Methods of digital image processing are now well established.

It is worth noting that the latter reason also causes difficulties in establishing robust algorithms, because the better compression techniques become, the less opportunities, suitable for embedding extraneous information, are available. It was initially supposed to put the information in the least significant bits to reduce visibility. Now the integration takes place in the most important areas of the image, the failure of which would lead to the complete degradation of the image. Therefore, current algorithms take into account properties of the human visual system. Many algorithms use transformations that are used in compression algorithms (discrete cosine transform (DCT) - JPEG, wavelet transform - JPEG2000). There are three possibilities: to embed information in the original image, to embed information along with the image compression or to embed information in an already compressed image. The first and the second methods are the most common.
Algorithms for hiding data in the spatial domain implement message in the original image. The advantage of these methods is that they don't require computationally complex transformations of the image. The message is implemented by manipulation of color components (r (x, y), g (x, y), b (x, y)) or by manipulation of brightness l(x, y) = f (r (x, y), g (x , y), b (x, y)).
Image compression algorithms use different conversion. Algorithms for hiding data in the transform domain implement a message in the transformation, such as DCT coefficients. The advantage of this mechanism of embedding is that message is stable relative to the image compression. It is advisable to use the same transformation for hiding as intended to the further compression.

Video:

The most popular video coding standards are MPEG-2 and MPEG-4. Steganographic methods used to embed information in the video, compressed by MPEG-2 standard, are designed to work in real time. It should be noted that the methods of embedding messages, which work in real time, should meet a number of requirements , first of all, they should be blind (i.e. the recipient don't know anything about container), and have a low computational complexity. Therefore, the only acceptable methods are methods of embedding data directly into the compressed data stream to avoid unnecessary calculations. It should be noted that the basic idea of ​​MPEG compression is that from the entire stream of data only certain frames are completely transmitted, for the remaining frames only difference from other frames is transmitted.

MPEG use three types of frames :

  • I- frames - intra- frames. They are coded without reference to other frames. They comprise a still image.
  • P- frames - predictable frames that are encoded with reference to the previous adopted (I) or (P) frame.
  • B- frames - right interpolated frames that are encoded by the most complicated way. This frame can be built in several ways - based of the previous frame, based on the next frame and as an interpolation between the previous and next frames.

Image is represented in the format YUV, i.e. one channel luminance Y and two chrominance channels U, V. The image in the luminance channel is substantially black and white image. It is widely known that the human visual system is more sensitive to changes in the luminance channel than to the chrominance channel . Consequently, the U and V components may be subjected to greater compression than Y.

Each component of the I-frame is divided into blocks of 8 * 8 pixels, and then each block is subjected to DCT. After the DCT in each cell block instead of the color put a DCT coefficient. This allows to get two-dimensional power spectrum of the image area. Such a range of images is usually concentrated in the low-frequency coefficients. The smaller the difference between values ​​of the neighboring pixels, the ​​closer to zero are values of the higher-frequency DCT coefficients.

P-frames, as well as B-frames are also divided into blocks of 8 * 8 pixels and then compared with a certain reference picture. Then three cases are possible :

  1. Separate block in the encoded P-frame coincides with the arrangement position in the same reference frame block. Then it is sufficient to indicate that the unit has remained the same.
  2. Separate block in the encoded frame coincides with the reference picture block located in other position. Then it is necessary to specify the encoding vector displacement.
  3. Separate block in the encoded frame may not coincide with one of the blocks of the reference frame. Then he will be fully coded.

Thus, at the lowest level of the MPEG structure are blocks of pixels 8 * 8, represented by 64 DCT coefficients. The block layer may be divided into three areas:

  • The first area - coefficients, where block contains digitized 8 * 8 DCT coefficients, represented by integers. Many of them are usually zero.
  • The second area - pairs. The DCT coefficients are zigzag scanned, and then the coefficients are replaced by pairs consisting of a zero-length series, then the value of non-zero coefficient. Zeroes to the end of block are ignored. For example, if a sequence of 5, 3, 2, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 1, then it is coded as follows (0,5), (0,3), (0,2), (2,4), (8,1).
  • The third area - bits. There previously formed pairs are coded by Huffman code. Each block of DCT coefficients ends with the end marker of the end of block ( EOB ).

From this we can determine that the most computationally simple algorithm is the introduction of data on the block level. Also, a low complexity has algorithm for embedding data into coefficients, while information embedding algorithm operating in a bit field only requires the implementation of additional Huffman coding. From this follows that the entire insertion procedure may consist of 3 steps:

  1. Huffman decoding
  2. Special modifications
  3. Huffman Encoding

Audio:

To work with audio systems people should take into account the requirements for such stegosystems [Г02]:

  • Information to hide must be resistant to the presence of various noise, lossy compression, filtering, analogous-to-digital and digital-to-analogousconversion;
  • Information to hide should not make such a signal distortions, which are perceived by the human hearing system;
  • Attempt to remove hidden information should lead to a significant damage to the container (for DW);
  • Information to hide should not make significant changes in the statistics of the container;

For embedding of information in audio, you can use the same methods as in other forms of steganography. For example, you can replace the least significant bits of container with bits of embedding messages. You can also build stegosystem based on features of human hearing system and the limitations of the audio signals. By its nature, the human ear is a frequency spectrum analyzer, which receives signals in the range of 10 - 20,000 Hz. The human hearing system can be modeled as 26 bandpass filters, bandwidth of which increases with increasing frequency. Changes in the phase of the signal is weaker detected by the human hearing system than changes in amplitude or frequency.
Consequently, there are three ways to embed audio information:

  • Embedding with spectrum enlargement (slightly modification of samples' amplitudes);
  • Embedding with modification of the phase of the audio signal (the initial phase of the signal segment is adjusted according to the implemented data, the next phase of the segments is coordinated with the phase of the initial segment to preserve the phase difference);
  • Embedding with modification of the echo-signal time delay.

Steganographic primitives and/or protocols

In this section we discuss some examples of stegoalgorythms.

Images:

As an example of the algorithm of hiding data in the spatial domain let's consider Kutter's algorithm (Kutter) [KJB97]. According to this algorithm, the insertion is made in the blue channel, as its changes are the least visible to human eyes. Suppose we want to transmit one bit of classified information si. I = {R, G, B} - container. p = (x, y) - a position in which you are embedding (pseudo-randomly selected).
Embedding occurs in the blue channel by modifying the brightness l(p) = 0.299r(p) +0.587g(p) +0.114b(p) as follows:

F1.png

q - is a constant, the value of which varies depending on the purpose of the scheme. The higher is its value, the greater is robustness of embedding, but the more visible is distortion of the container. To extract information you do not needed the original image (blind extraction). The value of the original pixel value is predicted by its neighbors (cross of pixels 7*7). Estimate of (b ^)(p) is prepared as follows:

Ф2.png

where c - the number of pixels up/down/left/right of the estimated (c = 3). Suppose that in the process of embedding a bit cr was repeated once. Then get cr ratings of one bit. The secret bit is obtained by averaging the difference between the derived value and the real pixel value​​:

Ф3.png

The sign of this difference determines the value of the embedde bit. However, it should be noted that noone can guaranty the right determination of the value of the secret bit.
As an example of the algorithm of hiding data in the transformation domain let's consider Koch's algorithm (Koch) [KZ95]. Typically, the container is divided into blocks of 8*8 pixels. For each block is obtained a matrix of 8*8 DCT coefficients. Assume that the coefficients are denoted as c_b(j,k), where b - block number, and (j,k) - position of the coefficient within the block.

In this algorithm 1 bit of information is embedded in the block of DCT coefficients. Pseudo-randomly two DCT coefficient are selected. The difference between these coefficients should be larger than some positive number or less than some negative:

F5.png

To find the value of the secret bit the reverse procedure is performed:

F6.png

.

Video:

As an example of the algorithm of hiding data on the coefficients level let’s consider the algorithm of Wu (Wu) [W97]. It was suggested to add a pseudorandom array (embedding message) to the DC-coefficients of the video, which is compressed by MPEG (using only luminance values in the I-frames.) DC-coefficients are DCT coefficients in the top left corner of each 8*8 block. They carry the biggest amount of iinformation about the unit and their strong distortion is noticeable to the eye.

  1. With the secret key a pseudorandom array of integers {-1,1} is generated, having the same dimensions as the I-frame.
  2. The resulting array is modified in accordance with embedded links and is multiplied by some gain.
  3. Values of DC-coefficients of each I-frame are added to the modified array.

The authors of this method argue that the video quality is significantly degraded, when using this method. Therefore, to maintain the required quality of the resulting video, it’s necessary to take low (<1) coefficient of intensification, and the number of pixels for one message bit must be sufficiently large (>> 100,000). As an example of the algorithm of hiding data on the bits level let’s consider an algorithm which was proposed in [LLB96,L96,LLB97,LLB98,L98,LL98]. This method is similar to the replacement of the least significant bits. Message of sequence of l bits bj (j = 0, 1, 2, ..., l-1) is embedded in the video stream, compressed by standard MPEG. For this purpose choosen suitable codewords are modified by replacing the least significant bit on the value of bj. To make the changes not seen after decoding the video stream, and for not change its size, it is necessary to choose the codewords that satisfy several conditions:

  • Same zero-length series;
  • The difference between the values of the DCT coefficients is equal to 1;
  • Equal length of codewords.
    .

Audio:

As an example of the algorithm of data hiding using spectrum enlargement let’s consider the Bassia’s algorithm (Bassia) [BP]. Let’s suppose there are N audio samples x(i), i = 0,1, ..., N, where the value of N>=88200. To embed information is used function, which must take into account the characteristics of human hearing system to avoid too noticeable distortion of signal - f(x i), w(i)), where w(i) is the countdown of message, varying in a certain interval [ -a, a] (a - constant). Counting the resultant signal is defined as follows: y(i) = x(i) + f(x(i), w(i)). Detection proceeds as follows:

Ф4.png

.

As an example of the algorithm of hiding data by modifying the phase of the audio signal let’s consider the Bender’s algorithm (Bender) [BGML96]. Audio encoding is performed as follows:

  • Sound signal s [i], (0 <= i <= I-1) is divided into a series of short segments (N pieces) sn [i], (0 <= n <= N). This is shown in Figure 3.

Рисунок 3 new.png

Figure 3. Splitting the original signal into a series of segments

  • To the n-th segment of signal sn [i] applies k-point discrete Fourier transform, where K = I/N, and are created matrix of phases φn (wk) and matrix of amplitudes An (wk)), (0 <= k <= K -1).
  • Memorized phase difference between every two adjacent segments

Ф7.png

  • The binary data sequence is represented as

    Ff8.png

    .
  • Including the phase difference, a new matrix of phases is created for n>0.
  • Stegocoded signal is obtained by applying inverse discrete Fourier transform to the original matrix of the amplitudes and to the modified matrix of phases.

As an example of the algorithm of hiding data by changing the echo-signal time delay let’s consider the Bender’s algorithm (Bender) [BGML96]. When encoding uses two time delay: for 0 and for 1, but they are both less than that on which the human hearing system can recognize echoes. Accordingly, the delay between the original signal and its echo carries message bits. If you want to embed multiple bits, the original signal is divided into sections, which are treated as separate signals and penetrated by one bit of information. It should be noted that nowadays there are no stegoalgoritms, which are resistant to any actions of the attacker. Therefore, durability of each of the existing algorithms can only be assessed in a particular environment under certain conditions.

Practical issues

With the development of means of personal computing became possible to create software solutions to many of steganographic algorithms. At this point in the Internet you can find over a hundred programs, with release date from 1995 to our days. It should be noted that commercial solutions are a little fraction of the total and often represents a complete solution to hide information on a personal computer. Many of the non-commercial steganography applications are divided into two main types:

  • Independent
  • Built-in

Unlike stand-alone applications, built-in applications necessarily need a program through which the user himself shall work with the files. The most popular in this area is the program (file manager) Total Commander, which can build quite well-known plug-ins DarkCryptTC and RedJPEG. Despite the popularity of the above solutions, the Internet can discover a lot more independent decisions, for example:

  • BmpPacker
  • ImageXYZ
  • Puff

These products are designed for embedding any binary files in containers, that can be of a variety of video/audio formats (AIFF, MP3, NEXT / SUN, WAV), (3GP, FLV, MP4, MPG, SWF, VOB), images (BMP , JPG, PCX, PNG, TGA, ICO, TIFF, JPEG, JPEG200), as well as executable files, such as exe. or dll. Moreover, the majority of them support the advanced encryption algorithms, ranging from the RC6 and ending TWOFISH and RIJNDAEL, however, the vast majority of steganoaplications work on the principle of LSB (embedded in the least significant bit) or fill unused fields.

Glossary

Bibliography

Go to biblyography

Main Page

Kryuchkova A., Kolobov D.