Nofix - Reverse Engineering Blog

Reverse engineering malwares for fun on my spare time

Recently I have been asked to create a script that embeds randomly a payload into an image using LSB embedding, and to create a function that could detect whether or not an image contains a payload. I have been doing researches and I found that the Sample Pair Analysis appeared to be the latest and the most efficient method to do so. I will try to explain it here, without all the maths the papers I have been reading were including.

What is SPA (Sample Pair Analysis)?

​ The sample pairs analysis is a technique that can be used to detect steganographic content in an image. It is extremely accurate, and researchers estimate that it is able to detect steganographic content embedded in a picture as soon as the rate exceed 3% of the medium.

To explain this technique, I have been reading a book and a research paper, full of formulas (see Annex). I will be trying to popularize the SPA technique so that you don’t have to go trough the formulas as I did to understand the principle. I will try to give you the less maths I can possibly can. It is up to the reader to go read the maths behind the principles I will present here.

LSB is an asymmetric operation because the process of hidding your message will decrease the value of odd value pixels, and increase the value of pair value pixels.(1)

Example:

• Pixel (A) = 1101 1100 = 219 -> LSB -> 1101 1100 or 1101 1101
• Pixel (B) = 0011 0111 = 55 -> LSB -> 0011 0111 or 0011 0111

​ On those pixels, if I need to store a 0 into an even pixel value (a), the pixel wont need to be modified. On the other hand if I need to store a 1, the global value of the pixel will increase.

The exact opposite occurs for odd pixel values (b). If I need to store a 1, the pixel wont be modified. If I need to store a 0, the value of the pixel will decrease.

​ This create statistical bias that one can exploit to detect if a message is hidden or not, using one of the many techniques that exists. The easiest way to notice that the visual way, is at looking at the histogram of a picture before and after the insertion of data in LSB of pixels :

https://security.stackexchange.com/questions/176276/lsb-replacement-and-its-effect-on-grayscale-histogram

F1. Abscissa: light intensity, ordinate: number of pixels

​ The histogram on the left is before insertion of data into LSB, the histogram on the right is after insertion of data into LSB. The figure (F1) looks a bit exaggerated but it is a good example of how one can detect such bias. The purpose of this image is to convince you that LSB creates statistic bias in an image. Looking at this histogram you could see big differences between neighboring intensities, because LSB perturbs natural evenness of neighboring intensities for normal images.

Here is a more realistic example:

Before insertion

After insertion

Long story short, this is the asymmetrical nature of the LSB replacement operation that allows us to detect it thanks to the bias it creates, no matter the method we will be using to detect it.

Detection of LSB embedding trough Sample Pair Analysis technique.

F2 - Histogram of neighboring pixels pair $(r,s)$ for 6000 RAW images.

​ Unlike the histograms of pixels shown in (1), an histogram of neighboring pixel pairs $(r, s)$ is predictable, as shown on the figure (F2). However, the histogram of pixel pairs will still be useful. It tells us something interesting: huge differences in neighboring pixels values are way less likely to occur then small ones (take a moment to understand the figure).

On this picture, you can see that big transitions (in red) are more rare than small ones (in green). That is an example but this applies to almost any normal image.

For the Sample Pair Analysis, we will be needing to take a close look at pairs of neighboring pixels.

​ Let’s imagine you are iterating over pairs of neighboring pixels from the above hilarious meme, from left to right. We are iterating over neighboring pixel pairs that I will name $(r,s)$. There are 4 possibilities for our 2 neighboring pixels:

$$(r,s) \in \{(2i,2j),(2i,2j+1),(2i+1,2j),(2i+1,2j+1)\}$$

In maths, the set $\{ {2t + 1} \}$ represents the set of odds integer. Thus, the above statement can be read : for all pair of pixels $r,s$ such as $r,s$ is part of a set made of ${(pair, pair), (pair, odd), (odd, pair), (odd, odd)}$. I will be using the above notation for the rest of the article, so be sure to understand it.

On a normal image, no particular stuff should be detected on the image. We will see that after LSB embedding, we will be able to exploit to previously presented bias looking at pairs of pixels in order to detect a hidden content.

​ Let’s take the case when $% $:

​ On the above figure, you can see the change of probabilities that LSB embedding does on pair of pixels (see 1 if this is unclear yet). I first will explain the figure on the left.

​ Let be a pair of pixels $(r,s)$ such as $% $. On the left figure, $r$ is even (LSB is at 0) and $s$ is odd (LSB at one). Due to property (1), the value of $r$ can only increase or stay the same. On the other hand, the value of $s$ can only decrease or stay the same. On this situation, because r < s, doing a LSB embedding to hide a message will lower the chances of encountering the pair $(2i,2j+1)$ (e.g : left pixel has the value 126 and right one has the value 127. Flipping both LSB will make the left value be superior to the one on the right). This assumes that the embedded payload is pseudo-random (encrypted content is a good example of that).

Similarly, according to the figure on the right (that is the exact opposite) we can expect to encounter more pairs of $(2i+1, 2j)$ when $% $.

​ I framed in red that the important element that rules this new bias is the LSB of the second pixel $s$. It is mainly because this bit changes that we can conclude the above properties. The left bit has little impact on occurrences probability detailed here.

This whole thing also works the other way : if $r>s$ we expect to encounter more pairs $(2i, 2j+1)$ and less $(2i+1,2j)$.

