Re: A new method for the steganography of 8 bit images

From: Arthur J. O'Dwyer (ajo_at_andrew.cmu.edu)
Date: 08/26/03 

Date: Mon, 25 Aug 2003 18:29:55 -0400 (EDT)

On Mon, 25 Aug 2003, snoopy wrote:
>
> A new method for the steganography of 8 bit images
>
> from: Franz Helmut Philip Kalchmair
> date: 08/24/2003
> mail: snoopy@oeh.uni-linz.ac.at
>
> 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!

A few points, and a suggestion for the interested parties:

First, this algorithm doesn't do very well at hiding the information.
It's painfully obvious upon examination of the image data that something
is awry, and it's not a far jump from "every color has two entries
differing by one bit" to "there is data hidden in the LSB of each pixel."

Second, you really don't need to make the paired entries exactly
identical. A very interesting algorithm might modify the pixel values
first, and then use the LSB pattern as a "dither template" to somehow
compute the optimal color values for each palette entry. It's hard
to explain, so it's probably hard to implement; but if you know what
I mean, you could try to rigorize it.

Finally, another algorithm: Simply color-reduce the '0'-LSB section of
the image separately from the '1'-LSB section. You'll end up with
two slightly different palettes. Now dither the whole image (with an
error-diffusion algorithm, I'd imagine), using colors from Palette 0 for
the '0'-LSB pixels and colors from Palette 1 for the '1'-LSB pixels. When
you're done, store the palette entries and pixel values as before.

It might be possible to shuffle or sort the entries somehow so as to
make the weird palette less conspicuous, yet still allow reconstruction
of the hidden message. I can't think of anything off the top of my
head, though.

If you (the OP) express interest, I can send you an implementation of
this algorithm. Otherwise, I probably won't bother coding it.
Anyone else is welcome to use or modify it in whatever way they like.

HTH,
-Arthur