Variation on the ECB Penguin problem [closed]

Question

So this is an age-old example of why encrypting images with ECB is a terrible idea, since the underlying pattern of the image remains the same. Referenced from: If you encrypt an image (AES), is it still an image and can you view it?

In this question, the answerer shows that is is easy to reconstruct an image (in the ppm format) with:

# First convert the Tux to PPM with Gimp
# Then take the header apart
head -n 4 Tux.ppm > header.txt  
tail -n +5 Tux.ppm > body.bin  
# Then encrypt with ECB (experiment with some different keys)
openssl enc -aes-128-ecb -nosalt -pass pass:"ANNA" -in body.bin -out body.ecb.bin  
# And finally put the result together and convert to some better format with Gimp
cat header.txt body.ecb.bin > Tux.ecb.ppm

The variation in this particular question is that, 1. I do not know what the header is, and 2. The header is not separated from the image.

To elaborate, let's say that I have a file called Tux.ppm which I encrypt as follows:

admin@ubuntu32:~/Documents$ openssl enc -aes-128-ecb -nosalt -in Tux.ppm -out image.bin
enter aes-128-ecb encryption password:
Verifying - enter aes-128-ecb encryption password:

Though it is not relevant to the question, for the sake of completeness, the encryption password used was foo.

Now, if I know what the header initially looked like, reconstructing the image is simple. Say, if I know that the header for Tux.ppm was:

P6
265 314
255

Then, if I simply create a new file, call it header.txt, add the above content to it, and execute:

cat header.txt image.bin > sampleTux.ppm

Then sampleTux.ppm is still entirely recognizable:

Nevertheless, the illustrate a certain point, if I mess the header up just a little bit (e.g. modify the width to 275 and the height to 324), the image screws up beyond recognition.

Say that I've now been given a file called image2.bin. I know that this image was initially a PPM image which was encrypted like above (i.e. it was encrypted with its header). I know that it is a P6 type image which uses the 255 color-encoding format. What I don't know is the width and the height of the initial image, so I cannot construct a new header for it.

How can I create such an "ECB Pengiun" for image2.bin? How can I get information about its initial width and height without guessing it (if that is at all possible)? As illustrated above, that width and height has to be quite exact, otherwise the image completely distorted.

EDIT: In the interest of making better guesses. Assuming that the image not compressed and was created from a standard A-series (A4, A5, etc.) paper, I know that is has a ratio of length-in-millimeters = sqrt(2) * height-in-millimeters. Furthermore, it has a possible DPI of 72, 150, 300 or 600... which still leaves a lot of possibilities.

Maybe I could narrow down the possibilities further if I knew the amount of pixels in the initial file? Could I just get this information from the size of image2.bin or would I have to do something infeasible such as reverse-engineer the process which AES encrypted the file in the first place?

Answer 1

You cannot, at least not if that's the only encrypted image. ECB leaks information because repeated plaintext blocks lead to repeated ciphertext blocks. But it doesn't leak the information within those blocks directly.

So you could find the original size by finding another encrypted picture with the same header of which you already know the size. In that case the encrypted header should be identical.

Otherwise, smart guessing might be the best way forward. If you look at the vertical lines then there should be a high amount of repetition between one horizontal line and the next. Just shifting the image and selecting the one with the most vertical repetition should do the trick.

Answer 2

For the benefit of anybody reading this in the future:

In this particular instance, to get the amount of pixels the image has, get its size, convert the bytes to bits (if necessary) and then divide by 24. This is because PPM format uses 24 bits per pixel: https://en.wikipedia.org/wiki/Netpbm_format

As per the assumption in the edited part of the question above, let's just assume the image was initially A4 and so we know the ratio of length to width (length-in-millimeters = sqrt(2) * height-in-millimeters).

Say that image2.bin had a size of 3000000 bytes or 24000000 bits. We assume that the 1-byte header is negligible. Therefore, noPixels = 24000000/24 = 1000000. Next, we know that length-in-pixels * width-in-pixels = 1000000 and that length-in-millimeters = sqrt(2) * width-in-millimeters. For simplicy, assume that our image has a DPI of 92 which means that 3.8 pixels = 1 mm (approximately). So, length-in-millimeters = 3.8 * length-in-pixels and width-in-millimeters = 3.8 * width-in-pixels.

With this information, we just get 2 equations:

length-in-pixels * width-in-pixels = 1000000
3.8 * length-in-pixels = sqrt(2) * 3.8 * width-in-pixels

Which means that now it is just a matter of solving 2 simultaneous equations.

length-in-pixels = sqrt(2) * width-in-pixels (3.8 cancels out)
sqrt(2) * width-in-pixels * width-in-pixels = 1000000
width-in-pixels^2 = 500000 sqrt(2)
width-in-pixels = sqrt(500000 sqrt(2)) = 841 (approx)
and thus
length-in-pixels = sqrt(2) * sqrt(500000 sqrt(2)) = 1190 (approx)

So we know that the size of the image is 841x1190

Answer 3

Not the best code, but you can generate all possible size for headers

#!/bin/bash

for i in $(seq 1 2); do
  for j in $(seq 1 2); do
    echo "p6" >> $1"_"$i$j.txt
echo -ne $i" "$j"\n" >> $1"_"$i$j.txt
    echo "255" >> $1"_"$i$j.txt
  done
done

Apart from Maarten's smart guesses; the number of pixels $N_p$ must be a product of two numbers. If you find the factorization of the $N_p$ than you can try with minimum ppms.