Ensuring that LSBs in Stego

[bill.stewart@pobox.com ,]

Tim is incorrect here, unless he's implicitly narrowing his argument to the case
where the eavesdropper has no better model of noise than the sender,
or if he's only concerned about the eavesdropper reading the message,
not about the attacker detecting its presence.
The problem is that a good stream of cyphertext will have a 50% ones density
with no apparent correlation patterns, while the real noise may look
much different, and XORing the two gives 50% uncorrelated.

For two simple cases, consider "LSB is always 0" and "LSB has 75% of the bits = 1"; 
Tim's stegotext would be detected in both these cases.  
Real cases are more likely to resemble "noise limited to X kHz, Y dB",
though they're of course much more computational effort to test for,
and therefore less likely to be tested for.

Peter Wayner's work on Mimic Functions provides some good methods
for transforming messages into stegotext that meets arbitrary grammars,
so you can pass automated tests for stego.  That doesn't mean a
human reader won't be able to detect that something's wrong,
but if you've got human eavesdroppers trying to read every message you send or
receive, you're probably under suspicion already.

Audio is tough to use as stego cover, because it's usually compressed,
removing much of the available noise and redundancy,
either with a human speech model (cellphones, VOIP, etc.)
or with MP3s for music, so hiding messages in it is likely to have
a major impact on the sound.  Doesn't mean you can't do it,
or can't start your messages with "Hi, Bob, I'm calling from the subway" or
label your music file "Live Phish concert, 1/1/01, audience tape from nosebleed seats",
and you're better off using less aggressive compression (e.g. 32kbps ADPCM
instead of  6.5kbps cellphone algorithms.)

          Bill



On 07/21/2001 - 17:25, Tim May wrote:

> At 4:28 PM -0700 7/21/01, jamesd at echeque.com wrote:
> >     --
> >On 18 Jul 2001, at 8:07, Ray Dillinger wrote:
> >>  *sigh*.  I will not use a stego system unless I write it first and
> >>  my recipient has the only other copy.   Because it's a matter of
> >>  keeping the *method* secret, that's really the only way.
> >
> >In principle, it should be possible to write a stego program that is
> >undetectable, provided your enemy has no better models of noise
> >sources in the medium than you have.   As far as I know, no one
> >has done this.
> >
> >It is probably easier to do this with sound than with video, as order
> >and randomness in sound somewhat easier to specify.
> 
> Take a set of bits generated by a good PRNG. Use this set for the LSB 
> of GIFs or other noncompressed image files. Anyone analyzing the LSBs 
> sees a set with various spectral and statistical properties.
> 
> To send a signal, a message, XOR the message with this set of 
> PRNG-generated bits. One's recipient already has a copy of the 
> PRNG-generated bits. (Remember, stego is not the same as public key 
> crypto, so Alice and Bob can arrange in advance to use a particular 
> entry point in an PRNG, or an entry point in a one-time pad, etc.)
> 
> The resulting LSBs will have, "in almost cases," a set of spectral 
> and statistical properties nearly identical with the original LSBs. 
> Unless the message bits are somehow correlated with the 
> PRNG-generated bits, the distribution will pass all tests for 
> "randomness" that the orginal PRNG-generated bits passed.
> 
> This is a kind of variant on von Neumann's scheme for ensuring even 
> distributions of heads and tails in a message stream even with coins 
> weighted unevenly towards heads and tails.
> 
> The approach can be extended to have the distribution of LSBs look 
> like that of a camera source, or whatever normal images or sound 
> files typically have. (In this case, Alice and Bob exchange sets of 
> LSBs from camera/microphone sources. Messages are then XORed with 
> these sets. All statistical tests produce the same results as 
> original camera/microphone sources produce.)
> 
> (A "gotcha" left as an exercise if if the image or microphone source 
> produces fixed patterns of bits in certain places. For example, if 
> every image file begins with 16 fixed bits, or somesuch. In this 
> case, XORing these fixed bits with the message bits would NOT 
> preserve the statistical properties.)
> 
> --Tim May
> 
> --Tim May
> 
> 
> 
> 
> -- 
> Timothy C. May         tcmay at got.net        Corralitos, California
> Political: Co-founder Cypherpunks/crypto anarchy/Cyphernomicon
> Technical: physics/soft errors/Smalltalk/Squeak/agents/games/Go
> Personal: b.1951/UCSB/Intel '74-'86/retired/investor/motorcycles/guns
> 
> 

X-Authenticated-User: idiom
===
               Thanks;
                     Bill Stewart <bill.stewart at pob