Steganography 12 - Regions with different data density

• Download source files for C# Express (.NET 2.0) - 48 Kb
• Download source files for SharpDevelop (.NET 1.1) - 27.6 Kb

Introduction

A well known method of steganoanalysis is to search one coloured area of the image for variations. In diffuse areas where every pixel has a different color than its neighbors, variations by hidden bits are hard to detect, but most pictures also contain areas with smooth colors. Look at this one:

• The blue sky in the upper middle should not contain hidden data, because there are nearly no natural variations in the colors.
• The clouds have more shades of blue, but anything that's not blue would be easy to find. If any data has to be hidden in the clouds, not more than one bit per pixel should be changed.
• It is the same with the trees on the right: changing the higher bits would produce light colors, but only dark pixels are allowed here, so the capacity of each pixel is reduced to one or two bits.
• The boats and the beach on the left side are better. They contain red, yellow, white, blue, green... We can change up to 7 bits in this region, nobody will notice anything.

To escape from simple variations analysis, we'll hide our secret message only in these regions, and with adjusted "bit rates":

Edit and Store Regions

Just as in the preceding examples, we need a carrier bitmap, a secret message, and a key.

The new feature is a Region Editor which lets the user define regions and their capacities.

An easy way to draw a region is to click the points of a polygon. So, we let the user click on the image, and add every clicked point to a polygon. A polygon can be closed with a double click, then the next click starts a new polygon:

private void picImage_MouseUp(object sender, MouseEventArgs e){
   if (e.Button == MouseButtons.Left){
      if (isDoubleClicked){
         //ignore the MouseUp event following a double click

         isDoubleClicked = false;
      }
      else{
           if (!isDrawing){
              //start a new polygon

              isDrawing = true;
              drawingPoints = new ArrayList();
              cleanImage = picImage.Image;
              bufferImage = new Bitmap(cleanImage.Width, cleanImage.Height);
           }

           AddPoint(e.X, e.Y);
      }
   }
}

When a polygon is being closed by a double click, we have to make sure that it does not overlap one of the already existing polygons. If the new polygon intersects another polygon, we merge the two regions. If the p�lygon stands alone, we create a new region and add it to the list. ctlRegions is a RegionInfoList, this control displays statistics and input fields for each region.

private void picImage_DoubleClick(object sender, EventArgs e){
   if (drawingPoints.Count > 2){
      isDrawing = false;
      isDoubleClicked = true;

      Point[] points = (Point[])drawingPoints.ToArray(typeof(Point));
      GraphicsPath path = new GraphicsPath();
      path.AddPolygon(points);

      if (!UniteWithIntersectedRegions(path, points)){
         RegionInfo info = new RegionInfo(path, points, picImage.Image.Size);
         drawnRegions.Add(info); //add to regions

         ctlRegions.Add(new RegionInfoListItem(info)); //add to list

      }

      ReDrawImages(true);
   }
}

