From: nobody@jarthur.cs.hmc.edu
Date: Sat, 23 Apr 94 13:40:05 PDT
To: cypherpunks@toad.com
Subject: Fractal steganography
Message-ID: <9404232039.AA10884@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


Hi, sorry if this appears twice, but I sent it a few days ago and it
never turned up. Recent mention of using fractals for steganography of
PGP-encrypted messages reminded me that I'd never seen this announcement
posted to cypherpunks...

>>>BEGIN INCLUDED MESSAGE
>Newsgroups: sci.crypt,alt.security.pgp
>From: qwerty@netcom.com (-=Xenon=-)
>Subject: New Steganograph Available
>Date: Sun, 13 Mar 1994 04:50:27 GMT

-----BEGIN PGP SIGNED MESSAGE-----

Henry Hastur's latest.

This thing generates fractals, hiding a PGP or Stealth PGP message
in them as well.

I have put it up for ftp at ftp.netcom.com in /pub/qwerty, as
MandelSteg1.0.tar.Z. Also there, is a "Steganography.software.list",
and other steganographic software.

 -=Xenon=-

P.S. I will forward mail to "Henry" if you would like to contact him.

-----BEGIN PGP SIGNATURE-----
Version: 2.3

iQCVAgUBLYJUWgSzG6zrQn1RAQEL0AQAutxwMCxCS09qdZFGxuO9+9kqUkigm2Jk
0ng+uZkAPuh9J8TNOg+xSaqoil2+AOYyQmUB1w/5HablUL22BffvX9omfkkAWFYR
gPRBIC1Dr56SP/PmZnLTQxjjUm5HfHupZHJCGs268uffizufi6Rzahp9y0iJ0YGf
JH/cGCpQqEQ=
=pA25
-----END PGP SIGNATURE-----


		MandelSteg V1.0 and GIFExtract V1.0
		-----------------------------------

These two programs allow you to hide confidential data in fractal GIF images,
giving an increased level of security compared to sending PGP-encrypted
email over the Internet. MandelSteg will create a Mandelbrot image (though
it could easily be modified to produce other fractals), storing your data
in the specified bit of the image pixels, after which GIFExtract can be
used by the recipient to extract that bit-plane of the image.

MandelSteg is not intended to replace the standardised methods of using
encryption (e.g. ASCII-armoured PGP email) ; in an ideal world we would
all be able to send openly encrypted mail or files to each other with no 
fear of reprisals, however there are often cases when this is not possible,
either because the local government does not approve of encrypted 
communication, or perhaps because you are working for a company that
does not allow encrypted email but doesn't care about Mandelbrot
GIFs. This is where steganography can come into play.

You will probably find that you also need to get hold of a copy of
an interactive Mandelbrot viewer in order to determine suitable
coordinates to use for images. There are numerous such viewers available
on the Internet and BBS systems (e.g. xmandel).


MandelSteg - 'Mandelbrot Steganography'
---------------------------------------

MandelSteg has numerous modes of operation, depending on the level of
security you desire. With no command line options specified it will
simply generate a 640x480 GIF of the default section of the set, and
send it to stdout. With the -c option it will calculate how many bytes
can be stored in the image and with -e will take the data fed to stdin
and hide it in the image (specify a file name after the -e to write it
to a file), and pad out the data with random bytes if neccesary if
-r was specified. 

For the lowest security level, the data will simply be stored in the specified
bit of each pixel, and a 128-color palette created such that the pixel looks
the same regardless of whether there is data stored in it or not. This will
be sufficient to survive a cursory examination, but will be obvious to anyone
versed in the arts of steganography - in particular replacing the supplied
palette for the image with another will show up the data bits hidden in areas
of solid color.

To avoid this problem, you should specify the -ns flag, which will only store
data in areas of non-solid color (note that this can greatly decrease the
amount of data that you can store in the image). Another indication of a
steg-ed image is the duplicated 128-color palette, which can be replaced
with a 256-color palette with the -fp flag. Obviously if you specify -fp
and don't specify -ns, you will produce a readily apparent steg-ed image.

If you don't have enough space for your data in the image, you can simply
increase the size of the image by using the -sz flag, followed by the width
and height in pixels. Alternatively, you can select a different area of the
mandelbrot set by using -md followed by the start x, start y, width and
height, specified with floating-point values.

Finally, you can specify the bit to store the data in using -b followed
by the bit number, otherwise the program defaults to bit seven. Bit seven 
gives the best performance, but bit zero should give the most security. You
can also specify that a number of bytes in the image should be missed out 
before the encrypted data with the -bp option, followed by the number of 
bytes to miss out. If the -r option is specified, then random data will be
placed in these bytes, and also appended to the input data to completely
fill the specified bitplane.


Compilation:
------------

On a BSD unix system you should be able to simply extract the source and
run make to generate the executables. On a System V version of Unix you
will need to edit the makefile to use one of the 'CFLAGS = ... -DSYSV ...'
lines instead of the default. If you have plenty of memory, you can undefine 
LOW_MEM, which will improve performance slightly.

On an MS-DOS machine with the Microsoft C compiler, simply execute
COMP.BAT. This batch file will compile and link the source to build
the executables. Sorry, but I was too lazy to create a proper DOS
makefile !


