A new method for the steganography of 8 bit images

A new method for the steganography of 8 bit images

from: Franz Helmut Philip Kalchmair
date: 08/24/2003
mail: [EMAIL PROTECTED]

1. Introduction
Steganography is a method to hide information within an image. In most
cases uncompressed 24 bit images are used, because the color values
for each pixel are saved in the data area. There is plenty of place to
hide information. It's easy to write an algorithm. A common method to
hide the information bytes is the LSB (Least siginifikant bit) method.
There bit 0 of a byte is used to save a bit from the information
bytes. The color value of pixel is changed very slightly. The
difference between original image and result image is hardly
recognizable.
Hiding information in 8 bit images is more difficult. There we have a
color palette with 256 colors or less. A pixel is saved as one byte in
the data area. This value means an index value which points to the
palette. If we would apply the LSB method to this kind of image, we
would get images, which differ very much from the original. Mostly the
palette is not sorted and there are mostly few smooth transisions
between two color entries.

2. A common method to solve the problem: The Sort-the-Palette method
There is already a method published to treat 8 bit images. There the
palette is sorted by luminance. The suggested formula to calculate
reference values for sorting the palette is: refvalue[i] =
sqrt(0.3*red[i]^2+0.59*green[i]^2+0.11*blue[i]^2). I got better
reference values by using the coefficients (0.3, 0.57, 0.13) instead
of the suggested coefficients. After Calculating the refvalues you can
sort the palette according to the (sorted) reference values. Now the
pixel values of the data area - a pixel value points to a color entry
in the palette - must be written according to the new palette.
This "new" image is now ready for hiding the information using LSB.

The results are in some way nice. The filesize does not change.
But in most images you SEE the difference, because most sorted color
palettes have jumps between the color entries. Maybe there is white,
then there are some green values, blue and black. So many black pixels
get blue as new color. So you see, it's not satisfying.
This method only works with "smoothing" palettes.

3. The FHK-Reduce-And-Double method
- First you reduce the amount of used colors to 128. Although most gif
images use near 256 colors, you get good results. A very good Reducer
algorithm is necessary.
I found one in the Java Package JIMI (SUN). It supports color
reduction with and without dithering (Floyd-Steinberg dither). It's an
implementation of the article "A simple method for color quantization:
Octree quantization" by Michael Gervautz, Werner Purgathofer in their
book "Graphics Gems".
The freeware program Irfanview also uses a very good algorithm!.
- Then you double each value in the palette. That means you write each
value two times into the palette: Val0, Val0, Val1, Val1, Val2, Val2,
....
So you get a maximum of 256 color values.
If the original image has less than 128 used colors you do not reduce,
but only double the values.
It's not necessary to sort the palette!
- Like the method above each pixel in the data area gets a new
(index-)value according to the new palette. Each color in the palette
now has two neighboring entries. It's not important which value you
write into the data area. Using LSB you get from a value 25 the new
value 24 or vice versa.
- Now the image is ready for hiding the information. After applying
the LSB method you can't see the changes in the image!

4. resumee
The results are very satisfying. Using gif images the FHK method
brings a changed file size because of the palette. Gif saves only the
needed colors of the palette and not all possible 256 color entries
like 8 bit bitmaps. The new gif image becomes up to 30% bigger. For me
it's more important, that the changes are hardly to see. If you use 8
bit bitmaps the file size stays unchanged.

Wels, Austria, Franz Helmut Philip Kalchmair
Aug./24/2003

P.S.: First published on Aug/24/2003 20:08 in the newsgroup
de.comp.security.