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.
public void StretchPalette(ColorPalette oldPalette, int maxPaletteSize,
ref ArrayList newPalette, ref Hashtable colorIndexToNewIndices) {
newPalette = new ArrayList(maxPaletteSize);
colorIndexToNewIndices = new Hashtable( oldPalette.Entries.Length );
Random random = new Random();
byte indexInNewPalette;
Color color, newColor;
ColorIndexList colorIndexList;
while(newPalette.Count < maxPaletteSize){
for(byte n=0; n<oldPalette.Entries.Length; n++){
color = oldPalette.Entries[n];
if(colorIndexToNewIndices.ContainsKey(n)){
colorIndexList = (ColorIndexList)colorIndexToNewIndices[n];
}else{
if(color.B%2 > 0){
color = Color.FromArgb(color.R, color.G, color.B-1); }
indexInNewPalette = (byte)newPalette.Add(color);
colorIndexList = new ColorIndexList(random);
colorIndexList.Add(indexInNewPalette);
colorIndexToNewIndices.Add(n, colorIndexList);
}
if(newPalette.Count < maxPaletteSize){
newColor = GetSimilarColor(random, newPalette, color);
if(newColor.B%2 == 0){
newColor = Color.FromArgb(
newColor.R, newColor.G, newColor.B+1);
}
indexInNewPalette = (byte)newPalette.Add(newColor);
colorIndexList.Add(indexInNewPalette);
}
colorIndexToNewIndices[n] = colorIndexList;
if(newPalette.Count == maxPaletteSize){
break;
}
}
}
}
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++;
}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:
private Bitmap CreateBitmap(
Bitmap bmp, ArrayList palette,
Hashtable colorIndexToNewIndices,
Stream messageStream, Stream keyStream) {
BitmapData bmpData = bmp.LockBits(
new Rectangle(0,0,bmp.Width, bmp.Height),
ImageLockMode.ReadWrite,
PixelFormat.Format8bppIndexed);
int imageSize = (bmpData.Height * bmpData.Stride)+(palette.Count * 4);
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();
int nextUseablePixelIndex = GetKey(keyStream);
for(int pixelIndex=0; pixelIndex<pixels.Length; pixelIndex++){
newColorIndices=(ColorIndexList)colorIndexToNewIndices[pixels[pixelIndex]];
if((pixelIndex < nextUseablePixelIndex) || messageByte < 0){
pixels[pixelIndex] = newColorIndices.GetIndex();
}else{
if(messageBitIndex == 7){
messageBitIndex = 0;
messageByte = messageStream.ReadByte();
}else{
messageBitIndex++;
}
messageBit = (messageByte & (1 << messageBitIndex)) > 0;
pixels[pixelIndex] = newColorIndices.GetIndex(messageBit);
nextUseablePixelIndex += GetKey(keyStream);
}
}
BinaryWriter bw = new BinaryWriter( new MemoryStream() );
foreach(Color color in palette){
bw.Write((UInt32)color.ToArgb());
}
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),
ImageLockMode.ReadWrite,
PixelFormat.Format8bppIndexed);
byte[] pixels = new byte;
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;
while((messageLength==0) || (messageStream.Length < messageLength)){
pixelIndex += GetKey(keyStream);
pixel = pixels[pixelIndex];
if( (palette[pixel].B % 2) == 1 ){
messageByte += (byte)(1 << messageBitIndex);
}
if(messageBitIndex == 7){
messageStream.WriteByte(messageByte);
messageBitIndex = 0;
messageByte = 0;
if((messageLength == 0)&&(messageStream.Length==4)){
messageStream.Seek(0, SeekOrigin.Begin);
messageLength = new BinaryReader(messageStream).ReadInt32();
messageStream.SetLength(0);
}
}else{
messageBitIndex++;
}
}
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...