Cryptography Reference
In-Depth Information
steganography.The lack of color, though, could be a bit of a indica-
tion that something had changed.
The second program,
reduce.exe
, shrank the color table from
256 colors to 128 colors and then duplicates these 128 colors so that
adjacent entries in the color table were exactly the same. If this is
done, hiding information in the least significant bit won't affect the
look of the image.
There are a number of different programs for reducing the size of
the palette. The simplest is:
1. Create a two-dimensional matrix containing the distances be-
tween all pairs of colors in the palette. The distance between
two colors,
(
R
1
,G
1
,B
1
)
and
(
R
2
,G
2
,B
2
)
is
R
2
,G
2
,B
2
)) =
(
R
1
− R
2
)
2
+(
G
1
− G
2
)
2
+(
B
1
− B
2
)
2
δ
((
R
1
,G
1
,B
1
)
,
(
.
2. Find the best color to delete. That is, find the color with the
closest neighbor and remove it.
3. Repeat until the palette is the desired size.
Unfortunately, this technique leaves a large red flag for anyone
scanning GIFs looking for hidden information. While the eye may
Chapter 17 describes a
several techniques for
detecting a
steganographic
message.
not see any change after flipping the least significant bits, an 8-bit
color table with only 128 different colors is easier to detect automat-
ically than a bad image with plenty of artifacts.
Another early program, EzStego's, solution for dealing with GIF
palettes was a bit more wily. The software written by Romana
Machado sorts the palettes so that the
2
n
colors in an
-bit file flow
smoothly from one to another. That is, each jump from the
n
i
-th color
to the
+1
is relatively small. Any hidden information that changes
the least significant bit will introduce small changes. Ordering the
colors in the palette is trivial with one-dimensional color spaces in
black and white images, but it is much more difficult in three dimen-
sions.
EzStego treats the challenge as a version of the Travelling Sales-
man Problem. The colors are cities in three dimensions (RGB) and
the goal is to find the shortest path through all of stops.
There are no easy answers for Travelling Salesman problems so
EzStego uses a basic approximation that works pretty well.
i
It may
Other approximations
for the travellings
salesman problem can
be found in
[Tah92, Cla83].
not find the optimal solution, but it will often find one that works
very well. Here's the algorithm:
Begin with two colors in the list,
{c
0
,c
1
}
. Set the first one to be
C
.
Repeat this until all colors are inserted.
