Ensuring that LSBs in Stego "look random enough"

[Tim May]

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