From: jim@bilbo.suite.com (Jim Miller)
Date: Fri, 4 Mar 94 12:06:36 PST
To: cypherpunks@toad.com
Subject: more steganography talk
Message-ID: <9403042001.AA02468@bilbo.suite.com>
MIME-Version: 1.0
Content-Type: text/plain



Stuff that Sergey Goldgaber, Hal, and others wrote induced the  
following ideas in my head:

Goal - create a steganography system that hides cyphertext in such a  
way that only the true recipient of the message will be able to prove  
an encrypted message is hidden within a public message.  Nobody else  
will be able to determine if the public message also contains an  
embedded encrypted message.  In Hal's words:

> A test, then, for the success of a steganographic
> technique is this: given some sampling of data items,
> half of which have embedded hidden messages, can the
> opponent guess which ones have such messages with better
> than 50% accuracy?  If not, the steganography is fully
> successful. If he can do slightly better than 50%, it may
> still be useful depending on the situation.  If he can
> guess with 100% accuracy, the steganography has failed
> and is totally worthless. 

> 


If the LSBs of most picture files were truly random, then good  
steganography would be trivial.  Anyone could just plop an  
unremarkable encrypted message (Stealth-PGP) in the LSB's, starting  
at the beginning of the file.  Since one sequence of truly random  
bits statistically looks like any other sequence of truly random  
bits, nobody would be able to prove the picture file contained a  
hidden encrypted message.

Unfortunately, I doubt that most, or even many, picture files have  
truly random LSBs.  It would be possible to write frame grabber or  
scanner software to purposely place random bits in the LSB of picture  
files to generate a source of useful picture files.  When this  
software became widely used, good steganography would become trivial.

Unfortunately, I don't have much confidence that this could be pulled  
off on a large enough scale.  If it could be done, great, but I'm not  
holding my breath.

Assuming the LSBs of most picture files are not truly random, and  
wont be any time soon, the next approach to good steganography would  
be to figure out how to transform a sequence of random bits (your  
encrypted message) into a sequence of bits that resemble the kinds of  
bit patterns you see in typical picture files.  If you could do this,  
and do it without requiring more secret keys, then good steganography  
becomes trivial again.

[Actually, you don't have to transform your random bits into a  
*sequence* of typical picture file LSB bits.  The steganography  
algorithm could deposit the bits anywhere in the picture file, as  
long the process was reversible and the result was undetectable.]


"Reversible, undetectable, without requiring additional keys."

Sounds like a good set of requirements for a steganography system.

I have an idea to help with the "reversible" part and the "no  
additional secret keys" part, and it suggests a direction for the  
"undetectable" part.

The idea:  Encrypt a widely known value with the recipient's  
public-key and use the result as an initialization vector for a  
clever transformation/steganography algorithm.  The message recipient  
recovers the encrypted message by re-calculating the initialization  
vector using the same widely known value and his public-key and  
reversing the transformation/steganography step.

The initialization vector will be different for each message  
recipient.  The "widely known value" could be a large block of bytes.    
A large file of random bits could be shipped with the steganography  
executable.  The intent is to make it more difficult and time  
consuming for the opponent to determine if a public message contains  
a hidden encrypted message.

It's not fool-proof.  The opponent could try to discover a hidden  
message by reversing the process using every known public-key.   
Worse, an opponent could narrow the search by only trying the  
public-keys of suspected recipients.  However, I think it is an  
improvement over the techniques being used today.


One significant property this technique does *not* possess is  
deniability.  A perfect steganography system will produce results  
that will let a recipient claim that they did not know a message  
contained a hidden encrypted message (e.g. most picture files had  
truly random LSBs).  If somebody sent you a hidden message using your  
public-key and the initialization vector technique, your claim of  
ignorance might not hold up.  Anybody could use your public-key to  
recover the random bit sequence.  They would not recover the contents  
of the hidden message, but they would be able to show that your file  
did contain what appears to be a hidden message.  It might be enough  
to tip the scales of justice against you.

In my mind, the perfect steganography system depends upon either an  
environment containing ubiquitous random bit sequences or a  
reversible algorithm that can transform non-random bit sequences into  
random bit sequences without using encryption (unlikely).  However, I  
believe a less-than-perfect, but still useful steganography system  
could be created using the initialization vector technique described  
above.


Jim_Miller@suite.com