Steganography : Ideas for New Software

----------------------------------------------------------------------------
               A WORK IN PROGRESS : Please keep checking back
----------------------------------------------------------------------------

8-Bit Images

Assume a palette-mapped image with 256 entries in the palette. First
construct a bijection f (with inverse f') from {0,1,..,255} to the 256
(R,G,B)-triples. Typically, this would be done by sorting the entries, using
the red, green, and blue components as primary, secondary, and tertiary
sort-keys.

Now construct a second bijection g (with inverse g') from {0,1,..,256!-1} to
the set of permutations of {0,1,..,255}.

The message can be considered as a single very large number m, with a length
header prefixed to differentiate between the one- two- and three-byte
messages (0), (0,0), (0,0,0), ...

If g(m)=(n0, n1, ..., n255), rearrange the image palette so that the i-th
palette entry P(i)=f(ni).

As both f and g are bijections, the procedure is reversible, and the message
m safely extracted.

Comments :

   * log(256!)/log(256) is 210.5. So we can inject up to 210 bytes in this
     way (a 209-byte message if a one-byte header is used for its length).

   * We can trivially generalise the procedure any palette size x, and for x
     in [60,256], log(x!)/log(256)~=0.9x-23.

   * The image is not degraded at all - the palette is simply sorted
     differently.

   * For most compressed formats (such as GIF), the compressed size should
     remain constant.

   * The only requirement is that the image contain each palette entry at
     least once (so as not to arouse suspicion.) It is thus possible to
     inject a 209-byte message into a 256-pixel image!

   * The fact that the palette will appear to be in a random order should
     not arouse suspicion as many common tools, such as djpeg -gif and
     ppmtogif, also do this. However, note that unsorted greyscale palettes
     are much rarer.

     (TO DO : Investigate how the apparently random palette-order of these
     programs is generated. Is it, as I suspect, the order that they occur
     within the image?)

Unfortunately, construction of g is non-trivial. The algorithm that I have
developed follows, but I am unsatisfied that this is particularly
efficient...

  1. Build a 256-element array A such that A[i]=i.

  2. For n := 2 to 256

       1. Circular shift right the first n elements of A by m mod n.

       2. m := m / n.

  3. The output of g is A[0], A[1], .., A[255].

Proof that g is a bijection by induction.

CONCLUSION : This is too good to be true. Where'd I go wrong?

----------------------------------------------------------------------------
Bob Tinsley tinsley@dcs.warwick.ac.uk