Cryptography Reference
In-Depth Information
9.5.3 F4 and F5
Jsteg was the first generation of programs designed to hide informa-
tion in the JPEG image format, but attackers soon discovered it left
a serious statistical signature. The coefficents in JPEG compression
normally fall along a bell curve and the information hiding process
distorts this. In most photographs, the most common coefficient is
0
followed by
1
and
2
, etc. The occur-
rence of coefficients drops off as the coefficients get larger.
Jsteg ruins this smooth curve when information is hidden. The
coefficients of
2
and
3
, for instance, are interchanged by the process
of tweaking the least significant bit leaving both of them occurring
in equal proportions. [JJ98a, JJ98b, WP99, Wes01] The same happens
with coefficient pairs like
4
and
5
or
−
1
, followed again by
2
and
−
2
.FindingaJPEGfile
with many pairs of coefficients that occur in equal probability is a
sure sign that a message may be hidden with the Jsteg algorithm.
One solution is to change the probability of zeros and ones in the
information being hidden. The algorithms from Chapter 6 make it
possible to change the statistical probability to mimic any distribu-
tion. Let's say that our analysis of JPEG image shows that the coeffi-
cient of
3
occurs about
60%
as often as
2
.A
3
corresponds to a hidden
bit of
1
and a
2
corresponds to a hidden bit of
0
.Ifwecouldarrange
for the number of
1
s to be hidden about
60%
as often as the number
of
0
s, then the coefficients would balance out.
Here's one basic solution. Create a collection of
−
1
and
−
bit words and
uses these as characters for the algorithm in section 6.2.1. Use the
number of zeros and ones in the word to determine the weight. If a
zero is assigned weight
n
375
, the values will
emerge in something approximating a distribution of
1
to
.
625
and a one is assigned
.
.
6
.
=8
.Thereare
256
characters in the alphabet.
Give
00000000
aweightof
8
For example, let
n
× .
625
,
00000001
aweightof
7
× .
625 +
.
375
, etc. These can be used to build a Huffman tree to change the
statistics of the incoming data. If this pre-processing is done, the
statistics of the Jsteg algorithm begin to come much closer to real
images. This isn't perfect, but it doesn't need to be because the values
of the coefficients vary from image to image.
Andreas Westfeld proposes another solution to the statistical gap.
His algorithm, F4, encodes the data with more care avoiding the sta-
tistical distortions. [Wes01]
Here's the mechanism for hiding a coefficient
C
:
•
If
=0
, skip over it and don't hide any information in this
coefficient. This decreases the effectiveness of the algorithm,
but there's no choice. Jsteg also does this.
C
