Image analysis – Applications
Reexamination Certificate
2001-06-22
2004-12-14
Boudreau, Leo (Department: 2621)
Image analysis
Applications
Reexamination Certificate
active
06831991
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to steganography. Steganography is the art of secret communication, whose purpose is to hide the very presence of a communication. In particular this invention relates to the detection of hidden messages.
Steganography differs from cryptography, whose goal is to make communication unintelligible to those who do not posses the right keys. By means of steganography, digital images, videos, sound files, and other computer files that contain perceptually irrelevant or redundant information can be used as covers, that is, as carriers that hide secret messages embedded within. If one embeds a secret message into a cover-image, one obtains a “stego-image.”
The stego-image cannot contain any detectable artifacts that result from embedding the secret message. If it does, a third party can use such artifacts to determine that a secret message lies within the stego-image. Once the third party can reliably detect the presence of the secret message, the steganographic tool becomes useless.
Images stored in the JPEG format make very poor cover images for steganographic methods that embed information in the spatial (pixel) domain. The quantization introduced by JPEG compression can serve as a “watermark” or unique fingerprint, and one can detect even very small modifications of the cover image by inspecting the compatibility of the stego-image with the JPEG format. (See J. Fridrich, M. Goljan, and R. Du, “Steganalysis based on JPEG compatibility”,
SPIE Multimedia Systems and Applications IV,
Denver, Colo. (Aug. 20-24, 2001), to be presented).
Most steganographic programs use Least Significant Bit embedding (“LSB”) as the method of choice to hide a message in 24-bit and 8-bit color images, and in grayscale images. They do so because it is generally believed that changes to the LSBs of colors cannot be detected. The noise that is always present in digital images is thought to mask such changes.
The present inventors have developed a steganographic method to detect LSB embedding in 24-bit color images. (See J. Fridrich, R. Du, and L. Meng, “Steganalysis of LSB Encoding in Color Images”,
ICME
2000, New York City, July 31-August 2, New York.) This RQP method is based on analyzing close pairs of colors created by LSB embedding. It works reasonably well as long as the number of unique colors in the cover image is less than 30% of the number of pixels. The size of the secret message can be estimated only very roughly. The results become progressively unreliable once the number of unique colors exceeds roughly 50% of the number of pixels, as happens frequently for high resolution raw scans and images taken with digital cameras stored in an uncompressed format. Another disadvantage of the RQP method is that it cannot be modified for grayscale images.
Westfeld and Pfitzmann (“Attacks on Steganographic Systems”,
Proc.
3
rd
Info. Hiding Workshop,
Dresden, Germany, Sep. 28-Oct. 1, 1999, pp. 61-75) introduced a method based on statistical analysis of Pairs of Values (PoVs) that are exchanged during message embedding. These PoVs could be formed, for example, by pairs of colors that differ in the LSB only. This method provides very reliable results when the message's placement is known (e.g., when it is sequential). However, randomly scattered messages can only be reliably detected with this method when the message length becomes comparable with the number of pixels in the image.
Johnson and Jajodia (“Steganography: Seeing the Unseen.”
IEEE Computer,
February 1998, pp.26-34; “Steganalysis of Images Created Using Current Steganography Software.”
Proceedings of Workshop on Information Hiding,
Portland, Oreg., April 1998. Also published as
Notes in Computer Science,
vol. 1525, Springer-Verlag, 1998) pointed out that steganographic methods for palette images that preprocess the palette can be vulnerable. A number of steganographic programs create clusters of close palette colors that can be swapped for each other to embed message bits. This swapping can be done by decreasing the color depth and then expanding it to 256 by making small perturbations to the colors. This preprocessing creates suspicious pairs (clusters) of colors that can be easily detected. However, steganographic techniques that do not modify the palette (e.g., those that hide messages by embedding LSB into the pointers) cannot be detected by inspecting the palette itself.
Thus there is a need for reliable and accurate steganalytic techniques that can be applied to both 24-bit color images and to 8-bit grayscale or color images with randomly scattered message bits embedded in the LSBs of colors or pointers to the palette.
OBJECTS AND SUMMARY OF THE INVENTION
An object of the present invention is to provide an efficient, accurate, and simple method to reliably detect LSB embedding.
A further object of the present invention is to provide such a method to reliably detect LSB embedding in randomly scattered pixels.
Still a further object of the present invention is to provide such a method to reliably detect LSB embedding where the randomly scattered pixels are in both 24-bit color images and 8-bit grayscale or color images.
Briefly stated, the present invention provides a system and a method that efficiently, accurately, and simply detect reliably least-significant-bit (“LSB”) embedding of a secret message in randomly scattered pixels. The system and method apply to both 24-bit color images and 8-bit grayscale or color images. Many commercial steganographic programs use Least Significant Bit embedding (LSB) as the method of choice to hide messages in 24-bit, 8-bit color images and in grayscale images. They do so based on the common belief that changes to the LSBs of colors cannot be detected because of noise that is always present in digital images. By inspecting the differences in capacity for lossless (invertible) embedding in the LSB and the shifted LSB plane, the present invention reliably detects messages as short as 1% of the total number of pixels (assuming 1 bit per sample). The system and method of the present invention are fast, and they provide accurate estimates for the length of the embedded secret message.
According to an embodiment of the invention, a method for detecting least significant bit (“LSB”) embedding of a message hidden in randomly scattered samples of an alleged cover image comprises the steps of:
dividing the alleged cover image into a plurality of disjoint groups of adjacent samples; defining a discrimination function that assigns a real number to each member of the plurality, thereby capturing the smoothness of each of the groups; defining on the plurality at least one invertible operation that comprises a permutation of sample values, whereby values of the samples are invertibly perturbed by a small amount; applying the discrimination function and the flipping operation to define in the plurality three types of sample groups, (R)egular, (S)ingular, and (U)nusable, each of the types being defined for both positive and negative operations; plotting both positive and negative R and S for the alleged cover image on an RS diagram; constructing four curves of the RS diagram and calculating their intersections by extrapolation; and determining the existence or nonexistence of a secret message from the intersections.
According to a feature of the invention, apparatus for detecting least significant bit (“LSB”) embedding of a message hidden in randomly scattered samples of an alleged cover image comprises means for dividing the alleged cover image into a plurality of disjoint groups of adjacent samples; first means for defining effective for defining a discrimination function that assigns a real number to each member of the plurality, thereby capturing the smoothness of each of the groups; second means for defining effective for defining on the plurality at least one invertible operation that comprises a permutation of sample values, whereby values of the samples are invertibly perturbed by a small amount; means for applying the discrimination function and t
Fridrich Jessica
Goljan Miroslav
Boudreau Leo
Hancock & Estabrook, LLP
Lu Tom Y.
Pastel Christopher R.
The Research Foundation of SUNY State University Plaza
LandOfFree
Reliable detection of LSB steganography in color and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reliable detection of LSB steganography in color and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reliable detection of LSB steganography in color and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3289030