Statistics of Low-Order Bits in Images

Several folks have recently mentioned the need to carefully look at
the statistics/distributions of bit values in the low-order bits
(least-significant bits, LSBs) of real-world images intended for
steganographic use. I concur.

This problem interests me. Material from Li and Vitanyi's "An
Introduction to Kolmogorov Complexity and Its Applications," 1993,
bears directly on the issues of "picture distance" and how much one
can change an image before it's recognizably "different" or before
filter programs can detect the presence (or absence) of characteristic
structure in images.

In this little article I'll be making some general points and
reasoning informally about image statistics, picture distances, and
the like. There's no doubt a more rigorous way to reason about these
statistical properties, using sigmas and summations and Central Limit
Theorems and the like, but I'm not that much of a real mathematician
to be bothered with that. C'est la vie.

Several points:

1. Probably not a pressing concern, yet. I expect few sites have
LSB-analyzers, just as few folks are using LSB stegonagraphy.

2. Romana Machado's "Stego" program for the Mac is interesting, and
may be useful, but it makes almost no effort to hide the _existence_ of
the message bits, e.g., anyone with a copy of Stego can apply it to an
image and recover the plaintext or ciphertext. (I mean in contrast to
some of the schemes which require a copy of the original image, a kind
of one-time pad approach, in which one XORs or subtracts the original
image to see the "differences" in the LSBs--a cryptanalyst without the
"reference" image is unable to extract any bits for further analysis.)

(I suggest we keep these two models in mind. Proposal for jargon:
"Type 1 Stego": No reference model needed: message bits are just the
specified bits, e.g., LSB, or larger low-order bits. "Type 2 Stego": a
reference model--an image or DAT or whatever--is needed to XOR with
message to recover the plaintext or ciphertext (if more encryption was
used originally).)

3. With fairly noisy 8-bit images, such as might be gotten by
frame-grabbing a video image under poor lighting or focus conditions,
my experiences at Intel (I ran an image processing lab, for electron
microscope analyis of microprocessors) tells me that the lowest
_several_ bits of each pixel are "noisy." Very noisy. The bottom bit
is "almost purely noise" (also a dangerous term!).  But I agree that
more recent images need to be looked at and the statistics analyzed.

Still, I suspect the bottom bit, the LSB, will be found to have
Gaussian noise characteristics. Note also that images are often run
through filters, as in PhotoShop, which can give Gaussian
characteristics where before there were none.

4. Can "image analyzers" in the hands of border security/law
enforcement be used to proseute holders of images that have such
white noise characteristics in the LSBs? I doubt it.

I interject this point here because an important long-term issue for
stego is whether the "Crypto Authority" (resonance with Gibson's
"Turing Authority") can make such images ipso facto illegal. I suspect
this is hopeless, both because many images have these characteristics
and because many people will massage their images to be this way,
regardless of original camera-CCD characteristics.

5. All of these arguments apply to the LSBs in DATs. Ambient room
noise, noise in microphones, thermal noise in the electronics, etc.,
all contributes to there being almost no "signal" in the LSB of a
16-bit CD or DAT sample of music. (There are anecdotal reports of
people being able to hear effects here, and different noise-shaping
filters may have audible effects at least some of the time. So, I do
agree that these statistics ought to be looked at, eventually. Some of
my audio magazines have articles on this, which I'll try to look at
soon.)

6. Here's a strategy which may work OK even if the statistical
patterns of the LSBs are not "completely random" (a dangerous term, of
course).

- take a plaintext or ciphertext and compress it with a good
compressor (L-Z may not be enough to wring out all the structure and
raise the entropy to the full 8 bits per character, for ASCII). A good
encryption of the text should of course produce high entropy.

- XOR the compressed (high entropy) text with the LSBs of the image.

- the resulting LSBs should have _similar statistics_ as compared with
the original image. "Noise" has been added, but no knew structure has
been added. Consider a couple of examples to see this:

Original image (in bits) :    1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1
Random      1s and Os:        1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 1 0
Resultant Image (XOR):        0 1 1 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 1 1

