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@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@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@pob