Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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.

share|improve this question
    
Just a terminology nit-pick here, if you have "repeated it over the length of the image" it's not a one-time pad. A one-time pad must be exactly the same size as the image. The relative sizes of the key/stream and the image make a big difference to whether the key can be retrieved or not. –  Ladadadada Mar 9 '13 at 20:40
    
@Ladadadada Thanks for pointing it out. However, I'm quite aware of that fact (title of the question should be sufficient), but I thought I'd mention it's a one-time pad because that's what the attempt to encrypt the image data seemed to most appropriately resemble. –  Khaled Nassar Mar 9 '13 at 20:48
    
This is a variant of the Vigenère cipher –  CodesInChaos Mar 9 '13 at 22:15

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
The idea of the padding actually solved it. Thanks! –  Khaled Nassar Mar 10 '13 at 20:45

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.

share|improve this answer
    
Is the chances / probability related to use of common dictionary words? –  Saladin Mar 9 '13 at 22:52
    
I can see how it would work with the assumption that the key is short, and is in plain English. However, that's not the case here, check out the edit. –  Khaled Nassar Mar 10 '13 at 4:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.