Many-time pad on image data, how to proceed?

Question

I have raw image data that is XOR-encrypted with a fixed-size one-time pad repeated over the length of the image. I know what the format of the image data container is so I can successfully retrieve the first 6 bytes of the key.

But that's it so far, I have no idea how to proceed.. Are there relations between adjacent pixels? Has any research been done on the subject, and if there is, how? I've searched for hours to no avail.

EDIT

The file is a Windows BMP image (BM magic number) with a BITMAPINFOHEADER. That's why I can correctly guess the first 6 bytes and a few more bytes in between.

The key is a stream of 337 bytes generated by a PRNG, more specifically, Mersenne Twister. So the key could be considered random for now.

Right now, all I'm left with is, well, XOR difference between two lines in the image. There is a pattern, I just don't know what to make of it exactly.

Answer 1

You have a 337 byte key that's repeated ad nauseum and then XORed with all the bits of a image file.

You can probably exploit some factor of the BMP, like how it has Padding (at the end of each row of the pixel data so each row is a multiple of 4 bytes and typically would be zero. So you could guess image height/widths, find where the padding would be, and then set the bits of the key at those places.

There maybe other properties of the image you can exploit; e.g., sparsity under a sparisfying transform (similar to compressed sensing), and can tweak each bit to see if leads to a better image.

Answer 2

Classical cryptanalysis of the many-times-pad (aka Vigenère's cipher) is about encryption of a text; the attack then uses the frequency of letters and pairs of letters and completing partial words, each time propagating findings (when you know a plaintext byte, you know the corresponding key byte, and thus you can decrypt all the bytes where that key byte was used, which are easy to locate modulo an hypothesis on the key length). See for instance this automatic decryption engine.

With a picture, you will have to work your way depending on the level of structural redundancy in the file format. So it depends a lot on the exact file format: is that a BMP, PNG, JPEG ? The most compressed formats may give you trouble, because compression is exactly about tracking down and removing redundancies (to reduce the file size). I am not claiming that compression makes many-times-pad safe, only that it will require more effort from the attacker.

If you already know the first 6 bytes of the key and you suppose that the key is short (say 10 bytes or less) then you can do an exhaustive search on the missing bytes. If the key is a character string, it might be "meaningful": e.g. if it starts with platyp then chances are that the next two key bytes will be us.