From: tcmay@got.net (Timothy C. May)
Date: Sun, 10 Mar 1996 14:01:39 +0800
To: cypherpunks@toad.com
Subject: Chaff in the Channel (Stealth PGP work)
Message-ID: <ad5b906f080210042e09@[205.199.118.202]>
MIME-Version: 1.0
Content-Type: text/plain


At 9:32 PM 2/29/96, Bruce Zambini wrote:

>Well, that's what I want to avoid; I think the issue is that as long as
>stego is predictable, there's a problem, ie a message to a certain party
>can be shown to exist, even if it's not readable. This might prove more
>than ample evidence in certain circumstances.
>
>You shouldn't be able to recover the stego'd message without special
>knowledge.  This isn't addressed by current software, to my knowledge.

Sorry if I haven't been following the latest "stego" messages too closely.

If it is desired that an image, say, carry a steganographic message that is
"undetectable" to adversaries, then much more than just stripping off the
PGP markers (headers, identifying bits, whatever) must be done: the LSB bit
plane, if this is the stego channel, must have statistics which are
indistinguishable from "normal" LSB bit planes of images. (Not an easy
thing to define or to implement, but there you go.)

So, when the Khmer Rouge People's Enforcement Division looks at the image
they have confiscated from your computer and examines the LSB bit plane for
evidence of human rights files encrypted steganographically, that bit plane
had better not have unusual statistics...it had better not look "too"
random, as real life LSB randomness may not have nearly the entropy of PGP
randomness, say.

What can be done?

One emergent standard could be to the following:

- when images are sent, or stored, replace the true LSB bit plane (I say
"true" to distinguish the actual "grey levels" of one or more of the color
bit planes from RGB encodings in which the nominal LSB is not at all the
minimum brightness changes) with a "PGP chaff image."

- this PGP chaff image could be randomly generated, or chosen from a
library, or (surprise, surprise) actually be an encoded message.

- the point is that some percentage of all images would have this chaff
present, so that mere possession of an image with the offending statistics
would not ipso facto be proof of possession of an encrypted/stegoized
message.

(Of course, the Khmer Rouge People's Enforcement Division might simply kill
you anyway, but then they might kill you for merely having a computer. One
would hope that Reno's Raiders would not do likewise, and that the
existence of multiple images with "chaff" image planes would be sufficient
to confuse things.)

- the adversary may know you have an image with a chaff plane, but he
doesn't know that you actually know how to decode that chaff, that that
chaff is not chaff to you.

[How is this any different from simply sending chaff messages
conventionally, without using steganography? Why not use the full
bandwidth? Answer: Stego provides some plausible deniability, more
important in court cases in the U.S. than to the Khmer Rouge, of course.
Having random messages filling up one's hard disk is suspicious, but having
images of the Mona Lisa which _may_ contain stego bits and which _may_ be
readable by the owner is considerably less suspicion-arousing.]

This is my take on fixing the stego situation. Instead of worrying about a
"stealth PGP version," which is likely to be only a slight speed bump
(because of the statistics), think about flooding the detection channels.

Longterm, however, I certainly think that cryptographic messages can be
made virtually indistinguishable from low-order bit noise. (I have argued
this since the late 1980s, so I'm not changing my views now.)

--Tim May

Boycott "Big Brother Inside" software!
We got computers, we're tapping phone lines, we know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Higher Power: 2^756839 - 1  | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."