Cryptography Reference
In-Depth Information
7. The receiver can now extract the bits by using the sorted palette
values assigned to the colors. The least significant bits now
encode the message.
This solution removes the problemwith a highly structured palettes
because it uses one produced by the image's creating software. Any
attacker will have trouble determining the existence of the message
by looking at the structure of the palette.
Andreas Westfeld and
Andreas Pfitzmann
created the pallettes in
Figure 9.8 for their
paper [WP99] with only
61 short lines of
Postscript!
9.3.2 Smarter Color Reduction
There are two different types of image steganography supported by
S-Tools a package written by Andy Brown. The software, now up
to version 4.0, can hide information in images stored as either GIFs
or BMP files orin sound stored as WAV files. Earlier versions even
offered to store data in the unallocated sectors of a disk.
Wilson MacGyver Liaw
wrote a good
introduction to the GIF
file format in [Lia95].
While the software can hide information in the least significant
bits of 24-bit BMP files, the software can also reduce the image to
256 colors with an algorithm designed by Paul Heckbert [Hec82] to
reduce the number of colors in an image in the most visually nondis-
ruptive way possible. The algorithm plots all of the colors in three di-
mensions and then searches for a collection of
boxes that contains
all of the colors in one of the boxes. When it is finished, it chooses
one color to represent all of the colors in each box. S-Tools offers
three different options for how to choose this one color: the center
of the box, the average box color, or the average of all of the pixels in
the box.
The process for constructing the set of boxes is described in detail
in Heckbert's thesis. The process begins with the complete
256
n
×
256
256
space as one box. Then it begins to recursively subdivide
the boxes by splitting them in the best way possible.
×
It continues
this splitting process until there are
boxes representing the space.
Heckbert developed this algorithm to correct some of the defects he
found in the “popularity” algorithms being used. These algorithms
would clump together nearby colors until only
n
clumps were left.
Then it would choose some color, usually the center of the clump,
to represent all of the colors. This works quite well for colors in
tight clumps, but it can be disastrous for colors that are part of big,
gaseous clumps. In those cases, the difference between the colors
and their chosen representative was too large. This would lead to big
shifts in the colors used in the details.
Heckbert suggests that a good way to understand the two ap-
n
David Charlap wrote a
good introduction to the
BMP format in
[Cha95a, Cha95b].
proaches is by comparing them to the “quantization” methods used
in choosing the representatives for the two houses of the Congress of
