description.html
b2d61d3217d9135359c018bc3e952ac39c497c02d0887647ff076b59244860c6<HTML>
<HEAD> <TITLE>How gifshuffle works</TITLE> </HEAD>
<BODY BGCOLOR="#8c8c8c" LINK="#c84848" VLINK="#903030">
<CENTER><H1> How gifshuffle works </H1></CENTER>
<P>
This document gives a description of the encoding scheme used
by <B>gifshuffle</B>. </P>
<H3> The Nature of Steganography </H3>
<P>
Steganography is the science of concealing messages in other messages.
Some historical techniques have involved invisible ink, subtle indentations
in paper, and even tattooing messages under the hair of messengers.
In this digital age, steganography provides means for hiding messages in
digital audio files, in some kinds of images, and even for generating
pseudo-English text which encodes the message. </P>
<P>
Ideally, the original message is not noticeably degraded by the presence
of a hidden message. As a result, the most effective techniques tend to
make use of data that contains a lot of redundancy, such as raw audio
and image files. Steganography works much less effectively, if at all,
with efficient compressed formats such as JPEG and MPEG. </P>
<P>
Unfortunately, sending large amounts of raw audio and image data can
arouse suspicion, and the pseudo-English encoding schemes are not
sophisticated enough to fool a human observer. </P>
<H3> GIF Colourmap Steganography </H3>
<P>
The encoding scheme used by <B>gifshuffle</B> relies on the fact that
the ordering of the colours in the colourmap of a GIF does not affect
the way an image is displayed. Two images with a different colourmap
ordering are visibly identical. </P>
<P>
The <B>gifshuffle</B> program runs in two modes - message concealment, and
message extraction. During concealment, the following steps are taken. </P>
<DL>
<DD> Message -> optional compression -> optional encryption
-> concealment in image
</DL>
<P>
Extraction reverses the process. </P>
<DL>
<DD> Extract data from image -> optional decryption ->
optional uncompression -> message
</DL>
<P>
Each of the steps are described in detail below. </P>
<H3> Compression </H3>
<P>
The compression scheme used by <B>gifshuffle</B> is a fairly rudimentary
Huffman encoding scheme, where the tables are optimised for English
text. This was chosen because the colourmap encoding scheme provides
very limited storage space in some situations, and a compression
algorithm with low overhead was needed. In other words, short messages
had to compress to even shorter data. Depending on the text, you
can usually get 25 - 40% compression. </P>
<P>
If you want to compress a long message, or one not containing standard
text, you would be better off compressing the message externally with
a specialized compression program, and bypassing <B>gifshuffle</B>'s optional
compression step. This usually results in a better compression ratio. </P>
<H3> Encryption </H3>
<P>
The encryption algorithm built in to <B>gifshuffle</B> is
<A HREF="../ice/index.html">ICE</A>, a 64-bit block cipher also
designed by the author of <B>gifshuffle</B>. It runs in 1-bit cipher-feedback
(CFB) mode, which although inefficient (requiring a full 64-bit encryption
for each bit of output), provides the best possible security when
different messages are encrypted with the same password. Although
using the same password many times is theoretically a big no-no, in
the real world it often can't be avoided. </P>
<P>
The lower 7 bits of each character in the password are packed into an array,
which is used to set the encryption key. The ICE encryption algorithm
can operate at different levels, with higher levels using longer keys
and providing more security. The ICE level appropriate for the password
length is used. </P>
<P>
CFB mode makes use of an initialization vector (IV), which is initially
set to the first 64 bits of the key encrypted by itself. Each time a
bit is encrypted, the IV is encrypted, and the leftmost bit of the
encrypted IV is XORed with the bit. The IV is then shifted left one bit,
and the ciphertext bit is added to the right. Decryption reverses this
process. </P>
<H3> The Encoding Scheme </H3>
<P>
Consider a pack of 52 cards. There are 52 factorial ways to sort the pack,
which means that any particular ordering of the cards can represent a
number in the range [0, 52!-1]. In other words, given <I>n</I> cards,
you can store approximately log<SUB>2</SUB>(<I>n</I>!) bits of information
based on their ordering. </P>
<P>
GIF images contain a colourmap with up to 256 entries, resulting in a
maximum storage capacity of 1675 bits. The image itself consists of a
compressed array of indices into this colourmap. To conceal a message
within a GIF image the following steps take place. </P>
<OL>
<LI> Start with the message you want to conceal, specified on the
command line or in a file. Optionally compress and/or encrypt
this message. You are then left with a sequence of <B>1</B>'s
and <B>0</B>'s.
<LI> Prepend a <B>1</B> to this sequence, giving you a binary number
<I>m</I> (probably quite large).
<LI> Next take a look at the GIF image that you want to conceal the
message in. Count the number of unique colours in the image, and
call the value <I>n</I>. If <I>m</I> > <I>n</I>!-1 then the message
is too large, and the procedure will be aborted.
<LI> The colours in the colourmap are first sorted into their "natural"
order. Each RGB colour is assigned the value (<I>red</I> * 65536 +
<I>green</I> * 256 + <I>blue</I>), and the colours are sorted
according to these values. Any duplicate colours are stored at the
top of the colourmap, and are not used for storing the hidden message.
<LI> Iterate <I>i</I> through the values 1 .. <I>n</I>. Each colour
<I>n</I>-<I>i</I> is allocated a target position (<I>m</I> mod
<I>i</I>), then <I>m</I> is divided by <I>i</I>.
<LI> Each colour (<I>n</I>-1) .. 0 is then in turn inserted into a new
colourmap at its target position. Colours previously occupying the
target position and above are moved up one place.
<LI> The image component of the GIF is then uncompressed, the colour
indices are re-mapped to the new colourmap, and the image is
re-compressed. For animated GIFs this is repeated for each image.
</OL>
<P>
Extracting a hidden message follows a similar procedure, but in reverse.
The ordering of the colourmap is used to construct a binary number,
which is then optionally decrypted and uncompressed before being output. </P>
<HR>
<DIV ALIGN=RIGHT>
<FONT SIZE=-1>
Document last modified by Matthew Kwan, 10 May 1998 <BR>
Please send any comments or corrections to
<A HREF="mailto:mkwan@darkside.com.au">mkwan@darkside.com.au</A>
</FONT>
</DIV>
</BODY>
</HTML>
© 2022 Packet Storm. All rights reserved.
%7Cutmcsr%3D(direct)%7Cutmcmd%3D(none)){kind=small}
Follow us on Twitter
Follow us on Facebook
Subscribe to an RSS Feed