12,892,320 members (49,425 online)
alternative version

#### Stats

86.3K views
58 bookmarked
Posted 25 Jun 2004

# Steganography 11- Indexed Images and their Palettes

, 25 Jun 2004 CPOL
 Rate this:
Hiding data of any kind in indexed Bitmaps like PNG and GIF.

## Introduction

This article explains how binary data can be hidden in indexed (8 bits/pixel) bitmaps. The method described here is completely different from the one we used for RBG (24 bit/pixel) bitmaps, but reading the first part of this series, Steganography - Hiding Messages in the Noise of a Picture, might help understanding the differences between these two kinds of bitmaps.

In the previous articles, we have hidden the bits of the secret messages in the lower bits of the color values. In an indexed bitmap, the color values don't stand in the pixels, but in the palette:

24 bits per pixel, no palette:

8 bits per pixel, palette of arbitrary size (1 - 256):

So, your first idea might be to hide the message in the palette instead of in the pixels. But a palette contains 256 or less colors, it could carry only a few bytes. This problem leads to the second idea: Make the palette larger, copy the color values!

If we duplicate the palette, we get two alternative indices for every color. Hey, this could be a better way! Referencing a color from the first two lines could mean "message bit is 0", and referencing the same color from the lower two lines could mean "message bit is 1". But again there is a problem: A palette with repeated colors is stupid. Nobody would ever use such a palette. A double-palette is much too obvious.

So we cannot just copy the palette, but we can add colors that differ a little from the existing colors. Let's say, for each color in the palette, we add two similar (but not equal) color values:

Now we have a stretched palette, but the presence of a hidden message is just as obvious, because only one of three colors is actually being used. That's no problem at all, we only have to change the pixels, so that a few of the pixels that referenced one original color references one of its copies.

Now we can hide something in the pixels. For a message-bit of "1", we let a pixel reference the original color; for a message-bit of "0", we let it reference on of the added colors. But how do we extract the hidden message? If we only know the stretched palette, we cannot see which colors are copied from the original palette, and which have been made up.

Is there a way to mark a color value as "taken from the original palette"? Well, there are three least significant bits in every one. This name is not correct. Due to common monitors and weak human eyes, the lowest bit of a color component should be called not significant at all. Setting or resetting the first bit of a color component is how we can stretch a palette and mark every color as copied or new:

## How to un-optimize a palette

While creating the new palette, we have to keep track of the copied and added colors, because later on, when we change the pixels to reference every color in the new palette, we have to be able to reference an original color (even Blue component) to hide a "0", or a changed color (odd Blue component) to hide a "1". The `StretchPalette` method uses a `HashTable` to map every index from the old palette to the corresponding indices in the new palette.

```/// <summary>
/// Creates a larger palette by duplicating and changing
/// the colors of another palette
/// </summary>
/// <param name="oldPalette">The palette to stretch</param>
/// <param name="maxPaletteSize">Count of colors in the new palette</param>
/// <param name="newPalette">Receives the new palette entries</param>
/// <param name="colorIndexToNewIndices">
/// Receives a Hashtable with the original indices as the keys,
/// and the corresponding new indices as the values
/// </param>
public void StretchPalette(ColorPalette oldPalette, int maxPaletteSize,
ref ArrayList newPalette, ref Hashtable colorIndexToNewIndices) {

//collects the new palette entries
newPalette = new ArrayList(maxPaletteSize);
//maps each old index to the new indices
colorIndexToNewIndices = new Hashtable( oldPalette.Entries.Length );

Random random = new Random();
byte indexInNewPalette;
Color color, newColor;
ColorIndexList colorIndexList;

//repeat the loop if necessary
while(newPalette.Count < maxPaletteSize){
//loop over old palette entries
for(byte n=0; n<oldPalette.Entries.Length; n++){
color = oldPalette.Entries[n]; //original color

if(colorIndexToNewIndices.ContainsKey(n)){
//this color from the original palette already has
//one or more copies in the new palette
colorIndexList = (ColorIndexList)colorIndexToNewIndices[n];
}else{
if(color.B%2 > 0){ //make even
color = Color.FromArgb(color.R, color.G, color.B-1); }

colorIndexList = new ColorIndexList(random);
}

if(newPalette.Count < maxPaletteSize){
//create a non-exact copy of the color
newColor = GetSimilarColor(random, newPalette, color);

if(newColor.B%2 == 0){ //make odd
newColor = Color.FromArgb(
newColor.R, newColor.G, newColor.B+1);
}

//add the changed color to the new palette
//add the new index to the list of alternative indices
}

//update the Hashtable
colorIndexToNewIndices[n] = colorIndexList;

if(newPalette.Count == maxPaletteSize){
break; //the new palette is full - cancel
}
}
}
}```

If you have read the piece of code (if not, you can do it after downloading the complete source), you may have seen a method `GetSimilarColor`. This method creates a variation of a color value:

```private Color GetSimilarColor(Random random,
ArrayList excludeColors,
Color color) {

Color newColor = color;
int countLoops = 0, red, green, blue;
do{
red = GetSimilarColorComponent(random, newColor.R);
green = GetSimilarColorComponent(random, newColor.G);
blue = GetSimilarColorComponent(random, newColor.B);
newColor = Color.FromArgb(red, green, blue);
countLoops++;
//make sure that there are no duplicate colors
}while(excludeColors.Contains(newColor)&&(countLoops<10));

return newColor;
}

private byte GetSimilarColorComponent(Random random, byte colorValue){
if(colorValue < 128){
colorValue = (byte)(colorValue *
(1 + random.Next(1,8)/(float)100) );
}else{
colorValue = (byte)(colorValue /
(1 + random.Next(1,8)/(float)100) );
}
return colorValue;
}```

Now, we have a new palette, and a key/value table to map old indices to new indices. The next step is hiding the message's bits while copying the image. `System.Drawing.Image` has got a property `Palette` of the type `ColorPalette`. This is one of the most restrictive classes I've ever seen. It has two properties, `Flags` and `Entries` - both are read only. `ColorPalette` allows to change the colors of the existing palette, but we cannot add any colors. I didn't want to search hours for a clean .NET solution, writing a new bitmap is easier:

```/// <summary>
/// Creates an image with a stretched palette,
/// converts the pixels of the original image for
/// that new palette, and hides a message in the converted pixels
/// </summary>
/// <param name="bmp">The original image</param>
/// <param name="palette">The new palette</param>
/// <param name="colorIndexToNewIndices">
/// Hashtable which maps every index in the original palette
/// to a list of indices in the new palette.
/// </param>
/// <param name="messageStream">The secret message</param>
/// <param name="keyStream">
/// A key that specifies the distances between two
/// pixels used to hide a bit
/// </param>
/// <returns>The new bitmap</returns>
private Bitmap CreateBitmap(
Bitmap bmp, ArrayList palette,
Hashtable colorIndexToNewIndices,
Stream messageStream, Stream keyStream) {

//lock the original bitmap
BitmapData bmpData = bmp.LockBits(
new Rectangle(0,0,bmp.Width, bmp.Height),
PixelFormat.Format8bppIndexed);

//size of the image data in bytes
int imageSize = (bmpData.Height * bmpData.Stride)+(palette.Count * 4);

//copy all pixels
byte[] pixels = new byte[imageSize];
Marshal.Copy(bmpData.Scan0, pixels, 0, (bmpData.Height*bmpData.Stride));

int messageByte=0, messageBitIndex=7;
bool messageBit;
ColorIndexList newColorIndices;
Random random = new Random();

//index of the next pixel that's going to hide one bit
int nextUseablePixelIndex = GetKey(keyStream);

//loop over the pixels
for(int pixelIndex=0; pixelIndex<pixels.Length; pixelIndex++){

//get the list of new color indices for the current pixel
newColorIndices=(ColorIndexList)colorIndexToNewIndices[pixels[pixelIndex]];

if((pixelIndex < nextUseablePixelIndex) || messageByte < 0){
//message complete or this pixel has to be skipped - use a random color
pixels[pixelIndex] = newColorIndices.GetIndex();
}else{
//message not complete yet

if(messageBitIndex == 7){
//one byte has been hidden - proceed to the next one
messageBitIndex = 0;
}else{
messageBitIndex++; //next bit
}

//get a bit out of the current byte
messageBit = (messageByte & (1 << messageBitIndex)) > 0;
//get the index of a similar color in the new palette
pixels[pixelIndex] = newColorIndices.GetIndex(messageBit);
nextUseablePixelIndex += GetKey(keyStream);
}
}

//Now we have the palette and the new pixels.
//Enough data to write the bitmap !

BinaryWriter bw = new BinaryWriter( new MemoryStream() );

//...
//...

//...
//...

//write palette
foreach(Color color in palette){
bw.Write((UInt32)color.ToArgb());
}

//write pixels
bw.Write(pixels);

bmp.UnlockBits(bmpData);

Bitmap newImage = (Bitmap)Image.FromStream(bw.BaseStream);
newImage.RotateFlip(RotateFlipType.RotateNoneFlipY);

bw.Close();
return newImage;
}```

## Extracting a hidden Message

Extracting a message from an image is much easier than hiding it. There is only one palette, and we don't have to care about new and old indices. We just use the distribution key to locate a carrier pixel, check the referenced color for an odd or even Blue component, save the found bit (which is `color.B % 2 > 0`), and continue with the next pixel until the message is complete:

```public void Extract(Stream messageStream, Stream keyStream){
Bitmap bmp = new Bitmap(sourceFileName);
BitmapData bmpData = bmp.LockBits(
new Rectangle(0,0,bmp.Width, bmp.Height),
PixelFormat.Format8bppIndexed);

//copy all pixels
byte[] pixels = new byte[bmpData.Stride*bmpData.Height];
Marshal.Copy(bmpData.Scan0, pixels, 0, pixels.Length);

Color[] palette = bmp.Palette.Entries;
byte messageByte=0, messageBitIndex=0, pixel=0;
int messageLength=0, pixelIndex=0;

//read pixels until the message is complete
while((messageLength==0) || (messageStream.Length < messageLength)){
//locate the next pixel that carries a hidden bit
pixelIndex += GetKey(keyStream);
pixel = pixels[pixelIndex];

if( (palette[pixel].B % 2) == 1 ){
//odd blue-component: message-bit was "1"
messageByte += (byte)(1 << messageBitIndex);
} //else: messageBit was "0", nothing to do

if(messageBitIndex == 7){ //a byte is complete
//save and reset messageByte, reset messageBitIndex
messageStream.WriteByte(messageByte);
messageBitIndex = 0;
messageByte = 0;

if((messageLength == 0)&&(messageStream.Length==4)){
messageStream.Seek(0, SeekOrigin.Begin);
messageStream.SetLength(0);
}
}else{
messageBitIndex++; //next bit
}
}

//release the carrier bitmap
bmp.UnlockBits(bmpData);
bmp.Dispose();
}```

## Example

The images must have 128 or less colors, otherwise we cannot add an alternative palette entry for each color. I don't think this is actually a restriction, because most indexed GIF or PNG images have less colors. If you need all 256 colors for an image, you should consider using a 24 bit/pixel format. Now, let's see how the palette changes...

This is Sternchen Canary, the model for this imaging session:

Here are the same image as an indexed PNG with 64 colors, and its palette:

Start the demo application, select the image as the carrier and another file as the key...

...and click Hide. The generated image contains a palette of 192 colors, and it does not look much different, though all colors are being used and none is repeated.

The generated image you see above carries a hidden message of 42 words that can be extracted with the demo application (not the cross-format application). The key to this message is somewhere in the fifth picture of this article, you'll need a hexadecimal editor to type its 11 bytes into a key file...

## Share

 Software Developer Germany
Corinna lives in Hanover/Germany and works as a C#/Delphi developer.

## You may also be interested in...

 First Prev Next
 Dynamic watermark nikhil94212-Aug-12 16:14 nikhil9421 2-Aug-12 16:14
 Re: Dynamic watermark Corinna John4-Aug-12 2:23 Corinna John 4-Aug-12 2:23
 Image Steganography using LSB algorithms in Windows Phone in C# 174t29-May-11 22:22 174t 29-May-11 22:22
 Re: Image Steganography using LSB algorithms in Windows Phone in C# Corinna John4-Aug-12 2:25 Corinna John 4-Aug-12 2:25
 Reading and displaying palette color image prashant_1441-Mar-10 23:56 prashant_144 1-Mar-10 23:56
 Re: Reading and displaying palette color image Corinna John4-Aug-12 2:37 Corinna John 4-Aug-12 2:37
 Algorithm LogiB2-Feb-10 23:34 LogiB 2-Feb-10 23:34
 Robustness of this method lonelywind19824-Sep-07 18:17 lonelywind1982 4-Sep-07 18:17
 LockBits exception mwolf@onet.pl10-Jan-07 1:10 mwolf@onet.pl 10-Jan-07 1:10
 Re: LockBits exception mwolf@onet.pl10-Jan-07 1:11 mwolf@onet.pl 10-Jan-07 1:11
 steganalysis amalla8430-Jun-06 10:02 amalla84 30-Jun-06 10:02
 JPEG image processing with C memoboy16-Jan-05 10:08 memoboy 16-Jan-05 10:08
 Re: JPEG image processing with C Corinna John16-Jan-05 20:36 Corinna John 16-Jan-05 20:36
 VC6++ HELP HOW??? cnncnn18-Aug-04 20:18 cnncnn 18-Aug-04 20:18
 nice work Jeremy Falcon30-Jun-04 11:31 Jeremy Falcon 30-Jun-04 11:31
 Great Article dstrbd_one29-Jun-04 10:56 dstrbd_one 29-Jun-04 10:56
 A thoroughly enjoyable article Marc Clifton27-Jun-04 16:25 Marc Clifton 27-Jun-04 16:25
 Re: A thoroughly enjoyable article Corinna John27-Jun-04 19:42 Corinna John 27-Jun-04 19:42
 Smart... HumanOsc27-Jun-04 2:33 HumanOsc 27-Jun-04 2:33
 Re: Smart... Corinna John27-Jun-04 7:22 Corinna John 27-Jun-04 7:22
 Re: Smart... HumanOsc27-Jun-04 10:01 HumanOsc 27-Jun-04 10:01
 Re: Smart... Corinna John28-Jun-04 19:58 Corinna John 28-Jun-04 19:58
 Last Visit: 31-Dec-99 18:00     Last Update: 27-Apr-17 10:08 Refresh 1