Cryptography Reference
In-Depth Information
This basic mechanism hides bits in pairs of pixels or data items.
The solution does not change the basic statistical profile of the un-
derlying file, an important consideration because many attacks on
steganography rely on statistical analysis. Of course, it
does
change
The locations of
transistors on a circuit
can be sorted in
different ways to hide
information that may
track the rightful
owner.[LMSP98]
some of the larger statistics about which pixels of some value are near
other pixels of a different value. Attackers looking at basic statistics
won't detect the change, but attackers withmore sophisticated mod-
els could.
The algorithm can also be modified to hide the information sta-
tistically. An early steganographic algorithm called Patchwork re-
peats this process a number of times to hide the same bit in nu-
merous pairs. The random process chooses pairs by selecting one
pixel from one set and another pixel from a different set. The mes-
sage is detected by comparing the statistical differences between
the two sets. The largest one identifies the bit being transmitted.
There's no attempt made to synchronize the random selection of pix-
els. [BGML96, GB98].
In this simple example, one bit gets hidden in the order of 2
1
items. The process can be taken to any extreme by choosing sets
of
pixels or items and hiding information in the order of all of
them. Here's one way that a set of
n
n
items,
{x
0
,x
1
,...,x
nā1
}
,can
encode a long log
n
!-bit number,
M
.Set
m
=
M
and let
S
be the set
{x
1
,x
2
,...,x
n
}
. Let the answer, the set
A
, begin as the empty set.
Repeat this loop for
i
taking values beginning with
n
and dropping to
2.
1. Select the item in
S
with the index
mmodi
.Theindicesstartat
0 and run up to
i ā
1. There should only be
i
elements left in
S
at each pass through the loop.
2. Remove the item from
S
and stick it at the end of
A
.
m
i
3. Set
m
=
. Round down to the nearest integer.
The value of
M
can be recoveredwith this loop. Beginwith
m
=1.
1. Remove the first element in
A
.
2. Convert this element into a value by counting the values left
in
with a subscript that is less than its own. That is, if you
remove
A
x
i
,countthevaluesof
x
j
still in
A
where
j<i
.
3. Multiply
m
by this count and set it to be the new value of
m
.
Using this steganographically often requires finding a way to as-
sign a true order to the element. This algorithm assumes that the