​ One thing to note is that this only works when bit gets flipped by LSB embedding, and so is proportional to the rate of the hidden message. In other words, the bigger our hidden message is, the bigger will be the bias, the few we will encounter $(2i, 2j+1)$ when $% $, etc.

Reminder: on a normal image, there is no reason that we notice any particular average change in pairs of pixels when $r>s$ or $% $.

Let’s put all those statements into equalities. Let $X,Y,Z$ be 3 sets.

• We will put in $X$ every pair of pixels $(r,s)$ such as $r>s$ and $s$ is odd or $% $ and $s$ is even (those have lower chances to happen proportionally to the length of the hidden message due to LSB embedding). [A]
• We will put in $Y$ every pair of pixels $(r,s)$ such as $r>s$ and $s$ is even or $% $ and $s$ is odd (those have better chances to happen proportionally to the length of the hidden message due to LSB embedding). [B]

• We will put in $Z$ every pair of pixels $(r,s)$ such as $r=s$ (cases 0,0 and 1,1, represented in our possibilities by $(2i,2j), (2i+1,2j+1)$).

We now have:

​ As explained earlier, because there is no reason to notice a correlation between $\| r-s \|$ and the LSB of $s$ on a cover image (in a general manner, there is no reason to notice anything special in a cover image), we should have $\|X\|\approx\|Y\|$ .

$\|S\|$ represents the cardinality of the set $S$. The cardinality is the number of element a set has.

We know that embedding a payload into an image will broke this equality. As mentioned earlier in [A], $\|X\|$ will lower with the length of our payload, while $\|Y\|$ will increase with the length of the payload. We know need to quantify this change rate that I will call $\beta$.

Please note that the full mathematical demonstration of the above statements, with probabilities, equalities and equations are in Annex.

We now need to be able to efficiently quantify the change rate $\beta$. Hopefully, with some more maths, more sets and probabilities I will not be detailing here (maybe later in Annex if I have time later on), we can get a quadratic equation that represents efficiently the change rate.

The quadratic equation ($0=ax^2+bx+c$) that will give a change rate as a result is represented by:

We can now solve the equation :

​ Good, we have our $p$ value that represents our change rate. From now on, we have only been solving for the red channel. We obviously need to try to detect a message in each channels of pixels (R,G,B). I personally calculated the average of the sum of my 3 rates (one for each channel : R, G and B).

We now need a threshold to determine whether or not our picture contains a hidden message, with the lowest false positives as possible. I found that a good threshold value is 0.025.

To sum it all up, here is a python algorithm:

        """
Sample Pair Analysis algorithm used to determine if a channel holds
a message or not. This will be used on 3 channels and calculate the
average of the 3 SPA. Treshold value is 0.025
"""
width, height = image # opened with Pillow
pixels = []
for i in range(width):
for j in range(height - 1):
pixels.append((channel[i, j], channel[i, j + 1])) # we will take pairs of neighboring pixels
z = 0 # we define our 3 sets
y = 0
x = 0
for k in range(len(pixels)):
r, s = pixels[k]
if (s % 2 == 0 and r < s) or (s % 2 != 0 and r > s): # getting the number of elements in the set X
x += 1
elif (s % 2 == 0 and r > s) or (s % 2 != 0 and r < s): # getting the number of elements in the set Y
y += 1
elif math.floor(r / 2) == math.floor(s / 2):
z += 1
if z == 0:
logger.log("[-] SPA failed", logger.FAIL)
sys.exit(1)

"""
resolution of the second order equation to get a rate
we have 0 = ax**2 + bx + c
with a, b and c described bellow
In a normal image, the delta between sets X and Y should be 0.
As LSB replacing is an asymmetrical opération, the delta
between X and Y changes. This delta can be calculated by
a quadratic equation which a,b and c are defined bellow.
We try to estimate the lenght of a possible hidden
message resolving it.
"""
a = 2 * z  # 2 * identical values
b = 2 * (2 * x - width * (height - 1)) #
c = y - x # beta, difference between X set and Y set
D = math.pow(b, 2) - (4 * a * c) # Delta of second order equation
if(D < 0): # no solutions in reals (imaginary solution)
return -1.0 # mostly a fail
p1 = (-b + math.sqrt(D)) / (2 * a) # solving second order equations
p2 = (-b - math.sqrt(D)) / (2 * a) # second solution
return min(p1, p2).real


Here is the ROC curve associated with this threshold, for 94 given images:

This method is really efficient. As you can see I had a few false negatives over low steganographic rates (4%-8%). For cover images, I had one or two false positives, which is decent.

Annex

Probabilities of $h_\beta[2i+1,2j]$ and $h_\beta[2i,2j+1]$ when $% $

When $% $:

“[…] LSB embedding changes any pair into another with probability that depends on the change rate $\beta$. […] $h_\beta$ is a convex combination of the cover counts for all four pairs of possibilities. $h[2i,2j]$ is the count of pairs $(2i,2j)$. If the payload is embedded pseudo-randomly in the image:

$h_\beta[2i+1,2j]$ will decrease with $\beta$ because three out of four terms in the first equality are smaller than $h[2i+1,2j]$. By a similar argument, $h_\beta[2i,2j+1]$ will increase with $\beta$.” ref(page223)

References

Detection of LSB Steganography via SamplePair Analysis, Sorina Dumitrescu, Xiaolin Wu and Zhe Wang.

Steganography in Digital Media: Principles, Algorithms, and Applications, Jessica Fridrich.

Nofix -