The Difficulty of Secure GIF Steganography
Al Donaldson
Without further comment...
In article <331BCB...@trellis.net>, <ph...@trellis.net> wrote:
><P>Steganography is the art of making messages slip by unnoticed...
>With computers, this is done by ... using different ways of encoding
>or packing the same data.</P>
...
><P><IMG SRC="bw1.gif" HEIGHT=700 WIDTH=468></P>
>
><P>And here is the palette of this picture:</P>
>
><TABLE BORDER=7 >
><TR>
><TD>
><TABLE BORDER=1 >
><TR>
><TH>Red</TH>
>
><TH>Green</TH>
>
><TH>Blue</TH>
></TR>
>
><TR>
><TD ALIGN=RIGHT>252</TD>
>
><TD align=right>252</TD>
>
><TD align=right>252</TD>
></TR>
>
><TR>
><TD align=right>246</TD>
>
><TD align=right>246</TD>
>
><TD align=right>246</TD>
></TR>
>
><TR>
><TD align=right>232</TD>
>
><TD align=right>232</TD>
>
><TD align=right>232</TD>
></TR>
>
><TR>
><TD align=right>213</TD>
>
><TD align=right>213</TD>
>
><TD align=right>213</TD>
></TR>
Harri Haanpää
>>>>> "phma" == phma <ph...@trellis.net> writes:
phma> <P>I conclude that there is no way to hide data in a GIF or
phma> 256-color BMP file so that the presence of the hidden data
phma> cannot be detected.
As I understand it, a GIF palette consists of at most 256 rgb color
entries. They can be in any order. There are 256! ways to order the
256 colors of the palette, so there can be 256! different messages
encoded in the ordering of the colors. I think that's about 1685
bits of information. To create an encoded message, one would do
something like this:
1. Take a 256 color GIF image. (the colors must be distinct)
2. Sort the colors in a predefined way (for example ascending according
to 65536*r + 256*g + b)
3. Calculate the permutation corresponding to the message
4. Permute the palette accordingly.
To decode, one would
5. Sort the colors
6. Determine the permutation used
7. Calculate the message
An obvious limitation of this scheme is that it only allows sending
a constant number of bits per GIF irrespective of the size of the
picture used.
On the other hand, a GIF having a jumbled palette is not too unusual,
at least if the GIF isn't a grayscale image. I think it should be
pretty hard to prove the existence of a message.
Sorry if this is nothing new, I just thought of it.
Harri Haanpää
Xcott Craver
First:
You just posted over 2250 lines of HTML code to several USENET groups.
USENET is not the World-wide web, and most people's readers are not capable of
translating all the HTML tags. As such, posting the source code of a homepage
(at least without warning) is often considered about the same level of
netiquette as posting a huge UUENCODED binary.
One of the advantages of the Web is that you could just post the
URL, so people can come and look at it as they like. Please do this in the
future. [And slightly off the subject, your HTML writing style is actually
quite neat and organized. Good for you.]
Having said that, I must comment:
In article <331BCB...@trellis.net>, <ph...@trellis.net> wrote:
>
><P>I conclude that there is no way to hide data in a GIF or 256-color BMP
>file so that the presence of the hidden data cannot be detected. I therefore
>believe that we should concentrate our steganographic efforts on other
>file formats, such as JPEG. Although data cannot be hidden in a JPEG file
>by altering the pixels because it uses lossy compression, data can be hidden
>by altering the output of the 2-dimensional Fourier transform used in the
>compression. A program to do this, available on several platforms as is
>PGP, would be a valuable contribution to steganography.</P>
Okay, think about what you just said. Suppose you could alter
the elements of the discrete-cosine transform blocks used in JPEG compression
so that you could hide a string inside them. If your scheme is robust enough,
then it *IS* a method for hiding data in GIFs as well, since you could just
convert to GIF and unconvert later. A number of schemes exist for hiding
watermarks in images using Fourier-based methods, and are incredibly robust
to some forms of image processing. One scheme, proposed by Ingemar Cox et al,
imbedded a watermark that survived printing the image out, Xeroxing it,
and scanning the Xerox copy!! I would be very surprised if you could
discover the hidden watermark once it was converted to a GIF.
Of course, I'm thinking in terms of watermarks rather than secret
messages, the former being very different from the latter. The Cox et al
watermark is a vector of floating-point numbers pseudo-randomly selected
from a normal distribution. Hiding a bit string with actual semantic content
is a different matter entirely!
Also, bear in mind that the degree to which data can be hidden in an
image depends on the amount of noise already present in it. If you have
very sharp artificial pictures you may not be able to imbed a bit string.
If you had a scanned photograph it will be much easier.
At the Photonics West conference in San Jose last month, a fella
from T.U. Delft proposed a watermark scheme whereby the lower-right triangles
of JPEG blocks were completely zeroed out to encode a zero bit, and left
alone to encode a one. The triangle was chosen to be large enough to be
noticable by a detector, but small enough not to distort the image *too*
much when cleared. In order to combat the small amount of distortion the
scheme *did* create, the fella subjected the blocks to pseudo-random shuffling
before inserting the bitstring. Of course, this means that you could utterly
obliterate the watermark simply by shifting the image 8 pixels to the left....
,oooooooo8 o oo...@math.niu.edu -- http://www.math.niu.edu/~caj/
o888' `88 ,888. 888
888 ,8'`88. 888 "This year's Summer fasions are simple yet
888o. ,oo ,8oooo88. 888 vibrant, as I will prove using the following
`888oooo88 o88o o888o 888 lemma." -Cindy Crawford, _Gauss_of_Style_
____________________8o888'_________________________________________________
W. D. Milner
ph...@trellis.net wrote:
><BASE HREF="http://web.trellis.net/users/phma/stegif.htm">
<MAJOR SNIP>
Now maybe I'm being unduly critical but isn't this on a web page?
Isn't HTML designed for that? Can't we jsut ahve the URL so we can go
read it there.
Frankly, I and most of the people I know *don't* read newsgroups with
HTML compliant readers. It just wastes bandwidth, especially when the
document is already posted on the web to read.
Just my 2 bits worth. In plaintext of course :)
---
W.Dean Milner
SHL Systemhouse Inc., IDPU
Sydney, NS, Canada
wdmi...@atcon.com
DISCLAIMER: Any opinions expressed are solely those of
the author and do not necessarily reflect those of SHL
Systemhouse Inc.
Mark Kaehny
ph...@trellis.net wrote:
Please put pictures in some public place and just put the pointers to
them in your post.
>
> I conclude that there is no way to hide data in a GIF or 256-color BMP
> file so that the presence of the hidden data cannot be detected. I
> therefore believe that we should concentrate our steganographic
> efforts on other file formats, such as JPEG. Although data cannot be
> hidden in a JPEG file by altering the pixels because it uses lossy
You attack one crude method and then make this conclusion. It is quite
easy to hide bits in a gif. You just don't hide as many. You use
something like whether some values are quadratic residues in some field,
or divisible by some other value in some field. You ALWAYS adjust
the values in EVERY GIF you send - with random values or with
encrypted values. You use some criteria in picking the values -
I'll leave that to you :)
MRK
Hal
In article <331EDB...@execpc.com> Mark Kaehny <kae...@execpc.com> writes:
> [...]
> It is quite
> easy to hide bits in a gif. You just don't hide as many. You use
> something like whether some values are quadratic residues in some field,
> or divisible by some other value in some field. You ALWAYS adjust
> the values in EVERY GIF you send - with random values or with
> encrypted values. You use some criteria in picking the values -
> I'll leave that to you :)
So, would you put this information in the color table, or in the pixel
portion? People usually prefer the latter since that is normally much
the larger.
The problem is that with only 256 colors, the different colors tend to be
pretty different. So changing a pixel to even a nearby color will produce
a very noticeable change in that part of the picture. If you do this to
a significant fraction of the pixels, the picture ends up being noticeably
degraded. Now, if the only pictures you ever publish have been degraded
by random noise as you suggest, then it won't be possible to distinguish
which ones have data and which have noise. But in a world in which high
quality pictures are preferred over low, the intentionally degraded ones
may stand out.
The alternative strategy challenged by the original poster was to try
to group the colors into a smaller set of closely matched pairs (or
octets in this case). Then any pixel can be changed to another in
that group while having virtually no visible change to the picture.
However, pictures which have had this done are of course very obvious
when you look at the raw data, which was the point of the original
posting.
Hal Finney
Mike Gahan
Hal wrote:
>
--- snip ---
>
> The alternative strategy challenged by the original poster was to try
> to group the colors into a smaller set of closely matched pairs (or
> octets in this case). Then any pixel can be changed to another in
> that group while having virtually no visible change to the picture.
> However, pictures which have had this done are of course very obvious
> when you look at the raw data, which was the point of the original
> posting.
>
Why bother with creating groups? Just have multiple colour table entries
the same RGB. The image will then be visually indistinguishable from the
original. Of course, looking at the raw data will give the game away as
before, but at least there will be no visual clue.
I have written some code which encodes gifs in this way. See
http://www.ucl.ac.uk/~ccaamrg/gifhide
for more (sketchy) details. The code has been run on AIX 3.2.5.
It needs the gd library, details at
--
Mike Gahan
Information Systems Division
University College London
http://www.ucl.ac.uk/~ccaamrg/