Steganography 14 - What Text Lists, GIF Images, and HTML Pages have in common

/* This class has been written by
 * Corinna John (Hannover, Germany)
 * cj@binary-universe.net
 * 
 * You may do with this code whatever you like,
 * except selling it or claiming any rights/ownership.
 * 
 * Please send me a little feedback about what you're
 * using this code for and what changes you'd like to
 * see in later versions. (And please excuse my bad english.)
 * 
 * WARNING: This is experimental code.
 * Exception handling has been omitted,
 * to keep the code readable to people who want
 * to understand the algorithm.
 * Please do not expect "Release Quality".
 * */

#region Using directives

using System;
using System.Drawing;
using System.Drawing.Imaging;
using System.Text;
using System.IO;
using System.Collections;
using System.Runtime.InteropServices;

#endregion

namespace SteganoList {
    public class PaletteUtility {

        /// <summary>Hide a message in an image by sorting the palette entries</summary>
        /// <param name="image">Carrier image</param>
        /// <param name="message">Message</param>
        /// <returns>Resulting image</returns>
        internal static Bitmap Hide(Bitmap image, Stream message)
        {
            //list the palette entries an integer values
            int[] colors = new int[image.Palette.Entries.Length];
            for (int n = 0; n < colors.Length; n++) {
                colors[n] = image.Palette.Entries[n].ToArgb();
            }
            
            //initialize empty list for the resulting palette
            ArrayList resultList = new ArrayList(colors.Length);
            
            //initialize and fill list for the sorted palette
            ArrayList originalList = new ArrayList(colors);
            originalList.Sort();

            //initialize list for the mapping of old indices to new indices
            SortedList oldIndexToNewIndex = new SortedList(colors.Length);
            
            Random random = new Random();
            bool messageBit = false;
            int messageByte = message.ReadByte();
            int listElementIndex = 0;
            
            //for each byte of the message
            while (messageByte > -1) {
                //for each bit
                for (int bitIndex = 0; bitIndex < 8; bitIndex++) {
                    
                    //decide which color is going to be the next one in the new palette
                    
                    messageBit = ((messageByte & (1 << bitIndex)) > 0) ? true : false;

                    if (messageBit) {
                        listElementIndex = 0;
                    } else {
                        listElementIndex = random.Next(1, originalList.Count);
                    }

                    //log change of index for this color

                    int originalPaletteIndex = Array.IndexOf(colors, originalList[listElementIndex]);
                    if( ! oldIndexToNewIndex.ContainsKey(originalPaletteIndex)) {
                        //add mapping, ignore if the original palette contains more than one entry for this color
                        oldIndexToNewIndex.Add(originalPaletteIndex, resultList.Count);
                    }

                    //move the color from old palette to new palette
                    
                    resultList.Add(originalList[listElementIndex]);
                    originalList.RemoveAt(listElementIndex);
                }

                //repeat this with the next byte of the message
                messageByte = message.ReadByte();
            }

            //copy unused palette entries
            foreach (object obj in originalList) {
                int originalPaletteIndex = Array.IndexOf(colors, obj);
                oldIndexToNewIndex.Add(originalPaletteIndex, resultList.Count);
                resultList.Add(obj);
            }

            //create new image
            Bitmap newImage = CreateBitmap(image, resultList, oldIndexToNewIndex);

            return newImage;
        }

