From: Matthew J Ghio <mg5n+@andrew.cmu.edu>
Date: Mon, 29 Nov 93 20:37:17 PST
To: cypherpunks@toad.com
Subject: Re: really hiding encrypted data
In-Reply-To: <9311300120.AA12755@bilbo.suite.com>
Message-ID: <ggygqbG00awUMEM0Y2@andrew.cmu.edu>
MIME-Version: 1.0
Content-Type: text/plain


> In a world like this, a person who wanted to encrypt data would have
> to find a way to hide the encrypted data.  Many people have suggested
> placing the encrypted data in the least significant bit of a binary picture
> file.  However, I suspect it is easy to distinguish between the collection
> of least significant bits of a normal picture file and the collection of
> least significant bits of a picture file used to hold some encrypted data.
> In other words,  your picture file envelope could trigger an alarm in
> some government traffic sniffer.
>
> This is probably a stupid question, but...is there anyway to take a
> chuck of encrypted data (presumably with a high degree of randomness)
> and securely munge it so it looks less random, while retaining the
> ability to reverse the munge and decrypt the data.

Not a stupid question at all.  I would suspect that altho the least
significant bits of a picture file are not very orderly, they are
probably not quite a random distribution.  I would suspect that in many
pictures, they would form curved contour lines, outlining subtle
differences in color across a picture image.  Of course, some pictures
are more random than others, so the best someone scanning data packets
could do would be to pick out "suspicious" images to analyze further.

> Any ideas?   How about something fractal?  <arg!  I can't believe I said
> the "f" word>   The "munge key" could be the initial state of the
> fractal engine.   <shrug>  I really don't have a clue about the randomness
> of the output of a fractal engine.

Well, since you mentioned the f-word, I guess I'll entertain the
possibility.  A fractal would probably be one way to hide data while
producing an orderly looking picture.  Suppose you wrote a program to
calculate the Mandelbrot set (fairly common example that most people
should be familiar with; if not, ask and I will clarify the math) to 256
iterations, and plot the number of iterations required for the magnitude
of the complex number pair to exceed 2.0 as the intensity of the pixel
(or zero for points in the set).  The result is a image that many people
have seen before.  Now, suppose that you modify your fractal generator
program slightly.  For points which required more than 32 iterations,
you would not plot the exact value, but instead change it +/- 1. 
Because the points which require a high number of iterations are in the
naturally most chaotic part of the fractal, it would probably defeat
"scanning" attempts to look for steg-data.  In fact, the only way to
discover the message would be to actually plot the fractal and compare
it to the file you had - a time consuming process, especially if the
cracker didn't know the exact coordinate boundries of the image, and the
number of significant figures used in your calculations.  Or maybe
instead of accepting divergance at 2.0, you choose 2.1, or even 2.01? 
Lots of possibilities...

If defeating a gummint traffic sniffer is your objective, consider what
kind of sniffer the gummint might use.  If they were just checking for
randomness, they might apply a data compression technique to look for
patterns (since cryptodata can't be compressed).  In such a case, you
could design a compression program which would "uncompress" data - that
is, run a data compression in reverse; adding random repitition that a
data compression program would notice.  Basically, what you need to do
is to design a data (un)compression system such that every possible
input file maps exactly to some "uncompressed" text.  You then steg the
uncompressed data, and then the recipient "compresses" the data to
reveal the original ciphertext, and then decrypts.