Tags: zlib png 


# Task
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
enc = hex(C)[2:].rstrip('L').decode('hex')
enc = ('0' + hex(C)[2:].rstrip('L')).decode('hex')
return enc

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

f = open('flag.enc', 'w')

# 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:
ciphertext = f.read()
ciphernum = int.from_bytes(ciphertext, byteorder="big")

def from_base(n, b):
l = []
while n != 0:
n,d = divmod(n,b)
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

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