Reliable detection of LSB steganography in color and grayscale images

Abstract

A system and 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.

1. A method for detecting least significant bit (“LSB”) embedding of a message hidden in randomly scattered samples of an alleged cover image, comprising 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 said plurality of disjoint groups, thereby capturing the smoothness of each of said groups;  
 defining on said plurality of disjoint groups at least one invertible operation that comprises a permutation of sample values, whereby values of said samples are invertibly perturbed by a small amount;  
 applying said discrimination function and said invertible operation to define in said plurality three types of sample groups, (R)egular, (S)ingular, and (U)nusable, each of said types being defined for both positive and negative operations;  
 plotting both positive and negative R and S for said alleged cover image on an RS diagram;  
 constructing four curves of said RS diagram and calculating their intersections by extrapolation; and  
 determining the existence or nonexistence of a secret message from said intersections.  
 
     
     
       2. The method of  claim 1 , further including the step, if said secret message is determined to exist, of estimating a length thereof. 
     
     
       3. The method of  claim 2 , wherein each of said samples is a pixel value. 
     
     
       4. The method of  claim 3 , wherein said pixel value is a grayscale. 
     
     
       5. The method of  claim 3 , wherein said pixel value is a color. 
     
     
       6. The method of  claim 2 , wherein each of said samples is an index to a palette of color values. 
     
     
       7. The method of  claim 1 , wherein said step of constructing further comprises arithmetically averaging the x coordinates of said intersections, thereby detecting said hidden message, if it exists, and estimating a length thereof. 
     
     
       8. The method of  claim 2 , wherein said step of estimating further comprises determining a length p of said hidden message, if it exists, by rescalingthe x-axis of said RS diagram so that p/2 becomes 0 and 100−p/2 becomes 1, whereby an x-coordinate of an intersection is a root of the following quadratic equation:
   2(d 1 +d 0 )x 2 +(d −0 −d −1 −d 1 −3d 0 )x+d 0 −d −0 =0,  
 
       where d 0 =R M (p/2)−S M (p/2), d 1 =R M (1−p/2)−S M (1−p/2), d −0 =R −M (p/2)−S −M (p/2), d −1 =R −M (1−p/2)−S −M (1−p/2), and said message length p is calculated from the root x whose absolute value is smaller,
   p=x/(x−½).  
 
     
     
       9. Apparatus for detecting least significant bit (“LSB”) embedding of a message hidden in randomly scattered samples of an alleged cover image, which comprises:
 means for dividing said 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 said plurality of disjoint groups, thereby capturing the smoothness of each of said groups;  
 second means for defining  effective for defining on said plurality of disjoint groups at least one invertible operation that comprises a permutation of sample values, whereby values of said samples are invertibly perturbed by a small amount;  
 means for applying said discrimination function and said invertible operation to define in said plurality three types of sample groups, (R)egular, (S)ingular, and (U)nusable, each of said types being defined for both positive and negative operations;  
 means for plotting both positive and negative R and S for said alleged cover image on an RS diagram;  
 means for constructing four curves of said RS diagram;  
 means for calculating the intersections of said four curves by extrapolation; and  
 first means for determining effective for determining from said intersections the existence or nonexistence of a secret message.  
 
     
     
       10. The apparatus of  claim 9 , further including means for estimating a length of said secret message if said secret message is determined to exist. 
     
     
       11. The apparatus of  claim 10 , wherein each of said samples is a pixel value. 
     
     
       12. The apparatus of  claim 11 , wherein said pixel value is a grayscale. 
     
     
       13. The apparatus of  claim 11 , wherein said pixel value is a color. 
     
     
       14. The apparatus of  claim 10 , wherein each of said samples is an index to a palette of color values. 
     
     
       15. The apparatus of  claim 9 , wherein said means for constructing and calculating is further effective for arithmetically averaging the x coordinates of said intersections, thereby detecting said hidden message and estimating a length thereof. 
     
     
       16. The apparatus of  claim 10 , wherein said means for estimating is effective for determining a length p of said hidden message by rescaling the x-axis of said RS diagram so that p/2 becomes 0 and 100−p/2 becomes 1, whereby an x-coordinate of an intersection is a root of the following quadratic equation:
   2(d 1 +d 0 )x 2 +(d −0 −d −1 −d 1 −3d 0 )x+d 0 −d −0 =0,  
 
       where d 0 =R M (p/2)−S M (p/2), d 1 =R M (1−p/2)−S M (1−p/2), d −0 =R −M (p/2)−S −M (p/2), d −1 =R −M (1−p/2)−S −M (1−p/2), and said message length p is calculated from the root x whose absolute value is smaller,
   p=x/(x−½).  
 
     
     
       17. A computer-readable storage medium embodying program instructions for a method for detecting least significant bit (“LSB”) embedding of a message hidden in randomly scattered samples of an alleged cover image, said method comprising the steps of:
 dividing said 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 said plurality of disjoint groups, thereby capturing the smoothness of each of said groups;  
 defining on said plurality of disjoint groups at least one invertible operation that comprises a permutation of sample values, whereby values of said samples are invertibly perturbed by a small amount;  
 applying said discrimination function and said invertible operation to define in said plurality three types of sample groups, (R)egular, (S)ingular, and (U)nusable, each of said types being defined for both positive and negative operations;  
 plotting both positive and negative R and S for said alleged cover image on an RS diagram;  
 constructing four curves of said RS diagram and calculating their intersections by extrapolation; and  
 determining the existence or nonexistence of a secret message from said intersections.  
 
     
     
       18. The computer-readable storage medium of  claim 17 , said method further including the step, if said secret message is determined to exist, of estimating a length thereof. 
     
     
       19. The computer-readable storage medium of  claim 17 , said method further including, in said step of constructing, arithmetically averaging the x coordinates of said intersections, thereby detecting said hidden message, if it exists, and estimating a length thereof. 
     
     
       20. The computer-readable storage medium of  claim 17 , said method further including, in said step of estimating, determining a length p of said hidden message, if it exists, by rescalingthe x-axis of said RS diagram so that p/2 becomes 0 and 100−p/2 becomes 1, whereby an x-coordinate of an intersection is a root of the following quadratic equation:
   2(d 1 +d 0 )x 2 +(d −0 −d −1 −d 1 −3d 0 )x+d 0 −d −0 =0,  
 
       where d 0 =R M (p/2)−S M (p/2), d 1 =R M (1−p/2)−S M (1−p/2), d −0 =R −M (p/2)−S −M (p/2), d −1 =R −M (1−p/2)−S −M (1−p/2), and said message length p is calculated from the root x whose absolute value is smaller,
   p=x/(x−½).  
 
     
     
       21. A method for detecting embedding of a message hidden in scattered samples of an alleged cover image, comprising the steps of:
   dividing the alleged cover image into a plurality of disjoint groups of samples;        defining a discrimination function that assigns a real number to each member of said plurality of disjoint groups, thereby capturing the smoothness of each of said groups;        defining on said plurality of disjoint groups at least one invertible operation that comprises a permutation of sample values, whereby values of said samples are invertibly perturbed by a small amount;        applying said discrimination function and said invertible operation to define in said plurality at least three types of sample groups, at least two of the types of sample groups being usable, each of said usable types being defined for both positive and negative operations;        analyzing a distribution of the at least two usable types for both positive and negative operations for said alleged cover image with respect to a quantized spatial image representation; and        determining the existence or nonexistence of a secret message from said distribution.     
     
     
       22. The method of  claim 21 , further including the step, if said secret message is determined to exist, of estimating a length thereof. 
     
     
       23. The method of  claim 22 , wherein each of said samples is a pixel value. 
     
     
       24. The method of  claim 23 , wherein said pixel value is a grayscale. 
     
     
       25. The method of  claim 23 , wherein said pixel value is a color. 
     
     
       26. The method of  claim 22 , wherein each of said samples is an index to a palette of color values. 
     
     
       27. The method of  claim 21 , wherein method further comprises the steps of:
   applying said discrimination function and said invertible operation to define in said plurality three types of sample groups,  ( R ) egular,  ( S ) ingular, and  ( U ) nusable, each of said types being defined for both positive and negative operations;        plotting both positive and negative R and S for said alleged cover image on an RS diagram;        constructing four curves constructing four curves of an RS diagram and calculating their intersections by extrapolation; and        arithmetically averaging the x coordinates of said intersections, thereby detecting said hidden message, if it exists, and estimating a length thereof.     
     
     
       28. The method of  claim 22 , wherein method further comprises the steps of:
   applying said discrimination function and said invertible operation to define in said plurality three types of sample groups,  ( R ) egular,  ( S ) ingular, and  ( U ) nusable, each of said types being defined for both positive and negative operations;        plotting both positive and negative R and S for said alleged cover image on an RS diagram;        constructing four curves constructing four curves of an RS diagram and calculating their intersections by extrapolation; and        wherein said step of estimating further comprises determining a length p of said hidden message, if it exists, by rescaling the x - axis of said RS diagram so that p/ 2  becomes  0  and  100 −p/ 2  becomes  1 , whereby an x - coordinate of an intersection is a root of the following quadratic equation:          2   ( d   1   +d   0 ) x   2 +( d   −0   −d   −1   −d   1   − 3 d   0 ) x−d   −0   = 0 ,          where d   0   =R   M ( p/ 2   ) −S   M ( p/ 2   ) , d   1   =R   M (   1 −p/ 2   ) −S   M (   1 −p/ 2   ) , d   −0   =R   −M ( p/ 2   ) −S   −M ( p/ 2   ) , d   −1   =R   −M (   1 −p/ 2   ) −S   −M (   1 −p/ 2   ) , and said message length p is calculated from the root x whose absolute value is smaller,        p=x/ ( x−  1 / 2   ).     
     
     
       29. An apparatus for detecting embedding of a message hidden in randomly scattered samples of an alleged cover representing perceptual data, comprising:
   an input for receiving perceptual data;        a processor, adapted for processing the received perceptual data, implementing an algorithm as follows:      dividing said alleged cover data into a plurality of disjoint groups of adjacent samples;        defining a discrimination function that assigns a real number to each member of said plurality of disjoint groups, thereby capturing the smoothness of each of said groups;        defining on said plurality of disjoint groups at least one invertible operation that comprises a permutation of sample values, whereby values of said samples are invertibly perturbed by a small amount;        applying said discrimination function and said invertible operation to define in said plurality at least three types of sample groups, at least two of the types of sample groups being usable, each of said usable types being defined for both positive and negative operations;        analyzing a distribution of the at least two usable types for both positive and negative operations for said alleged cover with respect to a quantized perceptual data representation; and        determining the existence or nonexistence of a secret message from said distribution; and          an output for presenting at least an indication of an existence of the secret message in the received perceptual data.     
     
     
       30. The apparatus of  claim 29 , wherein the processor further estimates a length of said secret message if said secret message is determined to exist. 
     
     
       31. The apparatus of  claim 30 , wherein each of said samples is a pixel value. 
     
     
       32. The apparatus of  claim 31 , wherein said pixel value is a grayscale. 
     
     
       33. The apparatus of  claim 31 , wherein said pixel value is a color. 
     
     
       34. The apparatus of  claim 30 , wherein each of said samples is an index to a palette of color values. 
     
     
       35. The apparatus of  claim 29 , wherein said algorithm further comprises the steps of:
   applying said discrimination function and said invertible operation to define in said plurality three types of sample groups,  ( R ) egular,  ( S ) ingular, and  ( U ) nusable, each of said types being defined for both positive and negative operations;        representing both positive and negative R and S for said alleged cover on an RS diagram;        constructing four curves constructing four curves of an RS diagram and calculating their intersections by extrapolation; and        arithmetically averaging the x coordinates of said intersections, thereby detecting said hidden message, if it exists, and estimating a length thereof.     
     
     
       36. The apparatus of  claim 30 , wherein said algorithm further comprises:
   applying said discrimination function and said invertible operation to define in said plurality three types of sample groups,  ( R ) egular,  ( S ) ingular, and  ( U ) nusable, each of said types being defined for both positive and negative operations;        plotting both positive and negative R and S for said alleged cover image on an RS diagram;        constructing four curves constructing four curves of an RS diagram and calculating their intersections by extrapolation; and        wherein said step of estimating further comprises determining a length p of said hidden message, if it exists, by rescaling the x - axis of said RS diagram so that p/ 2  becomes  0  and  100 −p/ 2  becomes  1 , whereby an x - coordinate of an intersection is a root of the following quadratic equation:          2   ( d   1   +d   0 ) x   2 +( d   −0   −d   −1   −d   1   − 3 d   0 ) x−d   −0   = 0 ,          where d   0   =R   M ( p/ 2   ) −S   M ( p/ 2   ) , d   1   =R   M (   1 −p/ 2   ) −S   M (   1 −p/ 2   ) , d   −0   =R   −M ( p/ 2   ) −S   −M ( p/ 2   ) , d   −1   =R   −M (   1 −p/ 2   ) −S   −M (   1 −p/ 2   ) , and said message length p is calculated from the root x whose absolute value is smaller,        p=x/ ( x−  1 / 2   ).     
     
     
       37. A computer- readable storage medium embodying program instructions for a method for detecting embedding of a message hidden in scattered samples of an alleged cover image, comprising the steps of:      dividing the alleged cover image into a plurality of disjoint groups of samples;        defining a discrimination function that assigns a real number to each member of said plurality of disjoint groups, thereby capturing the smoothness of each of said groups;        defining on said plurality of disjoint groups at least one invertible operation that comprises a permutation of sample values, whereby values of said samples are invertibly perturbed by a small amount;        applying said discrimination function and said invertible operation to define in said plurality at least three types of sample groups, at least two of the types of sample groups being usable, each of said usable types being defined for both positive and negative operations;        analyzing a distribution of the at least two usable types for both positive and negative operations for said alleged cover image with respect to a quantized spatial image representation; and        determining the existence or nonexistence of a secret message from said distribution.     
     
     
       38. The computer- readable storage medium of    claim 37   , said method further including the step, if said secret message is determined to exist, of estimating a length thereof.   
     
     
       39. The computer- readable storage medium of    claim 37   , said method further comprising the steps of:      applying said discrimination function and said invertible operation to define in said plurality three types of sample groups,  ( R ) egular,  ( S ) ingular, and  ( U ) nusable, each of said types being defined for both positive and negative operations;        representing both positive and negative R and S for said alleged cover image on an RS diagram;        constructing four curves constructing four curves of an RS diagram and calculating their intersections by extrapolation; and        arithmetically averaging the x coordinates of said intersections, thereby detecting said hidden message, if it exists, and estimating a length thereof.     
     
     
       40. The computer- readable storage medium of    claim 37   , said method further comprising the steps of:      applying said discrimination function and said invertible operation to define in said plurality three types of sample groups,  ( R ) egular,  ( S ) ingular, and  ( U ) nusable, each of said types being defined for both positive and negative operations;        plotting both positive and negative R and S for said alleged cover image on an RS diagram;        constructing four curves constructing four curves of an RS diagram and calculating their intersections by extrapolation; and        wherein said step of estimating further comprises determining a length p of said hidden message, if it exists, by rescaling the x - axis of said RS diagram so that p/ 2  becomes  0  and  100 −p/ 2  becomes  1 , whereby an x - coordinate of an intersection is a root of the following quadratic equation:          2   ( d   1   +d   0 ) x   2 +( d   −0   −d   −1   −d   1   − 3 d   0 ) x−d   −0   = 0 ,          where d   0   =R   M ( p/ 2   ) −S   M ( p/ 2   ) , d   1   =R   M (   1 −p/ 2   ) −S   M (   1 −p/ 2   ) , d   −0   =R   −M ( p/ 2   ) −S   −M ( p/ 2   ) , d   −1   =R   −M (   1 −p/ 2   ) −S   −M (   1 −p/ 2   ) , and said message length p is calculated from the root x whose absolute value is smaller,        p=x/ ( x−  1 / 2   ).