2
$\begingroup$

I have three binary arrays each one representing the pixels of an image. For example, if the picture size is 100 pixels X 100 pixels. Then the binary array would be 100×100×8×3 bits. These files are encrypted using the same cypher generated using LFSR.

What do we know about the LFSR?

  1. The polynomial is [1,0,0,1,0,0,0,0,0,0,0,0,1,0,1,1]
  2. memory size is 16

How would I go about finding the seed and decrypting the images?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

If the ciphertexts are R, G, B, try to form R⊕G, G⊕B, B⊕R, and visualize that. If the keystream is identical for the three as the question seems to suggest, the keystream will cancel out and you'll likely be able to guess what the image is by seeing it, without even considering the LFSR.

For full recovery, one option is to try all 216 = 65536 seeds, apply the LFSR to generate the keystream, decipher, and select the seed that leads to tentatively deciphered plaintext with the worse score at Pearson's chi-squared test of byte values (256 categories). Even if seeds were different for the three planes, that should work.


Re-updated: my reading of the question is that the LFSR is 16-bit with in principle* given polynomial. We can prepare a table with index the current two-byte state and output the new state after producing two bytes. Thus producing two bytes of keystream costs a single table lookup. A competently coded Pearson test is fast. Thus testing all seeds and picking the right one is feasible in seconds. Plus it's likely enough to decrypt and Pearson-test one or few rows of the image, rather than the whole image.

For further speedup, we may be able to use the "idea about what the image is" that was reportedly obtained by the technique in the first paragraph. If in the image (say) R⊕G we see an area with no contrast at all (a fraction of a line will do), we can confirm that by verifying that the corresponding bytes of R⊕G are identical. If so, quite likely, the corresponding bytes in R are identical, same (with a possibly different byte value) those of G. Having determined that say 4 or 5 consecutive bytes in the plaintext are identical, we have only 256 hypothesis to test for the LFSR state at that point (one for each of the common value of the bytes), and can pinpoint the right one. The whole keystream follows (it's easy to walk an LFSR forward and back). That would even allow solving the problem without the polynomial (and associated guesswork*), using the Berlekamp-Massey algorithm.


* The description of the polynomial in the question can be interpreted according to several conventions (low-order term first or last; one implicit term at either end, or none). Also, if the ciphertexts are available as bytes rather than bits (that depends on the file format), bits can be assembled into bytes according to big-endian or little-endian convention. If we have neither the code nor a known plaintext/ciphertext/key example, we may have to try 2×3×2 = 12 options of keystream (not counting the ambiguities in mapping seed to initial state, which we don't care, since our goal is to recover the keystream and images, not the seed).

$\endgroup$
2
  • $\begingroup$ So yes the keystreams are the same for the three images. However, every image contains its own R, G, and B channel. I tried XORing every 2 images and yes I can get an idea about what the image is. Some of the contents can be seen ,however , I would still want to know the seed. I have tried doing brute-force like you suggested but it takes so much time. Maybe because the way I generate cyphers is slow but for every seed I need to generate a cypher that's 960,000 bits long. Because my original images are 200 x 200 $\endgroup$ Commented Jan 20 at 17:48
  • $\begingroup$ I am sorry but can I ask you to elaborate on that last part. So two identical bytes in one image or two identical bytes in 2 images. How would I use the info of having two identical bytes to reduce the search space? $\endgroup$ Commented Jan 20 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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