Examples of use:
----------------

[ Note : Due to file system limits, on MS-DOS the executable names are
  mandsteg and gifextr rather than mandelsteg and gifextract. Also note
  that unless you have an 80x87 coprocessor or are running on a 486DX+
  processor, mandsteg will run VERY slowly due to the number of floating
  point operations required ! ]

Store file in 640x480 mandel.gif :

mandelsteg -e mandel.gif < file.dat

Store file in 400x400 mandel.gif, using non-standard co-ordinates :

mandelsteg -sz 400 400 -md -0.5505 -0.5505 0.0001 0.0001 -e mandel.gif 
	< file.dat

Encrypt file with PGP, strip headers with stealth, and store in bit 0 of 
mandel.gif with non-standard coordinates, using 256-color palette and not 
storing in solid colors, with 23 byte random prefix :

pgp -ef < secrets.dat | stealth | mandelsteg -sz 400 400 -md -1.0 -1.0 2.0 
	2.0 -b 0 -ns -fp -bp 23 -r -e mandel.gif

Test non-standard coordinates for available space :

mandelsteg -ns -sz 400 400 -md -0.5505 -0.5505 0.0001 0.0001 -c > /dev/null

Generate image containing random data to annoy cryptanalysts :

mandelsteg -fp -r -ns -e annoying.gif < /dev/null


Error messages:
---------------

The only likely error messages will indicate either invalid commands, or
that the input data has been truncated (i.e. not all the data that was
piped into the program could be stored in the GIF file). In the latter
case, you should create a larger file to store the data.


Security:
---------

Well, frankly, it's not that secure, even with -ns -fp -b ? -bp ? specified 
on the command line. There are several main reasons :

1. In essence, mandelsteg can be regarded as a one-time pad cipher using the
   mandelbrot image as the pad. As a result, the 'key' to this cipher would
   be the coordinates and size of the area you've generated, as with that
   data the cryptanalyst would be able to generate the 'real' image and compare
   it to the steg-ed image to find the data. Two important things to realise
   here as a result are that a) you should *never* use the default coordinates
   for secret data, and b) you should never use the same coordinates twice.

2. Obviously, any cryptanalyst out there can just run 'gifextract' on the 
   image, and your data will come out ! It may take sixteen or more attempts 
   using the different bit values, -bp values and -ns options, but it will 
   extract a valid copy of the data. And if the data has a PGP header or 
   something, well, they've got you. This can be hindered by either using 
   'Stealth' to produce headerless data, or by generating large numbers
   of images containing random data to provide a cover for the real data.

3. Typically, a mandelbrot image consists of about 55 % of one bits and
   45 % of zero bits. If you have replaced this with a PGP-encrypted
   messge, these frequencies will be more like 50% each. If you use
   an image much larger than neccesary, and a large -bp value, this will be 
   somewhat disguised.

4. The standard random() function is used to generate random padding, and
   the distribution of bits in the output wil therefore probably be
   different to that expected for encrypted data. If you are attempting
   to get data past a serious adversary, you should replace this with 
   a cryptographically strong random number generator such as the
   idea_rand() function used in PGP.

In most cases, none of these should be a real problem, as MandelSteg
is not intended to provide foolproof security against cryptanalysis, but
primarily to prevent cryptanalysis by disguising the fact that you are
sending encrypted messages at all.

In addition, YOU SHOULD ALWAYS VIEW THE IMAGE BEFORE SENDING IN CASE YOUR
CHOICE OF PARAMETERS HAS PRODUCED UNEXPECTED ARTIFACTS IN THE OUTPUT
IMAGE !!!!!!!! Excuse the shouting, but ths is important... 8-). I
haven't seen any strange results yet produced by the algorithm, but you 
only need to accidentally miss out a command line parameter once and your 
use of steganography will be obvious to anyone examining the image.

 
GIFExtract
----------

GIFExtract is a very simple program, which simply extracts the specified
bitplane from an image and sends the data to stdout. The program defaults
to extracting bit 7 of each pixel, but the bit can be specified with the
-b command line option, with -ns it will only extract data from non-solid 
areas, -bp can be used to ignore the first specified number of bytes 
extracted, and -a to analyse the distribution of zero and one bits in the
image.


Examples of use
---------------

Extract bit-plane 4 from foo.gif into secrets.pgp :

gifextract -b 4 foo.gif > secrets.pgp

or

gifextract -b 4 < foo.gif > secrets.pgp

Analyse bit plane 1 of foo.gif for one bit and zero bit frequencies prior
to using it for steganography :

gifextract -a -b 1 foo.gif

Extract the secrets.dat file that was used in the mandelsteg example above,
if your PGP key id is 23ffff :

gifextract -b 0 -bp 23 -ns mandel.gif | stealth -a 0x23ffff | 
	pgp -f > secrets.dat


Error messages
--------------

The only likely error messages will be due to either failure to allocate
the required memory for GIF decompression, or failure to open the input
file.


DISTRIBUTION NOTES
------------------

Either of these programs can be freely distributed, however you must
take into account any prevailing cryptography import and export 
regulations in international transfers. This program was written
outside the US, and as such copies should be available from European
ftp sites as well.


						Henry Hastur
>>>END INCLUDED MESSAGE