Uncovering file hidden in .BMP
One of the simplest textbook example of steganography in a bitmapped image (as opposed to formats providing lossy compression such as JPEG), is low-order-bit steganography. In such system, the low-order bits of the pixel components (gray-scale or RVB or CYMK levels, typically stored as a binary number of 8 bits) are modified in some way to hold information; this is hardly visible to the eye (especially on natural images with some degree of noise).

In some systems, the hidden information is the low-order bits of the pixel components. In that case, it is often possible to conclude that the image contains a steganographic message (and get at it, unless it is encrypted before insertion). Detection is based on the fact that in natural images, the low-order bits are correlated with nearby bits (that is, the higher-order bits of the same pixel component, bits of any other color components of that pixel, and bits defining adjacent pixels). The stego replacing the low-order bits removes this correlation, and instead it is seen low-order bits exhibiting the statistical characteristics of those in the payload if uncompressed and unencrypted; or seemingly close to uniformly random and independent otherwise.

But there can be other ways, including XOR-ing the low-order bits of the base image with the hidden information, as in a stream cipher. In that case, we (and the intended receiver) need some information about the low-order bits in the base image. Possibilities include


somewhat get hold of the base image (that would typically apply to the receiver);
exploit some known/guessed/assumed characteristic of the low-order bits in the base image (like their aforementioned correlation with nearby bits).


Worth considering: perhaps few low-order bits are changed; this makes conclusively proving the use of stego much more difficult, but worsens the already large bandwidth requirement.



On the particular problem: we are given MOVIE.BMP (2764854 bytes), a BMP (short for bitmap) file on a web page with a message hinting at stego in the image. Webmasters almost never uses BMP files that large, especially for an image promoting a movie, where JPEG easily saves an other of magnitude on bandwidth usage. All this prompts at steganography on low-order bit, or similar.

The 2764854 bytes consists of a 54-byte header (14-byte BMP header and 40-byte BITMAPINFOHEADER) followed by 1280x720 RVB components of 3 bytes each. There is no extra data (a primitive form of steganography is to append the payload at the end of a file, where rendering programs typically ignore it). The header is unremarkable, except perhaps that the 8 bytes for the horizontal and vertical resolution are zero.

Since the image is promoting a movie, it is worth feeding it to a search engine accepting images, in hope to locate the base image used. We want a visually very similar image, such that when some common program saves it (or a crop/resize thereof) as bitmap, we get something extremely close to the bitmap in MOVIE.BMP. I tried a few of the first hits of two search engines, and two programs: a paint program bundled with Windows, and IrfanView. I used primarily the later, because it is the only of the two I found sometime leaving the horizontal and vertical resolution fields at zero; and also because it can save images into a simple text format (PPM-text) which eases comparison and analysis.

I quickly narrowed down on maxresdefault.jpg (118533 bytes) as remarkably close to the original: after conversion to BMP format using IrfanView, a file compare (with fc /b maxresdefault.bmp MOVIE.BMP) yields only 955 different bytes (list by the OP), and the differences all are in low-order bits. By contrast, the other program yields 88119 different bytes, with differences not limited to the low-order bit (lots of &pm;1 that change more than the low-order bit, and many &pm;2; that could be due to minor differences in the JPEG decompression, like using the lower precision arithmetic of SIMD instructions versus the FPU). Some other online images I tried, like IMG_0825.jpg (128356 bytes), yield the exact same 955 differences (ignoring the resolution field); others (including conversions of MOVIE.BMP to JPEG) give overwhelmingly more differences.

I so far conclude that


with good certainty, MOVIE.BMP was prepared from a JPEG image yielding the same pixel data as maxresdefault.jpg does;
the tool used for the JPEG decompression of that file uses algorithms yielding very close to the same result as the algorithms used by IrfanView, hopefully exactly the same;
likely, after the JPEG decompression, at most 955 low-order bits (and hopefully exactly that much) have been altered;
accidental variants in JPEG decompression code seem more likely to yield differences of &pm;1, then only &oplus;1 as observed. That tends to comfort that indeed there is stego involved (but is far from proof).


I tried just a few more things, but basically I'm stuck:


In the (conjectured) base image maxresdefault.bmp, 1323359 out of 2764800 low-order bits are set (47.865%). 439 out of 955 bits flipped in MOVIE.BMP were previously set (46.0%), that's not a significant difference (a Pearson chi-squared test gives a two-tailed p-value 0.24).
I found no pattern in the addresses, pixel coordinates, or RGB planes where the flips occur.