Uncovering file hidden in .BMP I've recently been linked by someone to this particular puzzle which seems to point to a hidden file within the image. The clue given to me was "anagram" although I could not make much sense of it. Steganography comes to my mind but despite several effort at cracking it, nothing works.

http://securitystartshere.org/downloads/cddc/homework/

How can we generically process to try attack this kind of problem, where we are given an image (especially, an uncompressed one), suspect a primitive form of steganography, and do not know the method (contrary to Kerckhoffs principles, but according to practice as faced by  cryptanalyst, especially in the field of practical steganography)?  

Fgrieu has given a few tips such as binary comparison after identifying and proceeding with proper conversion of a clean file to the same format as the encoded file. However I am unsure of the follow-up to this methodology, having extracted the byte difference into a separate file, no common file extension seem to yield any executables.
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.