(Another example: If one toggles all the bits in a binary image, the
"Hamming distance" between the images is maximal, and yet the "picture
distance" is very small, i.e., the images look nearly the same. The
picture distance being small means the structure is the same, even
though the Hamming distance is, by definition, the greatest it can
be. This provides a powerful clue that there is a "lot of room" to
manipulate images so as to pack bits into this "Hamming space" while
still keeping the resulting pictures in a "tiny picture space
volume.")

Well, this is of coure not a proof, but gives a feel for why XORing
with a high entropy image will not _add_ structure.

However, it can certainly _remove_ structure! Which takes us back to
the original issue of the statistics (structure) of the LSBs of
images. If in fact there were "clumps" of 1s and 0s, "ridges" and
"valleys" caused by camera/CCD characteristics, then XORing the LSB
image with a "random" image will demolish this structure. This is
nothing more than the role of the one-time pad....to remove structure
but allow its immediate reconstruction on the other end.

At least in this case one does not have to worry about the ciphertext
_adding_ unwanted structure, only that it may _remove_ structure
already present in the image (and perhaps "typical" of images not
carrying stego bits). 

7. A better approach may be to take two very similar images, perhaps
successive frame grabs with the same camera/digitizer, and use the
statistics of the LSBs directly as part of the "one-time pad" above
(Type 2 Stego). This could be used to give the LSBs the same
"structure" (ridges and valleys of pixel values, for example) as a
"real image" but without leaking message bits. (More work needed here.)

(I apologize for any vagueness here. Partly it is that I haven't
worked this out completely. Partly it is the lack of a blackboard to
draw pictures on--verbal descriptions get confusing after a while. And
partly it is that this message is already too long and I want to wrap
it up.)

8. None of this subtlety really matters too much, I suspect. An image
or DAT contains _so much room_ for stego bits that the problem of
finding a tiny fraction of message bits in megabytes or hundreds of
megabytes (DATs) of noisy source material seems well beyond current
crunch capabilties. Perhaps images being sent to some sensitive
location could be given a quick analysis to see if the LSBs are "too
regular," but even this I doubt. And at least the XOR method described
above won't introduce new structure....at worst the images or DATs
would appear to be "too random."

Perhaps we need to paraphrase Eric's line: "Use a random image, go to jail."

--Tim May

-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^756839 | Public Key: PGP and MailSafe available.
Note: I put time and money into writing this posting. I hope you enjoy it.

Some other factors one needs to consider when analyzing images are:

* The lsb is going to be random if the image comes from any kind of a/d
  process. This is because all convertors have a error of +/- 1 bit.

* If an image is processed by software then the last significant bit will be
  on or off consistantly for a given color.

* By the use of exlusive-or operators it is possible to mask the data in a
  suitable manner. This does require that both sender and reciever have a
  copy or method of calculating the correct key.

The process as I understand it now to use a graphical concealment cypher is:

1. Both parties agree a priori on at least a way to generate suitable keys
   for masking.

2. You take your message and x-or it with a suitable bit stream.

3. The resultant x-or bit stream is placed in the image as the lsb.

4. Upon receipt, you strip out the x-or bit stream.

5. Generate the appropriate key and use exclusive-or to return the data
   stream.

The real question is how do you generate keys?

I see a method using the data bit stream itself as part of the answer. The
algorithm would look at some parameter like character statistics or entropy
of a text. It would look at the data stream and calculate its value. Then the
hard part is to try various bit streams and measure their x-or value. The
process is similar to Newtons Iterative Method for finding roots of
polynomials.

Jim Choate writes:

> Some other factors one needs to consider when analyzing images are:
> 
> * The lsb is going to be random if the image comes from any kind of a/d
>   process. This is because all convertors have a error of +/- 1 bit.

Nope. Not true. Some ADCs digitize with _more_ than the final
resolution and then do rounding or noise-shaping. And ADCs even at the
LSB can still have structure caused by other things, such as the image
itself (a binary image with thresholding will have the "LSB" certainly
not random noise! Q.E.D., by induction.) 

This can give the LSBs in the final product (image, DAT, CD) nonrandom
noise characteristics. This is what we're talking about.

> * If an image is processed by software then the last significant bit will be
>   on or off consistantly for a given color.

Huh? What if the "processing" is "do nothing"? Why will LSBs be
changed consistently? I must be misunderstanding your statement.


> * By the use of exlusive-or operators it is possible to mask the data in a
>   suitable manner. This does require that both sender and reciever have a
>   copy or method of calculating the correct key.

Key generation and sharing (if necessary) is separate from the stego issues.

> The real question is how do you generate keys?

In various ways, depending on what you're doing. Separate from the
main analysis of stego and image statistics/

--Tim May


-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^756839 | Public Key: PGP and MailSafe available.
Note: I put time and money into writing this posting. I hope you enjoy it.

> 
> Jim Choate writes:
> 
> > Some other factors one needs to consider when analyzing images are:
> > 
> > * The lsb is going to be random if the image comes from any kind of a/d
> >   process. This is because all convertors have a error of +/- 1 bit.
> 
> Nope. Not true. Some ADCs digitize with _more_ than the final
> resolution and then do rounding or noise-shaping. And ADCs even at the
> LSB can still have structure caused by other things, such as the image
> itself (a binary image with thresholding will have the "LSB" certainly
> not random noise! Q.E.D., by induction.) 
> 
> This can give the LSBs in the final product (image, DAT, CD) nonrandom
> noise characteristics. This is what we're talking about.

Sounds like the simple solution is for people everywhere to replace
the low order bits of all of their pictures with good random noise. Image
quality shouldnt suffer drastically and if the random data is replaced
with output from a good cryptosystem then it would be indistinguishable.
So are any people here influential with the authors of any popular
imaging software?

>Sounds like the simple solution is for people everywhere to replace
>the low order bits of all of their pictures with good random noise. 

An excellent idea.

It's not the imaging software which need do this, but the
steganography software.  The only addition is a random number source
and a way of using that instead of a file.

Eric

-----BEGIN PGP SIGNED MESSAGE-----

> The real question is how do you generate keys?

You use a known source of material. For example, here's one way you
could easily distribute messages to a wide audience using
off-the-shelf tools.  

1. Buy one of the many porno CD-ROMs. Pick one which is fairly
widespread and to which your source will also have access (i.e. if
you're in Denmark, don't choose a child porno CD to communicate with
someone in the US.) Of course, audio or other types of data CDs will
work here too.

2. Make _prearranged_ changes to your source file: convert JPEG->GIF,
or apply a Gaussian blur- whatever suits your fancy.
 
3. XOR in your message text.

4. Post to Usenet,  indicating the source of the materials (i.e. "This
picture came from `Girls of The Rural South, vol 1'" or "Audio sampled
from Michael Jackson's _Dangerous_")

Step 1 insures that your recipient will have access to the same source
material. Step 2 helps mask your message by introducing _other_
differences between the step 1 source and the transmitted message.
Step 4 gives you an easy, safe, distributed transmission medium.

Repeat as necessary.

- -Paul

- -- 
Paul Robichaux, KD4JZG      | "Violence on TV? Why can't it be on CSPAN?"
Intergraph Federal Systems  |     - Clayton Cramer, cramer@optilink.com
Not speaking for Intergraph | Be a cryptography user. Ask me how.


-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLPuvliA78To+806NAQHinwQAjYCOz85KnpG49G5wat6bUew1TQHVhB9B
YatgH2aBDhxADDNVB2f9V2ozs/t35grX3zkwKbB3yWcxAHjIoJg2vuKP8CrHrqZ9
Q7NJlbRUQczZLGoUi8S3jO35a6cyABDofTydmhsSj/Si6vgBRoit2reDA/Agkt3X
Y1r4Qv7Dbzs=
=8GwG
-----END PGP SIGNATURE-----

paul@poboy.b17c.ingr.com (Paul Robichaux) describes procedure for
preparing and sending steganographically-concealed data via Usenet:

>  4. Post to Usenet,  indicating the source of the materials (i.e. "This
>  picture came from `Girls of The Rural South, vol 1'" or "Audio sampled
>  from Michael Jackson's _Dangerous_")

Has anyone already tried looking for structure in the LSB's of the
"megabytes of copyright violations" already flowing thru
alt.binaries.pictures.* ?

-Anthony Garcia
agarcia@neosoft.com
--Why, didn't you know?  That's how the blacknet.* hierarchy gets propagated...