If another region has been drawn, we have to update the map and the statistics block. ReDrawImages paints the regions onto the source image and the map overview. (The map overview and the gradient brush are not necessary, they're just a nice visual effect.)

/// <summary>Display the source image with the regions on it in [picImage],

/// and only the regions in [picMap]</summary>

/// <param name="updateSummary">true: call UpdateSummary() when finished</param>

private void ReDrawImages(bool updateSummary){
    //create empty images

    Image bufferImageNoBackground =
          new Bitmap(baseImage.Width, baseImage.Height);
    Image bufferImageWithBackground = new
          Bitmap(baseImage.Width, baseImage.Height);

    //get graphics

    Graphics graphicsWithBackground =
             Graphics.FromImage(bufferImageWithBackground);
    Graphics graphicsNoBackground =
             Graphics.FromImage(bufferImageNoBackground);

    //draw/clear backgrounds

    graphicsNoBackground.Clear(Color.White);
    graphicsWithBackground.DrawImage(baseImage, 0, 0,
                  baseImage.Width, baseImage.Height);

    //draw regions

    foreach (RegionInfo info in drawnRegions){

        PathGradientBrush brush =
             new PathGradientBrush(info.Points, WrapMode.Clamp);
        brush.CenterColor = Color.Transparent;

        if (info == selectedRegionInfo){
           //mark the region that's selected in the list

            brush.SurroundColors = new Color[1] { Color.Green };
        }else{
            brush.SurroundColors = new Color[1] { Color.Red };
        }

        //draw the region

        graphicsWithBackground.DrawPolygon(new
                            Pen(Color.Black, 4), info.Points);
        graphicsNoBackground.DrawPolygon(new
                            Pen(Color.Black, 4), info.Points);
        graphicsWithBackground.FillRegion(brush, info.Region);
        graphicsNoBackground.FillRegion(brush, info.Region);
    }

    //clean up

    graphicsWithBackground.Dispose();
    graphicsNoBackground.Dispose();

    //show images

    picImage.Image = bufferImageWithBackground;
    picMap.Image = bufferImageNoBackground;
    picImage.Invalidate();
    picMap.Invalidate();

    //update numbers and errors

    if (updateSummary) { UpdateSummary(); }
}

The map has to be stored in the first pixels of the image so that it can be extracted before the rest of the message. That means, we have to embed a header into the image. When extracting the hidden message, we first have to extract the header, read the region information from it, and then we can extract the actual message from those regions. The header can be spread over all pixels from 0/0 to the first pixel in the topmost region. We won't know where the first region begins before we've extracted the map, so we have to store the index of the first pixel that belongs to any region in the header itself. The coordinates of this pixel are not important, because we'll treat the pixels as one long stream, not as rows and columns. A complete header contains these information:

1. (Int32) Index (not coordinates!) of the topmost pixel in the first region.
2. (Int32) Length of the following region data.
3. For every region:
   1. (Int32) Length (Region.GetRegionData().Data.Length)
   2. (Int32) Capacity (Count of bytes to hide in this region)
   3. (byte) Count of used bits per pixel
   4. (byte[]) Region (Region.GetRegionData().Data)

The length of the header depends on the count and the complexity of the regions. When a new region is added in the Region Editor, we must check the new header's length and the position on the topmost region. If there are not enough pixels left between the image's first pixel and the first region, the header cannot be hidden. In that case, we'll display a warning and disable the "Next" button. The regions that are going to carry the actual message have to be big enough, we'll display another warning if the message does not fit into the regions:

private void UpdateSummary(){
   bool isOkay = true; //no errors yet


   long countPixels = 0; //count of selected pixels

   int capacity = 0; //capacity of all regions


   RegionInfo firstRegion = null; //topmost region - not found yet


   //first pixel inside a region - not found yet

   int firstPixelInRegions = baseImage.Width * baseImage.Height;

   //Int32 beginning of first region +

   //Int32 regions length + Byte bits per pixel

   long mapStreamLength = 65;

   foreach (RegionInfo info in drawnRegions) {
      countPixels += info.CountPixels;
      capacity += info.Capacity;

      mapStreamLength += 64; //Int32 RegionData Length + Int32 Capacity

      mapStreamLength += info.Region.GetRegionData().Data.Length * 8;

      //is this region the first one?

      if ((int)info.PixelIndices[0] < firstPixelInRegions) {
         firstPixelInRegions = (int)info.PixelIndices[0];
         firstRegion = info;
      }
   }

   //pixels in the region

   lblSelectedPixels.Text = countPixels.ToString();

   //percent of the image covered by the region

   lblPercent.Text = (100 * countPixels /
    (baseImage.Width*baseImage.Height)).ToString();

   //capacity

   lblCapacity.Text = capacity.ToString();
   if (capacity == messageLength) {
      SetControlColor(lblCapacity, false);
      errors.SetError(lblCapacity, String.Empty);
   } else {
     SetControlColor(lblCapacity, true);
     errors.SetError(lblCapacity,
       "Overall capacity must be equal to the message's length.");
     isOkay = false;
   }

   //header size

   lblHeaderSize.Text = mapStreamLength.ToString() + " Bits";

   //are there enough pixels left for the header?

   if (firstRegion != null) {
      if (firstPixelInRegions > mapStreamLength) {
         lblHeaderSpace.Text = firstPixelInRegions.ToString() + " Pixels";
         SetControlColor(lblHeaderSpace, false);
      } else {
        isOkay = false;
        lblHeaderSpace.Text = String.Format(
            "{0} Pixels - Please remove the topmost region.",
            firstPixelInRegions);
        SetControlColor(lblHeaderSpace, true);
        selectedRegionInfo = firstRegion;
        ctlRegions.SelectItem(firstRegion);
        ReDrawImages(false);
      }
   } else {
     lblHeaderSpace.Text = "0 - Please define one or more regions";
     SetControlColor(lblHeaderSpace, true);
   }

   btnNext.Enabled = isOkay;
}

private void SetControlColor(Control control, bool isError) {
   if (isError) {
      control.BackColor = Color.DarkRed;
      control.ForeColor = Color.White;
   } else {
     control.BackColor = SystemColors.Control;
     control.ForeColor = SystemColors.ControlText;
   }
}

If the regions are big enough, configured for enough capacity and leaves enough space for the header, UpdateSummary will enable the "Next" button. Now, the map and the message can be hidden.

Embed the Data

Until now, we have done nothing except receiving input data about the carrier image. Now, the interesting part begins! In the earlier articles, we used the key to locate pixels, and simply embedded the message. This won't work anymore. We have specific regions over which the data has to be distributed, and the header should be distributed evenly over the available pixels at the beginning of the image. That means, the bytes from the key stream cannot be used directly as the next offset, but we can use them to initialize a pseudo-random number generator. This number generator can choose the next offset:

When the message is extracted later on, we just have to initialize the System.Ramdom object with the same seed (a value from the key stream), and we'll get the same offsets again. But, we need two values to calculate the intervals: the length of the data we want to hide/extract, and the count of the remaining pixels. Let's hide these two Int32 values in the first 64 pixels so that we can read them easily.

public unsafe void Hide(Stream messageStream, Stream keyStream){
    //make sure that the image has RGB format

    Bitmap image = (Bitmap)carrierFile.Image;
    image = PaletteToRGB(image);

    int pixelOffset = 0, maxOffset = 0, messageValue = 0;
    byte key, messageByte, colorComponent;
    Random random;

    BitmapData bitmapData = image.LockBits(
        new Rectangle(0, 0, image.Width, image.Height),
        ImageLockMode.ReadOnly, PixelFormat.Format24bppRgb);

    //go to the first pixel

    PixelData* pPixel = (PixelData*)bitmapData.Scan0.ToPointer();
    PixelData* pFirstPixel;

    //get the first pixel that belongs to a region

    int firstPixelInRegions = image.Width * image.Height;
    foreach (RegionInfo info in carrierFile.RegionInfo){
        info.PixelIndices.Sort();
        if ((int)info.PixelIndices[0] < firstPixelInRegions){
            firstPixelInRegions = (int)info.PixelIndices[0];
        }
    }

    //hide [firstPixelInRegions]

    HideInt32(firstPixelInRegions, ref pPixel);

    //get map stream

    MemoryStream regionData = new MemoryStream();
    BinaryWriter regionDataWriter = new BinaryWriter(regionData);
    foreach (RegionInfo regionInfo in carrierFile.RegionInfo)
    {
        byte[] regionBytes = PointsToBytes(regionInfo.Points);
        regionDataWriter.Write((Int32)regionBytes.Length);
        regionDataWriter.Write((Int32)regionInfo.Capacity);
        regionDataWriter.Write(regionInfo.CountUsedBitsPerPixel);
        regionDataWriter.Write(regionBytes);
    }
    //go to the beginning of the stream

    regionDataWriter.Flush();
    regionData.Seek(0, SeekOrigin.Begin);

    //hide length of map stream

    HideInt32((Int32)regionData.Length, ref pPixel);

Now that the initial values have been stored, we can distribute the regions map over all the available pixels between pixel 65 and the first region:

    pFirstPixel = pPixel; //don't overwrite already written header


    int regionByte;
    while ((regionByte = regionData.ReadByte()) >= 0){
        key = GetKey(keyStream);
        random = new Random(key);

        for (int regionBitIndex = 0; regionBitIndex < 8; ){

            pixelOffset += random.Next(1,
              (int)((firstPixelInRegions-1 - pixelOffset) /
              ((regionData.Length - regionData.Position + 1)*8))
            );
            pPixel = pFirstPixel + pixelOffset;

            //place [regionBit] in one bit of the colour component


            //rotate color components

            currentColorComponent = (currentColorComponent == 2) ? 0 :
                                                  (currentColorComponent + 1);
            //get value of Red, Green or Blue

            colorComponent = GetColorComponent(pPixel, currentColorComponent);

            //put the bits into the color component

            //and write it back into the bitmap

            CopyBitsToColor(1, (byte)regionByte,
                      ref regionBitIndex, ref colorComponent);
            SetColorComponent(pPixel, currentColorComponent, colorComponent);
        }
    }

Now, we have hidden the regions and everything we need to extract them. It is time to get to the point and hide the secret message.

    //begin with the first pixel of the image

    pPixel = (PixelData*)bitmapData.Scan0.ToPointer();
    pFirstPixel = pPixel;

    foreach (RegionInfo regionInfo in carrierFile.RegionInfo){

        //go to first pixel of this region

        pPixel = (PixelData*)bitmapData.Scan0.ToPointer();
        pPixel += (int)regionInfo.PixelIndices[0];
        pixelOffset = 0;

        for (int n = 0; n < regionInfo.Capacity; n++){

            messageValue = messageStream.ReadByte();
            if (messageValue < 0) { break; } //end of message

            messageByte = (byte)messageValue;

            key = GetKey(keyStream);
            random = new Random(key);

            for (int messageBitIndex = 0; messageBitIndex < 8; ){

                maxOffset = (int)Math.Floor(
                  ((decimal)(regionInfo.CountPixels - pixelOffset - 1) *
                    regionInfo.CountUsedBitsPerPixel)/
                   (decimal)((regionInfo.Capacity - n) * 8)
                );

                pixelOffset += random.Next(1, maxOffset);
                pPixel = pFirstPixel + (int)regionInfo.PixelIndices[pixelOffset];

                //place [messageBit] in one bit of the colour component


                //rotate color components

                currentColorComponent = (currentColorComponent == 2) ? 0 :
                                                      (currentColorComponent + 1);
                //get value of Red, Green or Blue

                colorComponent = GetColorComponent(pPixel, currentColorComponent);

                //put the bits into the color component

                //and write it back into the bitmap

                CopyBitsToColor(
                   regionInfo.CountUsedBitsPerPixel,
                   messageByte, ref messageBitIndex,
                   ref colorComponent);
                SetColorComponent(pPixel, currentColorComponent, colorComponent);
            }
        }
    }

    image.UnlockBits(bitmapData);
    SaveBitmap(image, carrierFile.DestinationFileName);
}

Extract the Data

So, we have an image, and want to read a hidden message from it. We have to read the message's bytes in the same order they have been hidden:

1. Get the length of the map data
2. Get the index of the first pixel in the topmost region
3. Use these values to extract the regions
4. Use the regions to extract the message

Let's go and get the regions!

/// <summary>Extract the header from an image</summary>

/// <remarks>The header contains information about

///     the regions which carry the message</remarks>

/// <param name="keyStream">Key stream</param>

/// <returns>The extracted regions with all meta data that

///                is needed to extract the message</returns>

public unsafe RegionInfo[] ExtractRegionData(Stream keyStream) {
    byte key, colorComponent;
    PixelData* pPixel;
    PixelData* pFirstPixel;
    int pixelOffset = 0;
    Random random;

    Bitmap image = (Bitmap)carrierFile.Image;

    BitmapData bitmapData = image.LockBits(
        new Rectangle(0, 0, image.Width, image.Height),
        ImageLockMode.ReadOnly, PixelFormat.Format24bppRgb);

    //go to the first pixel

    pPixel = (PixelData*)bitmapData.Scan0.ToPointer();

    //get firstPixelInRegions

    int firstPixelInRegions = ExtractInt32(ref pPixel);

    //get length of region information

    int regionDataLength = ExtractInt32(ref pPixel);

    //get region information


    pFirstPixel = pPixel;
    MemoryStream regionData = new MemoryStream();

    byte regionByte;
    while (regionDataLength > regionData.Length) {
        regionByte = 0;
        key = GetKey(keyStream);
        random = new Random(key);

        for (int regionBitIndex = 0; regionBitIndex < 8; regionBitIndex++) {
            //move to the next pixel

            pixelOffset += random.Next(1,
               (int)(
                 (firstPixelInRegions - 1 - pixelOffset) /
                 ((regionDataLength - regionData.Length) * 8))
               );
            pPixel = pFirstPixel + pixelOffset;

            //rotate color components

            currentColorComponent = (currentColorComponent == 2) ? 0 :
                                                  (currentColorComponent + 1);
            //get value of Red, Green or Blue

            colorComponent = GetColorComponent(pPixel, currentColorComponent);

            //extract one bit and add it to [regionByte]

            AddBit(regionBitIndex, ref regionByte, 0, colorComponent);
        }

        //write the extracted byte

        regionData.WriteByte(regionByte);
    }

    image.UnlockBits(bitmapData);

Now, we have reconstructed the map stream. To do anything useful with it, we have to reconstruct the regions.

    //read regions from [regionData]


    ArrayList regions = new ArrayList();
    BinaryReader regionReader = new BinaryReader(regionData);

    Region anyRegion = new Region(); //dummy region

    RegionData anyRegionData = anyRegion.GetRegionData(); //dummy region data

    Region region; //extracted region

    byte[] regionContent; //extracted region data

    //extracted region header

    int regionLength, regionCapacity;
    byte regionBitsPerPixel;

    regionReader.BaseStream.Seek(0, SeekOrigin.Begin);
    do {
        //If the program crashes here,

        //the image is damaged,

        //it contains no hidden data,

        //or you tried to use a wrong key.

        int regionLength = regionReader.ReadInt32();
        int regionCapacity = regionReader.ReadInt32();
        byte regionBitsPerPixel = regionReader.ReadByte();
        byte[] regionContent = regionReader.ReadBytes(regionLength);

        Point[] regionPoints = BytesToPoints(regionContent);
        GraphicsPath regionPath = new GraphicsPath();
        regionPath.AddPolygon(regionPoints);

        Region region = new Region(regionPath);
        regions.Add(new RegionInfo(region, regionCapacity,
                        regionBitsPerPixel, image.Size));
    } while (regionData.Position < regionData.Length);

    return (RegionInfo[])regions.ToArray(typeof(RegionInfo));
}

We're nearly finished. Now, we know in which regions the message is embedded, how many bytes are hidden in which region, and how many bits per pixel must be extracted from the pixels.

/// <summary>Extract a message</summary>

/// <param name="messageStream">Empty stream to receive

///                    the extracted message</param>

/// <param name="keyStream">Key stream</param>

public unsafe void Extract(Stream messageStream, Stream keyStream) {

    //lock the bitmap, go to the first pixel, and so on

    //...

    //...


    foreach (RegionInfo regionInfo in carrierFile.RegionInfo) {

        //go to first pixel of this region

        pFirstPixel = (PixelData*)bitmapData.Scan0.ToPointer();
        pPixel = pFirstPixel + (int)regionInfo.PixelIndices[0];
        pixelOffset = 0;

        for (int n = 0; n < regionInfo.Capacity; n++) {

            messageByte = 0;
            key = GetKey(keyStream);
            random = new Random(key);

            for (int messageBitIndex = 0; messageBitIndex < 8; ) {
                //move to the next pixel


                maxOffset = (int)Math.Floor(
                  ((decimal)(regionInfo.CountPixels - pixelOffset - 1) *
                    regionInfo.CountUsedBitsPerPixel)/
                   (decimal)((regionInfo.Capacity - n) * 8)
                );

                pixelOffset += random.Next(1, maxOffset);

                pPixel = pFirstPixel +
                         (int)regionInfo.PixelIndices[pixelOffset];

                //rotate color components

                currentColorComponent = (currentColorComponent == 2) ? 0 :
                (currentColorComponent + 1);
                //get value of Red, Green or Blue

                colorComponent = GetColorComponent(pPixel,
                                        currentColorComponent);

                for(int carrierBitIndex=0; carrierBitIndex <
                   regionInfo.CountUsedBitsPerPixel; carrierBitIndex++)
                {
                    AddBit(messageBitIndex, ref messageByte,
                            carrierBitIndex, colorComponent);
                    messageBitIndex++;
                }
            }

            //add the re-constructed byte to the message

            messageStream.WriteByte(messageByte);
        }
    }

    //clean up

    //...

    //...

}

Done! Now, let's display the message and the regions from which it has been read.

That's all we need to escape from people who try to find our hidden message by searching for unexpected variations in uniform parts of the carrier image.

By the way, there is an additional channel for secret messages: if you're sure that the recipient is creative enough to see it, you can draw outlines and letters with the region editor: