detectable artifacts due to message embedding. In other words, the set of stego-
images should have the same statistical properties as the set of cover-images. If there
exists an algorithm that can guess whether or not a given image contains a secret
message with a success rate better than random guessing, the steganographic system
is considered broken. For a more exact treatment of the concept of steganographic
security, the reader is referred to [1–3].
The ability to detect secret messages in images is related to the message length.
Obviously, the less information we embed into the cover-image, the smaller the
probability of introducing detectable artifacts by the embedding process. Each
steganographic method has an upper bound on the maximal safe message length (or
the bit-rate expressed in bits per pixel or sample) that tells us how many bits can be
safely embedded in a given image without introducing any statistically detectable
artifacts. Determining this maximal safe bit-rate (or steganographic capacity) is a non-
trivial task even for the simplest methods. Chandramouli et al. [4] give a theoretical
analysis of the maximal safe bit-rate for LSB embedding in the spatial domain.
Recently, Fridrich et al. [5,6] derived a more stringent estimate using dual statistics
steganalysis.
The choice of cover-images is important because it significantly influences the
design of the stego system and its security. Images with a low number of colors,
computer art, images with a unique semantic content, such as fonts, should be
avoided. Aura [7] recommends grayscale images as the best cover-images. He also
recommends uncompressed scans of photographs or images obtained with a digital
camera containing a high number of colors, and considers them safest for
steganography.
The choice of the image format also makes a very big impact on the design of a
secure steganographic system. Raw, uncompressed formats, such as BMP, provide the
biggest space for secure steganography, but their obvious redundancy makes them
very suspicious in the first place. Indeed, some researchers do not consider those
formats for steganography claiming that exchanging uncompressed images is
“equivalent” to using cryptography [8]. Never the less, most steganographic products
available on the Internet work with uncompressed image formats or formats that
compress data losslessly (BMP, PCX, GIF, PGM, and TIFF).
Fridrich et al. [9] have recently shown that cover-images stored in the JPEG format
are a very poor choice for steganographic methods that work in the spatial domain.
This is because the quantization introduced by JPEG compression can serve as a
"semi-fragile watermark" or a unique fingerprint that can be used for detection of very
small modifications of the cover-image by inspecting the compatibility of the stego-
image with the JPEG format. Indeed, changes as small as flipping the least significant
bit (LSB) of one pixel can be reliably detected. Consequently, one should avoid using
decompressed JPEG images as covers for spatial steganographic methods, such as the
LSB embedding or its variants.
Despite its proven insecurity, the method of choice of most publicly available
steganographic tools is the LSB embedding. This paradigm can be adapted not only to
raw formats but also to palette images after pre-sorting the palette (EZ Stego [10])
and to JPEG images (J-Steg [10], JP Hide&Seek [10], and OutGuess [11]).
Fridrich et al. [5,6] introduced the dual statistics steganalytic method for detection
of LSB embedding in uncompressed formats. For high quality images taken with a
