Re: some technical steganography

Eric Hughes wrote:

>
> >What does "appears relatively random" really mean?  How do you  

> >measure the randomness of a sequence of bits?  

> 

> Randomness is the wrong measure.  Suppose I take 2^10
> random bits and prepend 16 zeros.  How random is this? 

> Almost as random, and this can be made precise.  How
> compressible is it?  Almost incompressible. Now, what
> about 2^20 bit?  2^30? 

> 

> It is not randomness but recognizability which is at issue.
> 


One of my assumptions was that the stuff you're trying to hide is not  
recognizable.   In one of my posts I used the phrase "unremarkable  
encrypted message".  I should have said "unrecognizable encrypted  
message".

I assert that an "unrecognizable encrypted message" will be a random  
sequence of bits.  Is my assertion correct?  Should I be using the  
phrase "high entropy" instead of "random"?

Assume for the moment that there is a way to produce an  
unrecognizable encrypted message using public-key encryption.  (I  
leave it to the experts to figure out the best way do that.)

I still believe that if the reverse stego process frequently produces  
high entropy bit sequences, even if there is no hidden message, then  
the steganography system is successful.  If the reverse stego process  
*always* produces a high entropy bit sequence, then the steganography  
system is perfect.

Of course, this assumes there is no other way to detect a hidden  
message besides reversing the stego process and testing the result.
Obviously, if the forward stego process (inserting the bits) leaves  
telltale traces, then it doesn't matter what the reverse stego  
process produces.

To summrise, I believe a successful steganography system will include  
the following steps and have the following properties:


step 1) encrypt you plaintext.

step 2) hide the encrypted message in a public message (duh)


property 1) the result of the encryption step should be a random  
sequence of bits.

property 2) the bit insertion process must not leave telltale traces.

property 3) the reverse stego process should product frequent "false  
hits".  In other words, the reverse stego process should frequently  
produce high entropy bit sequences, even if there is no hidden  
message.

Am I correct?


Jim_Miller@suite.com

>I assert that an "unrecognizable encrypted message" will be a random  
>sequence of bits.  Is my assertion correct?  

It's neither correct or incorrect because the specific notion of
randomness hasn't been specified.

Your statement is falsifiable, however, since sometimes a non-random
string of bits is what you want to get out, if what you would expect
to get out normally was also non-random.  And you want them to be
non-random in the same way.

>Should I be using the  
>phrase "high entropy" instead of "random"?

No.  This was the notion of random I pointed out that didn't work.  If
you add 16 zeros to the front of a gigabit random message, that's
pretty recogizable, even though the entropy is may be very close to
maximum.

>Of course, this assumes there is no other way to detect a hidden  
>message besides reversing the stego process and testing the result.

Don't count on it.  Statistical tests can find correlations you hadn't
suspected were there.  In fact, for some message types, _not_ finding
the correlations may indicate dithering, or maybe a steganographic
message.

>property 3) the reverse stego process should product frequent "false  
>hits".  In other words, the reverse stego process should frequently  
>produce high entropy bit sequences, even if there is no hidden  
>message.

If the prior probabilities of the message type that you're hiding in
are not random, the steganographic extraction shouldn't be either,
because then there's a distinction between an unaltered container and
an incoded one.

Eric