Substitution based systems

The basic idea behind these systems is to substitute the redundant parts of the cover object with the stego message. Many available steganographic tools use this method like StegoDos[6], Hide and Seek[7], Steganos[8]

Least Significant Bit Substitution

This is by far the most popular way of embedding secret messages with simplicity. The basic idea here is to embed the secret message in the least signifcant bits of images. This works because the human visual system is not acute enough to pick out changes in color. Changes in luminance are much better picked out by our visual system.

A naive algorithm for LSB substitution would be to take the first M cover pixles where M is the length of the secret message to be hidden in bits. And then every pixel's last bit is replaced by one of the message bits. This is the simplistic case; we could get away with replacing more than one bit also . See the figures later in this page for examples of this. The problem with such an approach as above is that you end up having the first region of the image having different statistics than the rest of the image

Among various improvements possible to the LSB scheme one of the more effective/common ones is to seed a pseudo-random number generator and then use the numbers output. The basic algorithm to do this is shown below[4]:

Encoding algorithm



Decoding algorithm



Implementation

Simple LSB

The first implementation consists of a simple but very effective scheme . The idea is to take two images of the same size and replace n LSB of every pixel of the cover image with n most significant bits of the image to be hidden. The results are shown below:

The left hand side column represent the two original images - the top left one being the cover image and the bottom left being the stego/secret image to be hidden; the right hand side column represents the modified source image (modified in the sense that it contains the secret image) on the top and the extracted image at the bottom


LSB substitution (4 bits)


Another demo highlighting the same principle (all of these are LSB substitution of 4 bits in the cover image with 4 MSBs of the secret image)





The next image has the same algorithm applied to it except that if one looks carefully one can realize that it has more artifacts than usual. This illustrates the fact that this method is definitely dependent on the kind of images and many






LSB using PRNG

I then used the PRNG method to generate random locations to encode the bits as per the algorithm detailed above. In this case I chose to embed a text message inside the image. The source code listing is present in the code section. The downside is that the two parties have to share the key and this problem is mitigated somewhat because they really need to share only the seed to be applied to the same PRNG


Palette Sorting

Many image formats use palettes. The palette contains only a subset of the colourspace and assuming it has K colors the palette is an indexed pair of (i, K) where K is the color vector and i the index. The index is then used in the image data to lookup the colour. For images with less number of colours this provides a very efficient implementation. Some common formats which use this scheme are BMP and GIF

There are two obvious ways to exploit the palette-image for steganography. One of the ways is to manipulate the palette ; the other is to manipulate the image data. In general the preferred approach is to sort the palette so that neighboring colors are perceptually similar before they start the encoding process. EzStego[9] for example uses this technique.

There are many approaches for palette sorting of the image. One way would be to computer the color values to be sorted as sqrt(r^2+ g^2 + b^2) ; the other better way would be to use the Y (luminance) component of the YCbCr scale which is represented in relation to RGB as :

Y = 0.299R + 0.587G + 0.114B
Cb = 0.5 + (B-Y)/2
Cr = 0.5 + (R-Y)/1.6


There are other schemes among which of note is the one proposed by Fridrich[10] which does not need the palette to be sorted. Another scheme is to use dithering to reduce the total number of values and then double the entire palette; thereby all the entries are slightly modified. After this stage, each color value of the dithered image corresponds to two palette entries from which one will be chosen based on the message bit. Many tools like S-Tools[11] and MandelSteg[12] use this approach

Implementation

The algorithm I used for palette sorting is implemented as follows
  1. Find index of the pixel's luminance value in the sorted RGB palette.
  2. Get 1 bit from the binary message; replace LSB of the index.
  3. Find new RGB color that the index now points to in sorted palette
  4. Find index of the new RGB color in original palette.
  5. Change pixel to the index of the new RGB color


For the above algorithm I used the YCbCr luminance value instead of RGB euclidean distance for sorting the palette. The source code section has the listing of the implementation in Matlab