        /// <summary>Extract a message from the order of palette entries in an image</summary>
        /// <param name="image">Carrier image - the message will be removed from it</param>
        /// <returns>Message</returns>
        internal static Stream Extract(ref Bitmap image)
        {
            //initialize empty writer for the message
            BinaryWriter messageWriter = new BinaryWriter(new MemoryStream());

            //list the palette entries an integer values
            int[] colors = new int[image.Palette.Entries.Length];
            for (int n = 0; n < colors.Length; n++) {
                colors[n] = image.Palette.Entries[n].ToArgb();
            }

            //initialize list for the mapping of old indices to new indices
            SortedList oldIndexToNewIndex = new SortedList(colors.Length);

            //initialize and fill list for the carrier palette
            ArrayList carrierList = new ArrayList(colors);
            
            //sort the list to restore the original palette
            ArrayList originalList = new ArrayList(colors);
            originalList.Sort();
            int[] unchangeableOriginalList = (int[])originalList.ToArray(typeof(int));

            //the last palette entry holds no data - remove it
            
            //log change of index for this color
            int sortedPaletteIndex = Array.IndexOf(unchangeableOriginalList, (int)carrierList[carrierList.Count - 1]);
            oldIndexToNewIndex.Add(carrierList.Count - 1, sortedPaletteIndex);

            carrierList.RemoveAt(carrierList.Count - 1);

            int messageBit = 0;
            int messageBitIndex = 0;
            int messageByte = 0;
            byte messageLength = 0;
            int color;
            int carrierListIndex;

            //for each color that carries a bit of the message
            for (carrierListIndex = 0; carrierListIndex < carrierList.Count; carrierListIndex++) {
                
                //decide which bit the entry's position hides
                
                color = (int)carrierList[carrierListIndex];

                if (color == (int)originalList[0]) {
                    messageBit = 1;
                } else {
                    messageBit = 0;
                }

                //log change of index for this color
                sortedPaletteIndex = Array.IndexOf(unchangeableOriginalList, color);
                oldIndexToNewIndex.Add(carrierListIndex, sortedPaletteIndex);

                //remove the color from the sorted palette
                originalList.Remove(color);

                //add the bit to the message
                messageByte += (byte)(messageBit << messageBitIndex);

                messageBitIndex++;
                if (messageBitIndex > 7) {
                    if (messageLength == 0) {
                        //first hidden byte was the message's length
                        messageLength = (byte)messageByte;
                    } else {
                        //append the byte to the message
                        messageWriter.Write((byte)messageByte);
                        if (messageWriter.BaseStream.Length == messageLength) {
                            //finished
                            break;
                        }
                    }
                    messageByte = 0;
                    messageBitIndex = 0;
                }
            }

            //map unused palette entries
            carrierListIndex++;
            for (; carrierListIndex < carrierList.Count; carrierListIndex++) {
                sortedPaletteIndex = Array.IndexOf(unchangeableOriginalList, (int)carrierList[carrierListIndex]);
                oldIndexToNewIndex.Add(carrierListIndex, sortedPaletteIndex);
            }
            
            //create new image
            image = CreateBitmap(image, unchangeableOriginalList, oldIndexToNewIndex);

            //return message
            messageWriter.Seek(0, SeekOrigin.Begin);
            return messageWriter.BaseStream;
        }

        /// <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="oldIndexToNewIndex">Relations map: newIndex = oldIndexToNewIndex[oldIndex]</param>
        /// <returns>The new bitmap</returns>
        internal static Bitmap CreateBitmap(Bitmap bmp, IList palette, SortedList oldIndexToNewIndex)
        {

            int sizeBitmapInfoHeader = 40;
            int sizeBitmapFileHeader = 14;

            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));

            //get the new color index for each pixel
            int pixelColorIndex;
            object tmp;
            for (int pixelIndex = 0; pixelIndex < pixels.Length; pixelIndex++) {
                pixelColorIndex = pixels[pixelIndex];
                tmp = oldIndexToNewIndex[pixelColorIndex];
                pixels[pixelIndex] = Convert.ToByte(tmp);
            }

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

            //write bitmap file header
            bw.Write(System.Text.ASCIIEncoding.ASCII.GetBytes("BM")); //BITMAPFILEHEADER.bfType;
            bw.Write((Int32)(55 + imageSize)); //BITMAPFILEHEADER.bfSize;
            bw.Write((Int16)0); //BITMAPFILEHEADER.bfReserved1;
            bw.Write((Int16)0); //BITMAPFILEHEADER.bfReserved2;
            bw.Write(
                (Int32)(
                sizeBitmapInfoHeader
                + sizeBitmapFileHeader
                + palette.Count * 4)
                ); //BITMAPFILEHEADER.bfOffBits;

            //write bitmap info header
            bw.Write((Int32)sizeBitmapInfoHeader);
            bw.Write((Int32)bmp.Width); //BITMAPINFOHEADER.biWidth
            bw.Write((Int32)bmp.Height); //BITMAPINFOHEADER.biHeight
            bw.Write((Int16)1); //BITMAPINFOHEADER.biPlanes
            bw.Write((Int16)8); //BITMAPINFOHEADER.biBitCount
            bw.Write((UInt32)0); //BITMAPINFOHEADER.biCompression
            bw.Write((Int32)(bmpData.Height * bmpData.Stride) + (palette.Count * 4)); //BITMAPINFOHEADER.biSizeImage
            bw.Write((Int32)0); //BITMAPINFOHEADER.biXPelsPerMeter
            bw.Write((Int32)0); //BITMAPINFOHEADER.biYPelsPerMeter
            bw.Write((UInt32)palette.Count); //BITMAPINFOHEADER.biClrUsed
            bw.Write((UInt32)palette.Count); //BITMAPINFOHEADER.biClrImportant

            //write palette
            foreach (int color in palette) {
                bw.Write((UInt32)color);
            }
            //write pixels
            bw.Write(pixels);

            bmp.UnlockBits(bmpData);

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

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