really hiding encrypted data

Let's imaging that the government has made it illegal to encrypt data unless  
you use an "approved" crypto-system.

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.

Ideally, the munge process should not be based on obscurity.  The munge process  
should be a keyed algorithm so the government filters can't systematically  
"unmunge" to check for highly random (and suspect) data.

Unfortunately, I have a hard time imagining an algorithm that is secure AND  
produces an output that isn't highly random.
 

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.

 

 Jim_Miller@suite.com

>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.

This may be.  The connection is not obvious, but there may be
correlations because of data conversions, mechanical scanner
characteristics, etc.

The first step in any such system which more closely hides data is to
study carefully the statistics of base images.  Until you understand
them, any attempt at mimicking them is bound for failure.

Seeking a good understanding of the statistical properties of messages
of various sorts is generally missing in cypherpunks activity.  The
area gets quite technical, and we as a group need to develop some
better understanding of it.

Eric

> 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.

> From: jim@bilbo.suite.com (Jim Miller)
> 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.

I wrote something about this just a mont or two ago.  Rather than
going through it all again, let me summarize and go off in a
different direction.  Yes, simple-minded LSB steganography should be
detectible.  Its statistical effect is to stomp hard on the lowest
bit with white noise, while doing nothing to higher bits.  This
isn't a very plausible noise source.  I've been hoping to find some
time over winter break to brush up on my statistics and put together
a steganography detector.  This sort of analysis might not hold up
in court, as it's always possible that somebody has a bogus ADC or
something, but it's fine for traffic analysis.  I think the trick
will be avoiding false positives on images that have been dithered
at some point during their life...

> 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.

You could hit only scattered bits, but this sort of noise isn't
realistic either.  What you want is to end up with plausible
statistics.  One possibility is to construct a model for the
less-significant planes of the types of images (or other data) which
you intend to use.  If you leave a parameter or two free, or
partially free, you should be able to fit some data in without being
blatant about it.  Low data rate, though.  Constructing a decent
data model for this purpose is beyond me.

A simple approach: add plenty of Gaussian noise, and maybe introduce
some moire crud to make it look lousy.  Then replace every n'th LSB
with a bit of your choice.  This should be plausible enough to past
most auto-scanners, who probably can't afford to get too many false
positives.

>  Jim_Miller@suite.com

   Eli   ebrandt@jarthur.claremont.edu
	 PGP 2 key by finger or e-mail
"They have written customized software for pseudospoofing and style 
 analysis for cyberspatial warfare across the many lists."  -- L. Detweiler