Steganography 12 - Regions with different data density
4.81/5 (24 votes)
Define regions inside an image to keep smooth colours free from hidden data.
- 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:
- (
Int32) Index (not coordinates!) of the topmost pixel in the first region. - (
Int32) Length of the following region data. - For every region:
- (
Int32) Length (Region.GetRegionData().Data.Length) - (
Int32) Capacity (Count of bytes to hide in this region) - (
byte) Count of used bits per pixel - (
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:
- Get the length of the map data
- Get the index of the first pixel in the topmost region
- Use these values to extract the regions
- 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:
