Steganography 11- Indexed Images and their Palettes

• Download source files - 11.9 Kb
• Download updated Cross Format Application - 68.6 Kb

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.

Thinking about Indexed Pictures...

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); }
              
            //add color
            indexInNewPalette = (byte)newPalette.Add(color);
            colorIndexList = new ColorIndexList(random);
            colorIndexList.Add(indexInNewPalette);
            colorIndexToNewIndices.Add(n, colorIndexList);
        }
        
        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
          indexInNewPalette = (byte)newPalette.Add(newColor);
          //add the new index to the list of alternative indices
          colorIndexList.Add(indexInNewPalette);
        }

        //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),
    ImageLockMode.ReadWrite,
    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;
        messageByte = messageStream.ReadByte();
      }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 bitmap file header
  //...
  //...
    
  //write bitmap info header
  //...
  //...
    
  //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){
  //load the carrier image
  Bitmap bmp = new Bitmap(sourceFileName);
  BitmapData bmpData = bmp.LockBits(
    new Rectangle(0,0,bmp.Width, bmp.Height),
    ImageLockMode.ReadWrite,
    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)){
        //message's length has been read
        messageStream.Seek(0, SeekOrigin.Begin);
        messageLength = new BinaryReader(messageStream).ReadInt32();
        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...