Reading LSB traces: the Chi-Square Attack and RS Analysis in the browser

LSB steganography hides a message in the least significant bit of every pixel value. Changing an 8-bit value by one step, say from 154 to 155, is invisible to the eye, so an image carrying a message looks exactly like the original.

Steganalysis asks the opposite question: does an image likely contain a hidden message? This post walks through the two classic algorithms used by Steganalysis Web App, how they were ported to JavaScript to run in the browser, and what they report on two sample images.

The core idea

Embedding replaces the last bit of each pixel value with a message bit. An encrypted or compressed message looks random, so every pixel value has a one-in-two chance of moving to its "partner", the value that differs only in the last bit (2k and 2k+1). The change is invisible, but it leaves a statistical trace. The two algorithms below look for that trace in different ways.

Chi-Square Attack: pairs that are too even

The Chi-Square Attack (Westfeld & Pfitzmann) treats the pixel histogram as 128 pairs of values: (0, 1), (2, 3), …, (254, 255). In a natural photo, the counts of 2k and 2k+1 usually differ. Embedding random bits evens them out, because pixels keep moving back and forth inside their pair.

For each pair, the expected count is the average of the two. The χ² statistic measures how far the histogram is from that even state:

for (var k = 0; k < 128; k++) {
  var even = hist[2 * k], odd = hist[2 * k + 1];
  var expected = (even + odd) / 2.0;
  if (expected > 0) {
    chi2 += ((even - expected) * (even - expected)) / expected;
    valid++;
  }
}
var dof = valid - 1;
var pValue = dof > 0 ? 1.0 - chi2Cdf(chi2, dof) : 0.0;

The key is how to read the result: a p-value close to 1 means the pairs are too balanced for a natural image, a strong sign of embedding. chi2Cdf is computed through the incomplete gamma function (the Numerical Recipes method), so no statistics library is needed.

The histogram is not computed once for the whole image. The code adds pixels cumulatively, at 5%, 10%, 15% and so on from the start of the image, and computes a p-value at every step. Because simple LSB embedding writes the message sequentially from the first pixel, the curve forms a plateau while it is inside the message and drops once the message ends. From that curve the app derives two things:

• suspicious if the highest p-value in the first 20% is above 0.5;
• estimated message length is the last consecutive sample point that stays above 0.5.

RS Analysis: measuring how smooth pixel groups are

RS Analysis (Fridrich, Goljan & Du, 2001) does not depend on the embedding order. The image is split into groups of 4 consecutive pixels, and the "roughness" of each group is measured with the discrimination function f(G) = Σ |xᵢ − xᵢ₊₁|. The larger the value, the noisier the group.

Two bit-flipping functions are then applied according to the mask M = [1, 0, 1, 0]:

• F₁ swaps 2k ↔ 2k+1 (x ^ 1), exactly what LSB embedding does;
• F₋₁ swaps 2k−1 ↔ 2k, the "shadow" of F₁ shifted by one step.

A group is regular (R) if f increases after flipping and singular (S) if f decreases. In natural images both masks give almost the same proportions: R_M ≈ R_−M and S_M ≈ S_−M. LSB embedding breaks that balance: the gap R_M − S_M narrows while R_−M − S_−M widens.

for (var p = 1; p < groupSize; p++) {
  var o = g[p], pv = applyMask(o, mask[p]), nv = applyMask(o, -mask[p]);
  fOrig += Math.abs(o - prevO);
  fPos += Math.abs(pv - prevP);
  fNeg += Math.abs(nv - prevN);
  prevO = o; prevP = pv; prevN = nv;
}
if (fPos > fOrig) rM++; else if (fPos < fOrig) sM++;
if (fNeg > fOrig) rNM++; else if (fNeg < fOrig) sNM++;

The same counts are computed again on a copy of the image with all LSBs flipped. From those two points, the app estimates the share of pixels that carry the message:

var d0 = c[0] - c[1], d1 = c[2] - c[3];          // original image
var d0Bar = cb[0] - cb[1], d1Bar = cb[2] - cb[3]; // all LSBs flipped
var x = (d0 - d1) / ((d0Bar - d1Bar) + (d0 - d1));
var pEstimate = Math.max(0.0, Math.min(1.0, Math.abs(2.0 * x)));

The original paper derives a quadratic equation from the four R and S curves; this implementation uses a simpler linear form. An image is flagged when the estimate is above 3%.

Grayscale as the reference, RGB as support

Both algorithms run separately on the Grayscale, Red, Green, and Blue channels. Grayscale uses the same luminance formula as Pillow's Image.convert("L") (ITU-R 601-2, fixed-point version), so the browser and Python versions read the same pixels:

gray[i] = (r * 19595 + g * 38470 + b * 7471 + 0x8000) >> 16;

The final verdict comes from Grayscale: High when both methods flag the image, Medium when only one does, and Low when neither does. The color channels only play a supporting role. A Medium verdict is raised to High when at least two of the R/G/B channels show a strong indication, while indications in the color channels on a clean Grayscale are noted as likely sensor noise or demosaicing.

Results on two sample images

The live demo ships two 720×480 test images: an original and a copy carrying an LSB message. Here is what engine.js reports:

On contoh-stego.png the p-value stays above 0.89 from the 5% sample up to 55%, then drops to 0.0069 at 60% and to 0 after that. In other words, the message occupies roughly the first 55–60% of the pixels. RS Analysis, which ignores pixel order entirely, estimates 48.2%. Two methods that work in completely different ways reach the same conclusion: about half of the image carries the message.

The RS numbers also show the theory above in action. On the original image R_M = 55.9% and R_−M = 55.8% (almost equal), while on the image with a message R_M drops to 53.2% and R_−M rises to 58.6%. These sample images are grayscale, so all four channels give identical numbers.

You can reproduce these results in the live demo with the "Citra asli" (original image) and "Citra berisi pesan LSB" (image with an LSB message) buttons.

Running entirely in the browser

The original version is a Flask app: the image is uploaded and analyzed on the server. engine.js is a JavaScript port of its Python modules and returns JSON in the same format as the /analyze endpoint, so the interface did not need to change. Pixels are read through <canvas> and getImageData() (alpha is ignored, like Image.convert("RGB")), and the analysis runs in a Web Worker so the page stays responsive on large images. The image never leaves the device.

Limitations

• Both methods target LSB replacement. LSB matching, which randomly adds or subtracts 1, does not balance the (2k, 2k+1) pairs in the same way, so it is much harder to detect with this approach.
• The 0.5 and 3% thresholds are heuristics. Treat the result as an indication, not proof.
• Spatial-domain LSB steganography does not survive lossy JPEG compression, and different JPEG decoders can produce slightly different pixel values. The results are most meaningful for lossless formats such as PNG and BMP.