Tags: zlib png

Rating:

This was more a forensic challenge than a crypto challenge. Alongside flag.enc, the following code was given

~~~
from secret import exp, key

def encrypt(exp, num, key):
assert key >> 512 <= 1
num = num + key
msg = bin(num)[2:][::-1]
C, i = 0, 1
for b in msg:
C += int(b) * (exp**i + (-1)**i)
i += 1
try:
enc = hex(C)[2:].rstrip('L').decode('hex')
except:
enc = ('0' + hex(C)[2:].rstrip('L')).decode('hex')
return enc

msg = int(flag.encode('hex'), 16)
enc = encrypt(exp, msg, key)

f = open('flag.enc', 'w')
f.write(enc)
f.close()
~~~

# Encoding
flag = open('flag.png', 'r').read() so the flag is inside a PNG image, a file format with a fixed structure.

The encryption can be summarized as
$$C = \text{exp} \cdot \text{base-exp encoding} \circ \text{base-2 decoding} (flag + key) + \text{number of one-bits in even positions} - \text{number of one bits in odd positions}$$

where assert key >> 512 <= 1 ensures that key is very small, compared to a complete png image. With key of the same size as the input data, it would be a secure one time padding.

# Decoding

First, read flag.enc as number and decode it in base b=exp, guessed as 3
~~~
with open("flag.enc", "rb") as f:
ciphernum = int.from_bytes(ciphertext, byteorder="big")

def from_base(n, b):
l = []
while n != 0:
n,d = divmod(n,b)
l.append(d)
return l

exp = 3 # guessed / tried small values

cipherlist = from_base(ciphernum, 3)
~~~
This givs a list of digits, mostly 1 and 0, ending with the binary representation of "\x89PNG", ... 1,0,0,1,0,0,0,1].

At the Beginning of the list (least significant digits), there are some 2s, but it is expected as garbage, because the numer of one bits is added/substracted during encoding. Also the key (512 bit, 64 byte) is added, modifying the least significant digits. The length of the list is 1 mod 8, as there is a off by one is the encoding function.

A PNG image starts with a header and is divided into chunks, see <http://www.libpng.org/pub/png/spec/1.2/PNG-Structure.html>, the last chunk is always IEND with length 0, so the last 12 bytes are known as "\x00\x00\x00IEND" + crc32("IEND"), preceded by 4 bytes crc32(IDAT chunk) so we can ignore the beginning of the cipherlist. There remain 48 byte of image data corrupted by the key.

~~~
def as_base(l, b):
return sum((d*b**i) for (i,d) in enumerate(l))

image_number = cipherlist[1 + 8*(4+4+4+4) :]
corrupted_image = image_number.to_bytes(byteorder="big", length = (image_number.bit_length()+7)//8)
~~~

ath the end of the corrupted_image there is the "IDAT" chunk, ending in corrupted 48 bytes. The "IDAT" chunk is compressed by zlibs deflate algorithm, but decoding it with zlib.decompress fails with an exception, so it does not return the successful inflated prefix. My workaround was to use zlib-flate -uncompress from the qpdf package:

~~~
def inflate(data):
import subprocess
flate = subprocess.Popen(["zlib-flate", "-uncompress"])
inflated, errors = flate.communicate(data)
return inflated

idat_data = [corrupted_image.find(b"IDAT") + 4 : -48]
image = inflate(idat_data) # size around 8kB
~~~
there is some data missing at the end, so i appended some zeros (transparent pixels)
~~~
image += b"\x00" * 10000
~~~
and compressed it again
~~~
import zlib
idat_data = b"IDAT" + zlib.compress(image)
idat_length = (len(idat_data) - 4).to_bytes(byteorder="big", length=4) # len counted without "IDAT"
idat_crc = (zlib.crc32(idat_data) % 2**32).to_bytes(byteorder="big", length=4) # crc calculated with "IDAT"
idat = idat_length + idat_data + idat_crc
~~~
at last, we need a valid IEND chunk. It can be copied from any PNG image.
~~~
iend = b'\x00\x00\x00\x00IEND\xaeB\x82'
~~~
put everything together and save it to a file
~~~
f = open("flag.png", "wb")
f.write(corrupted_image[ : corrupted_image.find(b"IDAT")] ) # header
f.write(idat)
f.write(iend)
f.close()
~~~

this image could was opened successfully by an image viewer (for example the display` command)